Monday, September 21, 2015

LeetCode OJ - Gray Code

Problem:

Please find the problem here.

Solution:

First, let's define the gray code used in this problem. It is binary reflection gray code.

We start with the obvious gray code for 0 and 1

0: 0
1: 1

Now if we want to find the gray code for 2 and 3, we first zero pad the 0 and 1 gray code as follow

0: 00
1: 01

Next, we reflect them as if there is a reflection axis in the bottom of the list (you can see the reflection axis)

0: 00
1: 01
=====
1: 01
0: 00

Next, set the MSB on in the lower part, that would be the gray code!

0: 00
1: 01
2: 11
3: 10

The process can be repeated, and therefore define the gray code for 4 - 7 as follow

0: 000
1: 001
2: 011
3: 010
4: 110
5: 111
6: 101
7: 100

All right, now we have the definition of the gray code. Now we will proceed to prove an interesting formula.

gray(i) = (i >> 1) ^ i

Let $ S(n) $ be the statement that the formula is correct for all $ i \le 2^n - 1 $, it is obvious that it is true for $ n = 2 $.

Assuming $ S(i) $ is true for all $ i \le k $, for $ S(k) $, we need to find the gray code of some number in the range $ 2^{k -1} \le x \le 2^{k} $.

In this case, the MSB is 1, and according to the formula, the MSB is 1, and the gray code should be 1, that's good.

For the rest of the bit, the fun happens. To find the 'reflected' number of x, it is $ 2^{k} - 1 - x $. The former is just a sequence of 1 in binary, so the reflection is simply flipping all bits.

Now we flip all the bits, the xor does not change. So by the induction hypothesis, we get the right gray code!

Code:

#include "stdafx.h"

// https://leetcode.com/problems/gray-code/

#include "LEET_GRAY_CODE.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

namespace _LEET_GRAY_CODE
{
    class Solution
    {
    public:
        vector<int> grayCode(int n)
        {
            unsigned int size = 1 << n;
            vector<int> solution;
            solution.resize(size);
            for (unsigned int i = 0; i < size; i++)
            {
                /*
                 * The fun of this exercies reside in the proof of this formula
                 * The key idea is that the 'mirror' image of a number is the 2^n - 1 - x
                 * 2^n is a bit sequence of all 1, so the subtraction is simply flipping all bits
                 * and if you flip all the bits of both operand of xor, the result is unchanged.
                 */
                solution[i] = (i >> 1) ^ i;
            }
            return solution;
        }
    };
};

using namespace _LEET_GRAY_CODE;

int LEET_GRAY_CODE()
{
    Solution s;
    vector<int> gray = s.grayCode(4);
    for (unsigned int i = 0; i < gray.size(); i++)
    {
        cout << gray[i] << endl;
    }
    return 0;
}

No comments :

Post a Comment