Non negative integers without consecutive ones

Dynamic Programming

41.7% acceptance

Jan 13, 2026

1622

138

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

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn find_integers(n: i32) -> i32 {
    let mut fib = [0i32; 32];
    fib[0] = 1; fib[1] = 2;
    for i in 2..32 { fib[i] = fib[i-1] + fib[i-2]; }
    let mut count = 0;
    let mut prev_bit = 0;
    for i in (0..31).rev() {
      if n & (1 << i) != 0 {
        count += fib[i];
        if prev_bit == 1 { return count; }
        prev_bit = 1;
      } else { prev_bit = 0; }
    }
    count + 1
  }
}