Problem Statement

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

• Every integer is in the inclusive range [0, 2n - 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:

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 and11 differ by one bit
- 11 and 10 differ by one bit
-10 and00 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
-00 and10 differ by one bit
- 10 and 11 differ by one bit
-11 and01 differ by one bit
- 01 and 00 differ by one bit

Example 2:

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

Constraints:

• 1 <= n <= 16

Problem Link

Gray Code - LeetCode

Reference Video

https://www.youtube.com/watch?v=KOD2BFauQbA

Code

class Solution {
public:
    vector<int> grayCode(int n) {
        
        vector<string> vec = grayCodeInBase2(n);
        
        vector<int> ans;
        
        for(string str:vec)
        {
            int temp = 0;
            for(int i=0;i<str.size();i++)
            {
                if(str[i]=='1')
                {
                    temp+=(pow(2,n-i-1));
                }
            }
            ans.push_back(temp);
        }
        
        return ans;
        
    }
    
    vector<string> grayCodeInBase2(int n)
    {
        
        if(n==1)
        {
            vector<string> bres;
            bres.push_back("0");
            bres.push_back("1");
            return bres;
        }
        
        vector<string> res = grayCodeInBase2(n-1);
        vector<string> ans;
        
        for(int i=0;i<res.size();i++)
        {
            ans.push_back("0"+res[i]);
        }
        
        for(int i=res.size()-1;i>=0;i--)
        {
            ans.push_back("1"+res[i]);
        }
        
        return ans;
    }
};