Non-negative Integers without Consecutive Ones

hard dp bit manipulation

Problem

Count integers in [0, n] whose binary representation has no two adjacent 1s.

Inputn = 5

Output5

Valid: 0,1,2,4,5 (skipping 3 = 11₂).

input

def find_integers(n):
    fib = [1, 2]
    for _ in range(30): fib.append(fib[-1] + fib[-2])
    ans, prev = 0, 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

function findIntegers(n) {
  const fib = [1, 2]; while (fib.length < 32) fib.push(fib[fib.length-1] + fib[fib.length-2]);
  let ans = 0, prev = 0;
  for (let i = 30; i >= 0; i--) {
    if (n & (1 << i)) {
      ans += fib[i];
      if (prev) return ans;
      prev = 1;
    } else prev = 0;
  }
  return ans + 1;
}

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;
}

int findIntegers(int n) {
    vector fib(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)) {
            ans += fib[i];
            if (prev) return ans;
            prev = 1;
        } else prev = 0;
    }
    return ans + 1;
}

Explanation

We need to count numbers in [0, n] whose binary form has no two 1s next to each other. The beautiful fact is that the count of valid bit patterns of a given length follows the Fibonacci numbers, so we precompute a small fib table and walk the bits of n from the highest down to the lowest.

Here fib[i] counts how many ways the lower i bits can be filled with no adjacent 1s when the bit just above them is 0. Whenever we hit a set bit (a 1) at position i in n, we can instead put a 0 there and freely fill the remaining i bits — that adds fib[i] valid numbers that are guaranteed below n.

The catch is consecutive ones in n itself. We track the previous bit with prev. If we meet two 1s in a row, then no number can keep matching n's prefix any further, so we return the accumulated ans immediately.

If we make it through every bit without two adjacent ones, then n is itself valid and we add 1 at the end.

Example: n = 5 is 101 in binary. The valid numbers are 0, 1, 2, 4, 5 — we skip 3 = 11 — for a total of 5. Since we only touch about 30 bits, this runs in O(log n).

Time: O(log n) Space: O(log n)