Medium 0 solved 0% acceptance

Gray Code

List the n-bit reflected binary Gray code, where neighbors differ in exactly one bit.

What you'll learn

  • Compute a Gray code with XOR and shift
  • Generate 2^n values
  • Check that neighbors differ in one bit

Problem

In a Gray code sequence each value differs from the previous one in exactly one bit. The standard (reflected binary) Gray code of i is i XOR (i >> 1): for 2 bits the sequence is 0, 1, 3, 2, which is 00, 01, 11, 10 in binary. Rotary encoders use it so that a reading taken between two positions is never wildly wrong.

Implement gray_code(n).

Input

n: The number of bits.

Output

Return the 2^n values of the reflected binary Gray code in order, as integers, starting with 0. For n = 0 return [0].

Constraints

0 ≤ n ≤ 16

Examples

Example 1
Input:
n = 2

Expected output:
expected = [0, 1, 3, 2]
Input:
long long n = 2;

Expected output:
std::vector<long long> expected = {0, 1, 3, 2};
Input:
long n = 2;

Expected output:
long[] expected = new long[] {0, 1, 3, 2};

Explanation

In binary the sequence is 00, 01, 11, 10, so the answer is [0, 1, 3, 2].

Example 2
Input:
n = 3

Expected output:
expected = [0, 1, 3, 2, 6, 7, 5, 4]
Input:
long long n = 3;

Expected output:
std::vector<long long> expected = {0, 1, 3, 2, 6, 7, 5, 4};
Input:
long n = 3;

Expected output:
long[] expected = new long[] {0, 1, 3, 2, 6, 7, 5, 4};

Explanation

Each value is i XOR (i >> 1) for i = 0 to 7: [0, 1, 3, 2, 6, 7, 5, 4].

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

Loop i from 0 to 2^n − 1.

Hint 2

Each Gray code value comes from i and i shifted right by one.

Hint 3

For n = 0 the loop runs once and gives [0].

Expected complexity

O(2^n) time, O(2^n) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.