<p>An <strong>n-bit gray code sequence</strong> is a sequence of <code>2<sup>n</sup></code> integers where:</p>

<ul>
	<li>Every integer is in the <strong>inclusive</strong> range <code>[0, 2<sup>n</sup> - 1]</code>,</li>
	<li>The first integer is <code>0</code>,</li>
	<li>An integer appears <strong>no more than once</strong> in the sequence,</li>
	<li>The binary representation of every pair of <strong>adjacent</strong> integers differs by <strong>exactly one bit</strong>, and</li>
	<li>The binary representation of the <strong>first</strong> and <strong>last</strong> integers differs by <strong>exactly one bit</strong>.</li>
</ul>

<p>Given an integer <code>n</code>, return <em>any valid <strong>n-bit gray code sequence</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 2
<strong>Output:</strong> [0,1,3,2]
<strong>Explanation:</strong>
The binary representation of [0,1,3,2] is [00,01,11,10].
- 0<u>0</u> and 0<u>1</u> differ by one bit
- <u>0</u>1 and <u>1</u>1 differ by one bit
- 1<u>1</u> and 1<u>0</u> differ by one bit
- <u>1</u>0 and <u>0</u>0 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
- <u>0</u>0 and <u>1</u>0 differ by one bit
- 1<u>0</u> and 1<u>1</u> differ by one bit
- <u>1</u>1 and <u>0</u>1 differ by one bit
- 0<u>1</u> and 0<u>0</u> differ by one bit
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> [0,1]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 16</code></li>
</ul>

from copy import deepcopy

class Solution:
    debugging = True

    def get_num_bits_diff(self, a: int, b: int) -> int:
        '''Return the number of bits that a and b differ by'''
        ab_xor = a ^ b
        if ab_xor == 0:
            return 0
        
        one_count = 0
        while ab_xor > 0:
            if ab_xor % 2 == 1:
                one_count += 1
            ab_xor = ab_xor >> 1
        return one_count

    def backtracking_approach(self, n: int) -> List[int]:
        '''Try backtracking until we get a valid sequence
        pg 53: the alternative is trying to inductively notice a pattern from small n'''
        first_gray_code_seen = []

        def recur(cur_sequence: List[int], visited: List[bool]) -> bool:
            if self.debugging:
                print(f'{cur_sequence=}')
            if len(cur_sequence) == 2**n:
                first_last_bit_diff = self.get_num_bits_diff(cur_sequence[0], cur_sequence[-1])
                if first_last_bit_diff == 1:
                    if self.debugging:
                        print(f'\tis a Gray code')
                    first_gray_code_seen.extend(cur_sequence)
                    return True
                else:
                    if self.debugging:
                        print(f'\tnot a Gray code because {first_last_bit_diff=}')
            
            for i in range(2**n):
                if visited[i]:
                    continue
                bit_diff_w_last = self.get_num_bits_diff(i, cur_sequence[-1])
                if bit_diff_w_last != 1:
                    continue
                
                visited[i] = True  # Try adding i to the sequence
                found_gray_code = recur(cur_sequence + [i], visited)
                if found_gray_code:
                    return True
                visited[i] = False  # If we get here, then this branch didn't work
            
            if self.debugging:
                print(f'\tfailed to lead to any Gray codes')
            return False  # None of the possibilities worked

        recur([0], [True if i == 0 else False for i in range(2**n)])
        return first_gray_code_seen

    def check(self, gray_code: List[int]):
        '''For debugging purposes, check bit diffs between the output of the above function
        Don't forget to check bit diff between the first and the last'''
        bit_diffs = []
        for i in range(1, len(gray_code)):
            bit_diffs.append(self.get_num_bits_diff(gray_code[i], gray_code[i-1]))
        bit_diffs.append(self.get_num_bits_diff(gray_code[0], gray_code[-1]))
        print(f'{bit_diffs=}')

    def reverse_and_prepend(self, n: int) -> List[List[int]]:
        '''Much faster method to generate an n-bit Gray code:
        Take the n-1 bit Gray code, append a reversed version of it
        Then, prepend 0 to the original half, 1 to the reversed half'''
        cur_gray_code = [[0], [1]]
        for i in range(2, n+1):
            half_to_append = deepcopy(list(reversed(cur_gray_code)))
            for h in half_to_append:
                h.append(1)
            for c in cur_gray_code:
                c.append(0)
            cur_gray_code.extend(half_to_append)
            if self.debugging:
                print(f'{i=}, {cur_gray_code=}')
        return cur_gray_code

    
    def reversed_binary_to_int(self, reversed_digits: List[int]) -> int:
        '''Convert binary number (given as least-to-most significant digits) to an int'''
        int_repr = 0
        for i in range(len(reversed_digits)):
            int_repr += reversed_digits[i] * 2**(i)
        return int_repr


    def grayCode(self, n: int) -> List[int]:
        self.debugging = False
        # return self.backtracking_approach(n)
        reversed_gray_code_bits = self.reverse_and_prepend(n)
        return [self.reversed_binary_to_int(bits) for bits in reversed_gray_code_bits]
33400