Gray Code Problem


Description

LeetCode Problem 89.

An n-bit gray code sequence is a sequence of 2^n integers where:

  • Every integer is in the inclusive range [0, 2^n - 1],
  • The first integer is 0,
  • An integer appears no more than once in the sequence,
  • The binary representation of every pair of adjacent integers differs by exactly one bit, and
  • The binary representation of the first and last integers differs by exactly one bit.

Given an integer n, return any valid n-bit gray code sequence.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
Input: n = 2
Output: [0,1,3,2]
Explanation:
The binary representation of [0,1,3,2] is [00,01,11,10].
- 00 and 01 differ by one bit
- 01 and 11 differ by one bit
- 11 and 10 differ by one bit
- 10 and 00 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
- 00 and 10 differ by one bit
- 10 and 11 differ by one bit
- 11 and 01 differ by one bit
- 01 and 00 differ by one bit

Example 2:

1
2
Input: n = 1
Output: [0,1]

Constraints:

  • 1 <= n <= 16


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector<int> ans;
    
    int toDecimal(vector<int>& bin) {
        int dec = 0;
        for (int i = 0; i < bin.size(); i ++) {
            dec = (dec << 1) + bin[i];
        }
        return dec;
    }
    
    void backtrack(vector<int>& candidates, int idx) {
        if (idx == -1) {
            ans.push_back(toDecimal(candidates));
            return;
        }
        
        backtrack(candidates, idx-1);
        candidates[idx] = 1 - candidates[idx];
        backtrack(candidates, idx-1);
                
        
    }
    
    vector<int> grayCode(int n) {
        vector<int> candidates(n, 0);
        backtrack(candidates, n-1);
        return ans;
    }
};




Related Posts

Word Search Problem

LeetCode 79. Given an m x n grid of characters...

Subsets Problem

LeetCode 78. Given an integer array nums of unique elements,...

Subsets II Problem

LeetCode 90. Given an integer array nums that may contain...

Restore IP Addresses Problem

LeetCode 93. Given a string s containing only digits, return...

Gray Code Problem

LeetCode 89. Given an integer n, return any valid n-bit...

Combinations Problem

LeetCode 77. Given two integers n and k, return all...