Problem Statement

Given a positive integer n, return any valid n-bit gray code sequence.

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

• Each integer is in the inclusive range [0, 2ⁿ - 1].
• Sequence always starts with 0.
• All integers are unique in the sequence.
• The binary representation of every pair of adjacent integers differs by exactly one bit.
• The binary representation of the first and last integers differs by exactly one bit.

Examples

• Example 1

  • Input: n = 4
  • Expected Output: [0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]
  • Justification: This sequence starts at 0 and each subsequent number differs from the previous one by exactly one bit. The sequence covers all numbers from 0 to 15 (which is 2^4 - 1), adhering to the Gray Code property. It also ensures that the first and last numbers (0 and 8) differ by only one bit.

• Example 2

  • Input: n = 1
  • Expected Output: [0, 1]
  • Justification: With a single bit, the sequence can only be [0, 1], as both numbers differ by exactly one bit, and the sequence starts with 0.

• Example 3

  • Input: n = 3
  • Expected Output: [0, 1, 3, 2, 6, 7, 5, 4]
  • Justification: This sequence for 3 bits starts at 0, and each subsequent number differs from the previous by exactly one bit. Additionally, the first and last numbers (0 and 4) differ by only one bit, satisfying all the conditions of Gray Code.

Try it yourself

Try solving this question here: