Problem

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

Examples

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

Solution

Method 1 – Digit DP (Dynamic Programming on Bits)

Intuition

We count numbers without consecutive ones by building them bit by bit, using DP to avoid recomputation. For each bit, we decide to place 0 or 1, but only place 1 if the previous bit is 0. We also ensure we do not exceed n by tracking tight bounds.

Approach

  1. Precompute fib[i] where fib[i] is the number of valid binary numbers of length i (no consecutive ones). This follows Fibonacci because for each bit, we can place 0 (any previous) or 1 (only if previous is 0).
  2. Traverse the bits of n from highest to lowest:
    • If current bit is 1, add fib[i] to ans (all numbers with 0 at this bit and any valid below).
    • If two consecutive 1s are found, break (no more valid numbers above).
  3. Add 1 for n itself if it does not contain consecutive ones.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int findIntegers(int n) {
        int fib[32] = {1, 2};
        for (int i = 2; i < 32; ++i) fib[i] = fib[i-1] + fib[i-2];
        int ans = 0, prev = 0;
        for (int i = 30; i >= 0; --i) {
            if (n & (1 << i)) {
                ans += fib[i];
                if (prev) return ans;
                prev = 1;
            } else prev = 0;
        }
        return ans + 1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func findIntegers(n int) int {
    fib := [32]int{1, 2}
    for i := 2; i < 32; i++ {
        fib[i] = fib[i-1] + fib[i-2]
    }
    ans, prev := 0, 0
    for i := 30; i >= 0; i-- {
        if n&(1<<i) != 0 {
            ans += fib[i]
            if prev == 1 {
                return ans
            }
            prev = 1
        } else {
            prev = 0
        }
    }
    return ans + 1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int findIntegers(int n) {
        int[] fib = new int[32];
        fib[0] = 1; fib[1] = 2;
        for (int i = 2; i < 32; ++i) fib[i] = fib[i-1] + fib[i-2];
        int ans = 0, prev = 0;
        for (int i = 30; i >= 0; --i) {
            if ((n & (1 << i)) != 0) {
                ans += fib[i];
                if (prev == 1) return ans;
                prev = 1;
            } else prev = 0;
        }
        return ans + 1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun findIntegers(n: Int): Int {
        val fib = IntArray(32)
        fib[0] = 1; fib[1] = 2
        for (i in 2 until 32) fib[i] = fib[i-1] + fib[i-2]
        var ans = 0; var prev = 0
        for (i in 30 downTo 0) {
            if ((n shr i) and 1 == 1) {
                ans += fib[i]
                if (prev == 1) return ans
                prev = 1
            } else prev = 0
        }
        return ans + 1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def findIntegers(self, n: int) -> int:
        fib = [1, 2] + [0] * 30
        for i in range(2, 32):
            fib[i] = fib[i-1] + fib[i-2]
        ans = 0
        prev = 0
        for i in range(30, -1, -1):
            if n & (1 << i):
                ans += fib[i]
                if prev:
                    return ans
                prev = 1
            else:
                prev = 0
        return ans + 1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

impl Solution {
    pub fn find_integers(n: i32) -> i32 {
        let mut fib = [1, 2];
        fib.extend([0; 30]);
        for i in 2..32 {
            fib[i] = fib[i-1] + fib[i-2];
        }
        let mut ans = 0;
        let mut prev = 0;
        for i in (0..31).rev() {
            if (n & (1 << i)) != 0 {
                ans += fib[i];
                if prev == 1 {
                    return ans;
                }
                prev = 1;
            } else {
                prev = 0;
            }
        }
        ans + 1
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    findIntegers(n: number): number {
        const fib = [1, 2, ...Array(30).fill(0)];
        for (let i = 2; i < 32; ++i) fib[i] = fib[i-1] + fib[i-2];
        let ans = 0, prev = 0;
        for (let i = 30; i >= 0; --i) {
            if ((n & (1 << i)) !== 0) {
                ans += fib[i];
                if