Saturday, October 29, 2016

LeetCode OJ - Counting Bits

Problem:

Please find the problem here.

Analysis:

The key to this problem is that I found this self repeating pattern.

We start with 0,1 for [0,1]
Then we have 1,2 for [10,11]
Then we have 1,2,2,3 for [100,101,110,111]
And so on ...

Solution: 

Basically, we found that the $ 2^{n}+1 $ to $ 2^{n+1} $ is basically repeating $ 0 $ to $ 2^n $ because the only difference between the two sequences is the most significant bit. We can basically construct the answer using this simple trick.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/counting-bits/

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

using namespace std;

namespace _LEET_COUNTING_BITS
{
    class Solution
    {
    public:
        vector<int> countBits(int num)
        {
            vector<int> result;
            result.resize(num + 1);
            result[0] = 0;
            if (num == 0)
            {
                return result;
            }
            result[1] = 1;
            int i = 0;
            int j = 2;
            int b = 1;
            while (true)
            {
                for (i = 0; i < j; i++)
                {
                    if (i + j > num)
                    {
                        break;
                    }
                    result[i + j] = result[i] + b;
                }
                if (i + j > num)
                {
                    break;
                }
                j = i + j;
            }

            return result;
        }
    };
};

using namespace _LEET_COUNTING_BITS;

int LEET_COUNTING_BITS()
{
    Solution solution;
    vector<int> v = solution.countBits(13);
    for (int i = 0; i < 14; i++)
    {
        cout << v[i] << ", ";
    }
    cout << endl;
    return 0;
}

No comments :

Post a Comment