# Gray code

This topic is 3491 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi. I know about the FAQ and this is indeed partially homework related. I'm not asking someone for a solution but rather a direction. I need to write a recursive function that gets two strings and checks whether they differ by only one bit. The thing is the skeleton of the function is already given (you can assume that the stings only contain 0's and 1's and are of the same length):
boolean IsGray(String s1,String s2)
{
if ((s1.length()==0) || (s2.length()==0))
return false;
if (s1.charAt(0)!=s2.charAt(0))
{
// Do stuff
}
else
{
// Do stuff
}
}

I only got here:
boolean IsGray(String s1,String s2)
{
if ((s1.length()==0) || (s2.length()==0))
return false;
if (s1.charAt(0)!=s2.charAt(0))
{
boolean res=IsGray(s1.substring(1),s2.substring(1));
if (res)
return false;
else
return true;
}
else
{
return IsGray(s1.substring(1),s2.substring(1));
}
}

As expected this code only checks if they differ by an odd number of bits. Any suggestions, tips and such would be greatly appreciated.

##### Share on other sites
Quick question: you say you are checking if they differ by only a bit; does this mean that in the case where one bit or less are different, to return true? Or only return true if the strings are identical?

Can you please be very specific as to the 'true' conditions?

##### Share on other sites
The function should return true only if the two strings differ by exactly one bit.
For instance:
s1=0001
s2=0000
returns true
but
s1=0001
s2=1000
returns false.

##### Share on other sites
Quote:
 Original post by CableGuyThe function should return true only if the two strings differ by exactly one bit.
It is often helpful to think of boolean problems in terms of their inverse - in this case, you can return false as soon as you encounter second bit that is different, or at the end of the strings if all bits are the matching.

##### Share on other sites
But I can't count how many bits differ. My first thought was when I encounter two bits that are different check if there are more and return false, as written in my first post. But since it is recursive, it checks if the number of bits are odd.

##### Share on other sites
Consider these hints:

- For your function, the only data that you can pass recursively are the two strings themselves. This means you need to think about string usage and manipulation.

- Each recursive call always checks the first index of each string to compare. If the function always checks the first index of the string for each recursive call, what would that indirectly imply about the parameter strings that are passed each recursive chain (would they be the same string always or not)?

- Are the parameters passed by reference or by value? If they are passed by value, it means you can modify them in place. If they are passed by reference, then you will be passing a new object. The answer to this does not matter in particular, but it is related to the previous hint.

I think that's about as much can be said without giving it away, good luck [smile]

##### Share on other sites
As I see it, the function should "choose" different code paths depending on what was found previously but I can't know that.
Quote:
 - Each recursive call always checks the first index of each string to compare. If the function always checks the first index of the string for each recursive call, what would that indirectly imply about the parameter strings that are passed each recursive chain (would they be the same string always or not)?

Sorry didn't quite get you. Did you mean I have to trim the strings I pass? If so did you look at the code at bottom of my first post?

##### Share on other sites
Is there any reason why this needs to be recursive in the first place.

With a simple loop over two equal-length strings it shouldn't be hard to inspect each pair of characters and keep a counter how many are different. You can stop earlier as already suggested, or continue till the end of the strings if you for some reason really want to find out the total count of different bits.

Of course, it wouldn't be hard to turn that into recursion either...

##### Share on other sites
Quote:
 Original post by visitorIs there any reason why this needs to be recursive in the first place.With a simple loop over two equal-length strings it shouldn't be hard to inspect each pair of characters and keep a counter how many are different. You can stop earlier as already suggested, or continue till the end of the strings if you for some reason really want to find out the total count of different bits.Of course, it wouldn't be hard to turn that into recursion either...

It needs to be recursive because that's the requirement.

##### Share on other sites
Don't know if I'm giving the answer away, but I'll try to just give you a hint (according to how I solved it). Return in this form: return a + b;. What a and b are, and what operator to use instead of + is up to you ;)

1. 1
2. 2
3. 3
4. 4
frob
13
5. 5

• 16
• 13
• 20
• 12
• 19
• ### Forum Statistics

• Total Topics
632171
• Total Posts
3004555

×