Leetcode#89. Gray Code

Photo by Clark Tibbs on Unsplash

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

• Every integer is in the inclusive range [0, 2n - 1],
• The first integer is 0,
• An integer appears no more than once in the sequence,
• The binary representation of every pair of adjacent integers differs by exactly one bit, and
• The binary representation of the first and last integers differs by exactly one bit.

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

Example 1:

Input: n = 2
Output: [0,1,3,2]
Explanation:
The binary representation of [0,1,3,2] is [00,01,11,10].
- 00 and 01 differ by one bit
- 01 and 11 differ by one bit
- 11 and 10 differ by one bit
- 10 and 00 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
- 00 and 10 differ by one bit
- 10 and 11 differ by one bit
- 11 and 01 differ by one bit
- 01 and 00 differ by one bit

Example 2:

Input: n = 1
Output: [0,1]

Solution:

In gray code current number and previous number are only different by 1 bit in their binary representation.

“0” -> “1” -> “11” -> “10” -> “110” -> “111” -> “101” -> “100”

Can you see the pattern, every time when I am increasing number of bits I am adding 1 to the all previous bit representation in reverse order .

As you know adding 1 means multiplying the number by 2^(len-1), because “10(2)” -> “110(4+2=6)” -> “1110(“8+6”).

Conclusion:

If you want more like this please follow for more updates .

Comment your valuable thoughts or any suggestion about solution modification .