600. Non-negative Integers without Consecutive Ones

• Difficulty: Hard

• Topics: Dynamic Programming

• Similar Questions:

  • House Robber

  • House Robber II

  • Ones and Zeroes

Problem:

Given a positive integer n, find the number of non-negative integers less than or equal to n, whose binary representations do NOT contain consecutive ones.

Example 1:

Input: 5
Output: 5
Explanation: 
Here are the non-negative integers <= 0="" 1="" 2="" 3="" 4="" 5="" 10="" 11="" 100="" 101="" with="" their="" corresponding="" binary="" representations:="" :="" among="" them,="" only="" integer="" disobeys="" the="" rule="" (two="" consecutive="" ones)="" and="" other="" satisfy="" rule.="" <="" pre="">

Note: 1 <= n="" <="10<sup">9

Solutions:

class Solution {
public:
    int findIntegers(int num) {
        unordered_map<int, int> cache;
        return helper(num, 31, cache);
    }

private:
    int helper(int num, int pos, unordered_map<int, int>& cache) {
        // cout << num << " " << pos << endl;
        if (cache.count(num))   return cache[num];
        if (pos < 0)  return 1;
        if ((num & (1 << pos)) == 0) {
            return helper(num, pos - 1, cache);
        }    

        if (pos == 0) {
            return 2;
        }

        if (pos == 1) {
            return 3;
        }

        int ret;
        int num1 = (1 << pos) - 1;
        int num2 = 
            ((num & (1 << (pos - 1))) == 0) ? num & (~(3 << (pos - 1))) : (1 << (pos - 1)) - 1;
        ret = helper(num1, pos - 1, cache) + helper(num2, pos - 2, cache);

        cache[num] = ret;
        return ret;
    }

};