Generate n-bit Gray Codes

Given a number n, generate bit patterns from 0 to 2^(n-1) such that successive patterns differ by one bit.

Examples:

Input: n = 2
Output: 00 01 11 10
Explanation: We begin with all 0s, and then add the smallest next number that has only one bit difference, we keep adding this way to generate the full sequence.

Input: n = 3
Output: 000 001 011 010 110 111 101 100

Try it on GfG Practice

Table of Content

Using Reflection Method
Using Bit Manipulation

Using Reflection Method

The idea is based on the fact that n bit Gray codes can be generated using (n-1) bit Gray codes. We start with the 1 bit Gray code, which is {0, 1}.

How to generate n bit Gray code from (n-1) Gray codes?

Take (n−1) bit Gray code
Copy it in reverse
Prefix 0 to original list and prefix 1 to reversed list
Concatenate the two lists generated in the previous step and we have the n bit Gray code.

Why does this work?

Since we create two lists of same size as n-1 bit Gray codes, the count of n bit Gray codes is double of the (n-1) bit Gray codes.
Prefix 0 and 1 ensures that the first half starts with 0 and second half starts with 1. So no overlap between halves
Since we reverse the second half before prefixing with 1, the end of first list and first of second list were same before appending. After concatenating two lists, these two elements only differ by first bit.

C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<string> grayCode(int n) {
    vector<string> res;
    
    // base case
    res.push_back("0");
    res.push_back("1");

    for (int i = 2; i <= n; i++) {
        int size = res.size();

        // reverse and append
        for (int j = size - 1; j >= 0; j--) {
            res.push_back(res[j]);
        }

        // add '0' to first half
        for (int j = 0; j < size; j++) {
            res[j] = "0" + res[j];
        }

        // add '1' to second half
        for (int j = size; j < 2 * size; j++) {
            res[j] = "1" + res[j];
        }
    }

    return res;
}

int main() {
    int n = 3;
    vector<string> result = grayCode(n);

    for (string s : result) {
        cout << s << " ";
    }
    return 0;
}

Java

import java.util.ArrayList;
import java.util.List;

class GFG {
    public static List<String> grayCode(int n) {
        List<String> res = new ArrayList<>();
        
        res.add("0");
        res.add("1");

        for (int i = 2; i <= n; i++) {
            int size = res.size();

            // reverse and append
            for (int j = size - 1; j >= 0; j--) {
                res.add(res.get(j));
            }

            // prefix '0'
            for (int j = 0; j < size; j++) {
                res.set(j, "0" + res.get(j));
            }

            // prefix '1'
            for (int j = size; j < 2 * size; j++) {
                res.set(j, "1" + res.get(j));
            }
        }

        return res;
    }

    public static void main(String[] args) {
        int n = 3;
        List<String> result = grayCode(n);

        for (String s : result) {
            System.out.print(s + " ");
        }
    }
}

Python

def gray_code(n):
    res = ["0", "1"]

    for i in range(2, n + 1):
        size = len(res)

        # reverse and append
        res += res[::-1]

        # prefix '0'
        for j in range(size):
            res[j] = "0" + res[j]

        # prefix '1'
        for j in range(size, 2 * size):
            res[j] = "1" + res[j]

    return res

if __name__ == "__main__": 
    n = 3
    result = gray_code(n)

print(" ".join(result))

using System;
using System.Collections.Generic;

class GFG {
    static List<string> GrayCode(int n) {
        List<string> res = new List<string>();
        
        res.Add("0");
        res.Add("1");

        for (int i = 2; i <= n; i++) {
            int size = res.Count;

            // reverse and append
            for (int j = size - 1; j >= 0; j--) {
                res.Add(res[j]);
            }

            // prefix '0'
            for (int j = 0; j < size; j++) {
                res[j] = "0" + res[j];
            }

            // prefix '1'
            for (int j = size; j < 2 * size; j++) {
                res[j] = "1" + res[j];
            }
        }

        return res;
    }

    static void Main() {
        int n = 3;
        List<string> result = GrayCode(n);

        foreach (string s in result) {
            Console.Write(s + " ");
        }
    }
}

JavaScript

function grayCode(n) {
    let res = ["0", "1"];

    for (let i = 2; i <= n; i++) {
        let size = res.length;

        // reverse and append
        for (let j = size - 1; j >= 0; j--) {
            res.push(res[j]);
        }

        // prefix '0'
        for (let j = 0; j < size; j++) {
            res[j] = "0" + res[j];
        }

        // prefix '1'
        for (let j = size; j < 2 * size; j++) {
            res[j] = "1" + res[j];
        }
    }

    return res;
}

// Driver Code
let n = 3;
let result = grayCode(n);
console.log(result.join(" "));

Output

000 001 011 010 110 111 101 100

Time Complexity: O(n*(2^n))

Auxiliary Space: O(1), while the overall space complexity is O(n*(2^n)) to store the resulting Gray code sequence.

Using Bit Manipulation

We directly generate the i'th Gray Code using the formula Gray(i) = i XOR (i >> 1), we iterate from 0 to 2^(n - 1), apply this formula for each value, convert the result into an n-bit binary string, store it, and finally print the sequence.

Why does this formula work?

If we take a closer look at the formula,

When we do (i >> 1), all bits shift one position to the right, least significant bit is dropped and a 0 is inserted at the left.
When we do XOR of i with (i >> 1), all trailing flips cancel out in XOR
Only the first changing position survives

C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<string> generateGray(int n) {
    vector<string> res;

    for (int i = 0; i < (1 << n); i++) {
        
        // generate i-th Gray code
        int g = i ^ (i >> 1);

        // Convert the code to string
        string s = "";
        for (int j = n - 1; j >= 0; j--) {
            if (g & (1 << j))
                s += '1';
            else
                s += '0';
        }

        res.push_back(s);
    }

    return res;
}

int main() {
    int n = 3;
    vector<string> result = generateGray(n);

    for (string s : result) {
        cout << s << " ";
    }
    return 0;
}