Formatted question description: https://leetcode.ca/all/600.html

600. Non-negative Integers without Consecutive Ones (Hard)

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 <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule. 

Note: 1 <= n <= 10⁹

Companies:
Pocket Gems

Related Topics:
Dynamic Programming

Solution 1.

Let f(n) be the numbers less than or equal to n whose binary representations DO contain consecutive ones.

x	binary(x)	has consecutive ones
0	0
1	1
2	10
3	11	1
4	100
5	101
6	110	1
7	111	1
8	1000
9	1001
10	1010
11	1011	1
12	1100	1
13	1101	1
14	1110	1
15	1111	1
16	10000

We can find pattern in this way:

1. We separate the table rows according to count of bits. So 0~1 is the first group, 2~3 is the second group, 4~7 is the third group, 8~15 is the forth group…
2. Starting from the second group, the numbers in the second half of the group all have consecutive ones, simply because they have leading 11.
3. For the numbers in the first half of the groups, the pattern is the same after removing the leading 10.
   Take 14 as example which is in group 8~15, it’s in the second half, so 12~14 all have consecutive ones. And 8~11 has the same pattern as 0~3.

So we can get this equation:

let k = floor(log2(n))
let p = 2^k
f(n) = f(p-1) +
       { f(n-p)                        if n-(p-1)<= p/2
       { n-(p-1)-p/2 + f(p/2-1)        if n-(p-1)>p/2

// OJ: https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/

// Time: O(logN)
// Space: O(logN)
class Solution {
private:
    unordered_map<int, int> m;
    int find(int num) {
        if (num < 2) return 0;
        if (m.find(num) != m.end()) return m[num];
        int k = log2(num), p = pow(2, k);
        int ans = find(p - 1);
        if (num > p / 2 * 3 - 1) ans += num - p / 2 * 3 + 1 + find(p / 2 - 1);
        else ans += find(num - p);
        return m[num] = ans;
    }
public:
    int findIntegers(int num) {
        return num + 1 - find(num);
    }
};

Java

class Solution {
    public int findIntegers(int num) {
        if (num <= 2)
            return num + 1;
        int bits = (int) (Math.log(num) / Math.log(2));
        int counts = 2;
        int zeros = 0, ones = 1;
        for (int i = 2; i <= bits; i++) {
            int newZeros = zeros + ones;
            ones = zeros;
            zeros = newZeros;
            counts += zeros;
            counts += ones;
        }
        int zerosUnrestricted = 0, zerosRestricted = 0, onesUnrestricted = 0, onesRestricted = 1;
        for (int i = 1; i <= bits; i++) {
            int curBit = (num >> bits - i) & 1;
            if (curBit == 0) {
                int curZerosUnrestricted = zerosUnrestricted + onesUnrestricted;
                int curZerosRestricted = zerosRestricted + onesRestricted;
                int curOnesUnrestricted = zerosUnrestricted;
                int curOnesRestricted = 0;
                zerosUnrestricted = curZerosUnrestricted;
                zerosRestricted = curZerosRestricted;
                onesUnrestricted = curOnesUnrestricted;
                onesRestricted = curOnesRestricted;
            } else {
                int curZerosUnrestricted = zerosUnrestricted + zerosRestricted + onesUnrestricted + onesRestricted;
                int curZerosRestricted = 0;
                int curOnesUnrestricted = zerosUnrestricted;
                int curOnesRestricted = zerosRestricted;
                zerosUnrestricted = curZerosUnrestricted;
                zerosRestricted = curZerosRestricted;
                onesUnrestricted = curOnesUnrestricted;
                onesRestricted = curOnesRestricted;
            }
        }
        counts += zerosUnrestricted + zerosRestricted + onesUnrestricted + onesRestricted;
        return counts;
    }
}

All Problems

All Solutions