600. Non-negative Integers without Consecutive Ones

Time: O(log n)

Space: O(log n)

Intuition

Digit DP: count binary numbers up to n with no two consecutive 1s. This relates to Fibonacci — valid k-bit numbers = Fib(k+2).

Algorithm

1Find binary representation of n.
2Use DP with states (position, tight, prev_bit).
3At each bit: if we can place 0 freely; if we can place 1 only if prev_bit is 0.

Common Pitfalls

•Handle the "tight" constraint carefully — when following the exact bits of n vs when we're already below n.

600.cs

// Approach: Digit DP on the binary representation — Fibonacci-like recurrences
// zero[i]/one[i] count valid i-bit endings; subtract over-counts above num.
// Time: O(log n) Space: O(log n)

public class Solution
{
    public int FindIntegers(int num)
    {
        StringBuilder bits = new StringBuilder();
        for (; num > 0; num >>= 1)
            bits.Append(num & 1);

        int n = bits.Length;
        int[] zero = new int[n];
        int[] one = new int[n];

        zero[0] = 1;
        one[0] = 1;

        for (int i = 1; i < n; ++i)
        {
            zero[i] = zero[i - 1] + one[i - 1];
            one[i] = zero[i - 1];
        }

        int ans = zero[n - 1] + one[n - 1];

        for (int i = n - 2; i >= 0; --i)
        {
            // The numbers > num and <= 2^n - 1 are invalid.
            if (bits[i] == '1' && bits[i + 1] == '1')
                break;
            if (bits[i] == '0' && bits[i + 1] == '0')
                ans -= one[i];
        }

        return ans;
    }
}

Was this solution helpful?