Create number sequence of length x with only difference of 1 bit in successive numbers

Question

Was asked this Amazon Telephonic Interview Round 1

So for Length = 1

0 1 (0 1)

Length = 2

00 01 11 10 (0, 1, 3, 2)

and so on

write function for length x that returns numbers in digit(base 10) form

Answer 1

That's called gray code, there are several different kinds, some of which are easier to construct than others. The wikipedia article shows a very simple way to convert from binary to gray code:

unsigned int binaryToGray(unsigned int num)
{
    return (num >> 1) ^ num;
}

Using that, you only have to iterate over all numbers of a certain size, put them through that function, and print them however you want.

Answer 2

This is one way to do it:

int nval = (int)Math.Pow(2 , n);  
int divisor = nval/2; 
for (int i = 0; i < nval; i++)
{
    int nb =(int) (i % divisor);
    if ( nb== 2) Console.WriteLine(i + 1);
    else if (nb == 3) Console.WriteLine(i - 1);
    else Console.WriteLine(i);
}