online advertising

Friday, September 4, 2015

LeetCode OJ - Bitwise AND of Numbers Range

Problem:

Please find the problem here.

Solution:

Had fun with Zhicheng on this problem.

The basic idea is that for each bit, the 0 and 1 change in a pretty simple pattern. For a particular bit, if the bitwise AND is 1, then it is impossible for a '0' to be there.

For there to be 0s, there are three possible casees

It starts with 1, end with 1, but there is 0 inside,
Or it starts with 0,
Or it ends with 0.

It is fairly easy to check the last two, so the key problem is, is it possible to have 0 inside if it starts with 1 and then ends with 1, turn out there is a simple range check that can do the job.

So here is the code.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/bitwise-and-of-numbers-range/

#include "LEET_BITWISE_AND_OF_NUMBERS_RANGE.h"
#include <stack>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_BITWISE_AND_OF_NUMBERS_RANGE
{
    class Solution {
    private:
        bool oneOnly(int m, int n, int d, int mask)
        {
            if ((n - m + 1) > mask)
            {
                return false;
            }
            else
            {
                int m_masked = m & mask;
                int n_masked = n & mask;
                return (m_masked != 0 && n_masked != 0);
            }
        }
    public:
        int rangeBitwiseAnd(int m, int n)
        {
            int result = 0;
            int mask = 1;
            for (int d = 0; d < 32; d++)
            {
                if (oneOnly(m, n, d, mask))
                {
                    result += mask;
                }
                mask = mask << 1;
            }
            return result;
        }
    };
};

using namespace _LEET_BITWISE_AND_OF_NUMBERS_RANGE;

int LEET_BITWISE_AND_OF_NUMBERS_RANGE()
{
    Solution solution;
    cout << (solution.rangeBitwiseAnd(0, 0) == 0) << endl;
    cout << (solution.rangeBitwiseAnd(1, 1) == 1) << endl;
    cout << (solution.rangeBitwiseAnd(5, 7) == 4) << endl;
    return 0;
}

No comments :

Post a Comment