CodingGyan

Gray Code Sequence

medium Recursion and Backtracking

Problem

A Gray code lists all numbers from 0 to 2^n - 1 so that two neighbours differ in exactly one bit. Print one such list for n bits as decimal numbers, using this rule: the list for n bits is the list for n-1 bits, followed by the same list in reverse order with the bit 2^(n-1) added to each number. The list for 0 bits is just 0.

Constraints

  • 0 <= n <= 12

Examples

Input

2

Output

0 1 3 2

Solutions

Best approachTime O(2^n)Space O(2^n)

Reflecting a list keeps the neighbours different in one bit, and adding the top bit makes the two halves meet with a single changed bit. The closed formula i ^ (i >> 1) gives the same list without recursion.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Gray code list.
 * Input   : One integer n.
 * Output  : 2^n numbers.
 * Approach: Reflect and prefix.
 * Time    : O(2^n)
 * Space   : O(2^n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;
import java.util.Arrays;
import java.util.stream.Collectors;

public class Main {
        // Step 1: Base case. With 0 bits there is only the number 0.
        static int[] gray(int bits) {
            if (bits == 0) {
                return new int[] {0};
            }
            // Step 2: Solve the smaller problem first.
            int[] smaller = gray(bits - 1);
            int[] result = new int[smaller.length * 2];
            // Step 3: Copy the smaller list. Then add the same list in reverse order with the new top bit set.
            for (int i = 0; i < smaller.length; i++) {
                result[i] = smaller[i];
                result[result.length - 1 - i] = smaller[i] + (1 << (bits - 1));
            }
            return result;
        }

    // This method solves the task. It receives the input and returns the answer.
    static int[] solve(long n) {
        return gray((int) n);
    }

    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        System.out.println(Arrays.stream(solve(n)).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
    }
}
Hints (1)
  1. Which bit differs between the last number of the first half and the first number of the second half?