Gray Code

JavaView on GFG

Intuition

n-bit Gray code: i-th value = i XOR (i>>1). Or build iteratively: mirror and prefix with 0/1.

Algorithm

1Iterative: start with [0]. For each step i from 1 to n: for j from current.size-1 to 0, append current[j] | (1<<(i-1)).
2Or formula: for i in 0..2^n-1, gray[i] = i ^ (i>>1).

Example Walkthrough

Input: n=2

1.Step 0: [0]. Step 1: [0,1]. Step 2: [00,01,11,10] = [0,1,3,2].

Output: [0,1,3,2]

Common Pitfalls

•Successive values differ by exactly 1 bit. The XOR formula i^(i>>1) directly gives the i-th Gray code.

Gray Code.java

Java


// Approach: For each number i in [0, 2^n), compute Gray code as i XOR (i >> 1).
// Convert to binary string and left-pad with zeros to length n.
// Time: O(2^n * n) Space: O(2^n)
import java.util.*;

class Solution {

    public ArrayList<String> graycode(int n) {
        ArrayList<String> result = new ArrayList<>();

        for (int i = 0; i < (int) Math.pow(2, n); i++) {
            int xor = i ^ (i >> 1);
            String binStr = Integer.toBinaryString(xor);
            StringBuilder sb = new StringBuilder("");
            if (binStr.length() < n) {
                for (int j = 1; j <= n - binStr.length(); j++) {
                    sb.append("0");
                }
            }
            sb.append(binStr);
            result.add(sb.toString());
        }
        
        return result;
    }
}

Was this solution helpful?