[ lichess ]
Some amazing games
15+15 • CLASSICAL
0 Inaccuracies 0 Mistakes 0 Blunders
3+0 • BLITZ
An excellent move!
A Gray code is a list of all 2^n bit strings of length , where any two successive strings differ in exactly one bit (i.e., their Hamming distance is one). source The problem is, how to generate Gray Code for a given length n. When n = 2 , Gray Code : 00 01 11 10 When n = 3, Gray Code : 000 001 011 010 110 111 101 100 000(0) position Gray code string 000 001(1) -> 001 010(2) -> 011 011(3) -> 010 ..... Key observation - For the K position, the Gray code string is S . if i and (i+1)- th bit of K is equal then i- th char of S will be ' 0 ', otherwise, it will be ' 1 '. Code : int n; cin >> n; for(int i = 0; i < (1 << n); i++) { int value = ( i ^ (i >> 1) ) ; string s = ""; for(int j = 0; j < n; j++) { if( value & (1 << j) )s.push_back('1'); else s.push_back('0'); } reverse( s.begin(), s.end() );
Comments
Post a Comment