600. Non-negative Integers without Consecutive Ones

Posted on Edited on In

600. Non-negative Integers without Consecutive Ones

Description

Given a positive integer n, return the number of the integers in the range [0, n] whose binary representations do not contain consecutive ones.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
Input: n = 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.

Example 2:

1
2
Input: n = 1
Output: 2

Example 3:

1
2
Input: n = 2
Output: 3

Constraints:

  • 1 <= n <= 10^9

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int n_, m;
    vector<vector<int>> dp;

    int findIntegers(int n) {
        n_ = n; m = __lg(n);
        dp.resize(m + 1, vector<int>(2, -1));
        int res = dfs(0, 0, true);
        return res;
    }

    int dfs(int index, int prev, bool isLimit) {
        if (index == m + 1) {
            return 1;
        }
        if (!isLimit && dp[index][prev] != -1) {
            return dp[index][prev];
        }
        // if there's other constraint on the digit, only modify the for loop
        // condition, don't modify up here
        int up = isLimit ? n_ >> (m - index) & 1 : 1;
        int res = 0;
        for (int i = 0; i <= up; i++) {
            if (prev && i) {
                continue;
            }
            res += dfs(index + 1, i, isLimit && i == up);
        }
        if (!isLimit) {
            dp[index][prev] = res;
        }
        return res;
    }
};