Skip to content

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:

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:

Input: n = 1
Output: 2

Example 3:

Input: n = 2
Output: 3

 

Constraints:

  • 1 <= n <= 109

Solutions

Solution 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def findIntegers(self, n: int) -> int:
        @cache
        def dfs(pos, pre, limit):
            if pos <= 0:
                return 1
            up = a[pos] if limit else 1
            ans = 0
            for i in range(up + 1):
                if pre == 1 and i == 1:
                    continue
                ans += dfs(pos - 1, i, limit and i == up)
            return ans

        a = [0] * 33
        l = 0
        while n:
            l += 1
            a[l] = n & 1
            n >>= 1
        return dfs(l, 0, True)

 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
36
class Solution {
    private int[] a = new int[33];
    private int[][] dp = new int[33][2];

    public int findIntegers(int n) {
        int len = 0;
        while (n > 0) {
            a[++len] = n & 1;
            n >>= 1;
        }
        for (var e : dp) {
            Arrays.fill(e, -1);
        }
        return dfs(len, 0, true);
    }

    private int dfs(int pos, int pre, boolean limit) {
        if (pos <= 0) {
            return 1;
        }
        if (!limit && dp[pos][pre] != -1) {
            return dp[pos][pre];
        }
        int up = limit ? a[pos] : 1;
        int ans = 0;
        for (int i = 0; i <= up; ++i) {
            if (!(pre == 1 && i == 1)) {
                ans += dfs(pos - 1, i, limit && i == up);
            }
        }
        if (!limit) {
            dp[pos][pre] = ans;
        }
        return ans;
    }
}

 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 a[33];
    int dp[33][2];

    int findIntegers(int n) {
        int len = 0;
        while (n) {
            a[++len] = n & 1;
            n >>= 1;
        }
        memset(dp, -1, sizeof dp);
        return dfs(len, 0, true);
    }

    int dfs(int pos, int pre, bool limit) {
        if (pos <= 0) {
            return 1;
        }
        if (!limit && dp[pos][pre] != -1) {
            return dp[pos][pre];
        }
        int ans = 0;
        int up = limit ? a[pos] : 1;
        for (int i = 0; i <= up; ++i) {
            if (!(pre == 1 && i == 1)) {
                ans += dfs(pos - 1, i, limit && i == up);
            }
        }
        if (!limit) {
            dp[pos][pre] = ans;
        }
        return ans;
    }
};

 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
36
37
func findIntegers(n int) int {
    a := make([]int, 33)
    dp := make([][2]int, 33)
    for i := range dp {
        dp[i] = [2]int{-1, -1}
    }
    l := 0
    for n > 0 {
        l++
        a[l] = n & 1
        n >>= 1
    }
    var dfs func(int, int, bool) int
    dfs = func(pos, pre int, limit bool) int {
        if pos <= 0 {
            return 1
        }
        if !limit && dp[pos][pre] != -1 {
            return dp[pos][pre]
        }
        up := 1
        if limit {
            up = a[pos]
        }
        ans := 0
        for i := 0; i <= up; i++ {
            if !(pre == 1 && i == 1) {
                ans += dfs(pos-1, i, limit && i == up)
            }
        }
        if !limit {
            dp[pos][pre] = ans
        }
        return ans
    }
    return dfs(l, 0, true)
}

Comments