edited by
1,403 views
0 votes
0 votes

Was solving the GO 2019 pdf when I encountered this question asked in TIFR 2017. Although I have understood this question, I have one doubt-

It is mentioned in the question that for a 3-bit number, the ordering (000, 100, 101, 111, 110, 010, 011, 001) is one of the possible Gray codes.

Then, how many such orders are there for an n-bit number? 

edited by

2 Answers

0 votes
0 votes
If we model as hypercube then we can convert it to bipartite graph. And from bipartite graph we can get number of hamiltonian cycles. For 3-bit,

V1                                       V2

000 (4-possibilities)        001(3-possibilities)

011  (3-possibilities)        111 (2)

101 (2)                                100(1)

110(1)                                 010(1)

 

Total = 4*3*3*2*2 =144 but as they are cycles divide by 2. So total = 72.

Please let me know if there is any wrong wit this method.
0 votes
0 votes
we have a unique gray code for each binary combination which is obtained by Exoring in some manner,

since we have 2^n binary combinations for n-bits similarly,we have 2^n combinations of gray code for n-bits

Related questions

0 votes
0 votes
2 answers
1
air1ankit asked Aug 24, 2017
1,602 views
x1= 10101010x2=11111111x1x2 >EX-OR >GRAY CODE ->(Output in decimal)????
0 votes
0 votes
1 answer
2
Himanshu1 asked Jan 5, 2016
483 views
1 votes
1 votes
2 answers
3
shikharV asked Jan 3, 2016
3,365 views
I read somewhere that gray code is self-complementing but I couldn't find any explanation for that. Please tell if anyone has some idea about it.
0 votes
0 votes
0 answers
4
sripo asked Dec 9, 2018
640 views
How was this years paper? I haven't answered but what is the competition scenario? Like number of students applying versus seats available.Same style of question like pre...