Day 1: Gray Code

In this article, let's discuss an amazing LeetCode problem.

ยท

4 min read

Hello coder! This is the first post of Let's LeetCode July Series, and we are going to solve the first exciting problem of the month, which is: Gray Code. (looks black here LOL ;)

This is a medium - level question on LeetCode, which is quite easy to solve, if you know to do some magic.

Excited know what it is? Great! Continue reading.

What does the Problem say?

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

  • Every integer belongs to the range [0, 2^n - 1]
  • The first integer is 0
  • Integers are not repeated 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

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

The problem basically says that we need to form a sequence of numbers from 0 to 2^n - 1, such that the adjacent numbers, as well as the first and the last numbers should have only 1 bit difference.

Example

Test case 1: n = 1

The numbers are ranging from [0...2^1 - 1] = [0, 1]. The binary representations will be:

0 => 0000

1 => 0001

From this highlighted example, 0 and 1 differ by one bit. So, [0, 1] can be a possible solution.

Test case 2: n = 2

The numbers are ranging from: [0...2^2 - 1] = [0...3]. The binary representations will be: 0 => 0000

1 => 0001

2 => 0010

3 => 0011

From this example, 0 and 1, 0 and 2, 2 and 3 differ by 1 bit. So the possible answer could be [0, 1, 3, 2], or [0, 2, 3, 1].

Quite complicated Test case 3: n = 3

The numbers are ranging from: [0...2^3 - 1] = [0...7]. The binary representations will be:

0 => 0000

1 => 0001

2 => 0010

3 => 0011

4 => 0100

5 => 0101

6 => 0110

7 => 0111

From the highlighted bits, we can see that the pair of numbers with 1 bit difference are: (0, 1), (0, 2), (0, 4), (1, 2) and so on.

Try to find the other pair of numbers too!

The possible answer here could be: [0, 1, 3, 2, 6, 7, 5, 4].

Check whether this solution satisfies the problem statement.

How to Solve?

This problem could be easily solved using Bit Manipulation. Buckle yourself up to become magicians!

FYI; Bit manipulation is way too exciting than the magic that you would have ever seen!

Magic # 1: Any number when divided by 2, it gets shifted by 1 bit.

For example: 2 is represented as 0010 in binary. If you divide it by 2, it becomes 1, which is 0001 in binary.

Could you notice the bit shift, the change in the position of 1?

One more example for you:

3 => 0011

3/2 = 1 => 0001

Notice that I'm taking the floor value of the quotient.

Magic # 2: If you XOR the values, it gives the numbers with 1 bit difference of the previous number.

If you want to know what is XOR, checkout this link.

Example:

0 ^ (0/2) = 0 = 0000

1 ^ (1/2) = 1 ^ 0 = 1 = 0001

2 ^ (2/2) = 2 ^ 1 = 3 = 0011

3 ^ (3/2) = 3 ^ 1 = 2 = 0010

4 ^ (4/2) = 4 ^ 2 = 6 = 0110

Now, let's see how we figure out the solution of this problem using C++ code.

P. S.

Now that you have learnt the tricks, try to do the problem by yourself first. You can try out this amazing problem in LeetCode, by clicking here .

C++ Solution

vector<int> grayCode(int n) {
        int x = 0;
        vector<int> ans;
        for(int i = 0; i < (1 << n); ++i) {
            x = i ^ (i / 2) ;
            ans.push_back(x);
        } return ans;
    }

Walkthrough

The function takes a single integer n as input. Since we have to return a list of integers, I am taking it in the form of a vector.

For each integer i from 0 to 2^n - 1, I'm finding the value of i ^ (i/2), and inserting into the vector.

Note that 1 << n is the faster form of 2^n. (Magic # 3)

Finally, I'm returning the vector I have formed.

That's it!

Thanks for your patient reading. Hope you learnt something new, some cool magic tricks and hacks to flaunt yourself! If you really found this article interesting and want me to discuss more amazing problems like this, do give this article a ๐Ÿ‘ and support me!

Happy (Leet)Coding!

mgn

ย