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 — Brute force (backtracking)

Intuition

Generate every binary string of length n and reject any sequence that contains 11 as a substring.

Approach

  • Recurse building the string one character at a time.
  • At each step, append 0 always; append 1 only if the previous character is not 1.
  • When length reaches n, count one valid string.

Code

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

class Solution {
 public:
  int findIntegers(int n) {
    return dfs(n, 0);
  }
 private:
  int dfs(int rem, int prev) {
    if (rem == 0) return 1;
    int ans = 0;
    ans += dfs(rem - 1, 0);          // place 0
    if (prev == 0) ans += dfs(rem - 1, 1); // place 1 only if previous was 0
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

package main

func findIntegers(n int) int {
    var dfs func(rem, prev int) int
    dfs = func(rem, prev int) int {
        if rem == 0 { return 1 }
        ans := 0
        ans += dfs(rem-1, 0)
        if prev == 0 { ans += dfs(rem-1, 1) }
        return ans
    }
    return dfs(n, 0)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
  public int findIntegers(int n) {
    return dfs(n, 0);
  }
  private int dfs(int rem, int prev) {
    if (rem == 0) return 1;
    int ans = 0;
    ans += dfs(rem - 1, 0);
    if (prev == 0) ans += dfs(rem - 1, 1);
    return ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def findIntegers(self, n: int) -> int:
        def dfs(rem: int, prev: int) -> int:
            if rem == 0:
                return 1
            ans = dfs(rem - 1, 0)
            if prev == 0:
                ans += dfs(rem - 1, 1)
            return ans
        return dfs(n, 0)

Complexity

  • ⏰ Time complexity: O(2^n), because the recursion explores all valid prefixes (worst-case close to 2^n).
  • 🧺 Space complexity: O(n), recursion stack.

Method 2 — Top-down DP (memoization)

Intuition

Many subproblems overlap: the count only depends on the remaining length rem and the previous bit prev. Cache results for (rem, prev) and reuse.

Approach

  • Define dp(rem, prev) = number of valid strings of length rem when previous bit is prev.
  • Recurrence: dp(rem, 0) = dp(rem-1, 0) + dp(rem-1, 1) (place 0 or 1), dp(rem, 1) = dp(rem-1, 0) (can only place 0).
  • Use memoization to compute each state once.

Code

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

class Solution {
 public:
  int findIntegers(int n) {
    memo.clear();
    return dp(n, 0);
  }
 private:
  std::map<std::pair<int,int>, int> memo;
  int dp(int rem, int prev) {
    auto key = std::make_pair(rem, prev);
    if (memo.count(key)) return memo[key];
    if (rem == 0) return 1;
    int ans = dp(rem - 1, 0);
    if (prev == 0) ans += dp(rem - 1, 1);
    memo[key] = ans;
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

package main

func countStringsMemo(n int) int {
    memo := make(map[[2]int]int)
    var dp func(rem, prev int) int
    dp = func(rem, prev int) int {
        key := [2]int{rem, prev}
        if v, ok := memo[key]; ok { return v }
        if rem == 0 { memo[key] = 1; return 1 }
        ans := dp(rem-1, 0)
        if prev == 0 { ans += dp(rem-1, 1) }
        memo[key] = ans
        return ans
    }
    return dp(n, 0)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import java.util.HashMap;
import java.util.Map;

class Solution {
  private final Map<String,Integer> memo = new HashMap<>();
  public int findIntegers(int n) {
    memo.clear();
    return dp(n, 0);
  }
  private int dp(int rem, int prev) {
    String k = rem + "," + prev;
    if (memo.containsKey(k)) return memo.get(k);
    if (rem == 0) return 1;
    int ans = dp(rem - 1, 0);
    if (prev == 0) ans += dp(rem - 1, 1);
    memo.put(k, ans);
    return ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

from functools import lru_cache

class Solution:
    def findIntegers(self, n: int) -> int:
        @lru_cache(None)
        def dp(rem: int, prev: int) -> int:
            if rem == 0:
                return 1
            ans = dp(rem - 1, 0)
            if prev == 0:
                ans += dp(rem - 1, 1)
            return ans
        return dp(n, 0)

Complexity

  • ⏰ Time complexity: O(n), each state (rem, prev) has only 2n possibilities and is computed once.
  • 🧺 Space complexity: O(n), for memoization and recursion stack.

Method 3 – Digit DP (iterative, Fibonacci-like)

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