Problem Description

Given a non-negative integer n, count how many non-negative integers less than or equal to n have binary representations that do not contain consecutive ones. In other words, for each integer x such that 0 ≤ x ≤ n, its binary form should not have two or more adjacent '1's.

Constraints:

• 0 ≤ n ≤ 10^9
• Each valid integer can be used only once in the count.
• Each solution must be unique; do not count duplicates.

Thought Process

At first glance, one might consider iterating through every number from 0 to n and checking if its binary representation has consecutive ones. This brute-force approach is straightforward, but it's inefficient for large values of n (up to a billion).

To optimize, we need to avoid checking every number individually. The key insight is to use properties of binary numbers and dynamic programming. If we can count, for any given number of bits, how many numbers do not have consecutive ones, we can build up the answer efficiently. This problem is closely related to the Fibonacci sequence, as the number of valid binary strings of length k without consecutive ones follows a similar recurrence.

Solution Approach

We'll use a dynamic programming approach, leveraging the relationship between the problem and the Fibonacci sequence. Here's how the algorithm works:

1. Precompute Fibonacci Numbers:
   • Let fib[i] be the number of valid binary strings of length i (without consecutive ones).
   • The recurrence is: fib[i] = fib[i-1] + fib[i-2] (either start with '0' and any valid string of length i-1, or with '10' and any valid string of length i-2).
2. Process Bits from Most Significant to Least:
   • Iterate over the bits of n from highest to lowest.
   • If the current bit is '1', add fib[position] to the answer (since all numbers with a '0' at this position and any valid combination below are less than the current prefix).
   • If two consecutive '1's are encountered, stop—the rest would contain consecutive ones.
3. Include n if Valid:
   • After processing, check if n itself has no consecutive ones. If so, increment the answer by 1.

This approach efficiently counts valid numbers without iterating through all possibilities.

Example Walkthrough

Let's take n = 5 (binary: 101).

1. Compute Fibonacci:
   • We need up to 3 bits (since 5 in binary is 3 digits): fib = [1, 2, 3, 5]
2. Process bits:
   • Bit 2 (value 4): '1' → add fib[2] = 3 to answer (for numbers 0xx, 1xx where xx are valid).
   • Bit 1 (value 2): '0' → move on.
   • Bit 0 (value 1): '1' → add fib[0] = 1 to answer.
   • No consecutive ones encountered.
3. Check if n is valid:
   • 5 (101) has no consecutive ones, so add 1.
4. Total: 3 (from first '1') + 1 (from last '1') + 1 (n itself) = 5.
5. Valid numbers: 0 (0), 1 (1), 2 (10), 4 (100), 5 (101).

Time and Space Complexity

• Brute-force approach:
  • Time: O(n \cdot k), where k is the number of bits (checking each number up to n).
  • Space: O(1) (no extra storage needed except for counters).
• Optimized DP approach:
  • Time: O(k), where k is the number of bits in n (since we process each bit once).
  • Space: O(k) for the Fibonacci array.

The optimized approach is feasible for large n (up to 10⁹).

Summary

This problem leverages bitwise properties and dynamic programming to efficiently count all non-negative integers up to n whose binary representations do not contain consecutive ones. By transforming the problem into counting valid binary strings and using the Fibonacci sequence, we avoid brute-force enumeration and achieve a fast, elegant solution.

Code Implementation

class Solution:
    def findIntegers(self, n: int) -> int:
        # Precompute Fibonacci numbers
        fib = [1, 2]
        for i in range(2, 32):
            fib.append(fib[-1] + fib[-2])
        
        ans = 0
        prev_bit = 0
        for i in range(30, -1, -1):
            if (n & (1 << i)):
                ans += fib[i]
                if prev_bit == 1:
                    return ans
                prev_bit = 1
            else:
                prev_bit = 0
        return ans + 1
      

class Solution {
public:
    int findIntegers(int n) {
        vector<int> fib(32, 0);
        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_bit = 0;
        for (int i = 30; i >= 0; --i) {
            if (n & (1 << i)) {
                ans += fib[i];
                if (prev_bit)
                    return ans;
                prev_bit = 1;
            } else {
                prev_bit = 0;
            }
        }
        return ans + 1;
    }
};
      

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, prevBit = 0;
        for (int i = 30; i >= 0; --i) {
            if ((n & (1 << i)) != 0) {
                ans += fib[i];
                if (prevBit == 1)
                    return ans;
                prevBit = 1;
            } else {
                prevBit = 0;
            }
        }
        return ans + 1;
    }
}
      

var findIntegers = function(n) {
    let fib = [1, 2];
    for (let i = 2; i < 32; ++i) {
        fib[i] = fib[i-1] + fib[i-2];
    }
    let ans = 0, prevBit = 0;
    for (let i = 30; i >= 0; --i) {
        if ((n & (1 << i)) !== 0) {
            ans += fib[i];
            if (prevBit === 1)
                return ans;
            prevBit = 1;
        } else {
            prevBit = 0;
        }
    }
    return ans + 1;
};