#600 Non-negative Integers without Consecutive Ones - Solution

The key idea for #600 Non-negative Integers without Consecutive Ones is to analyze the binary representation of numbers. Instead of checking every integer up to n, we count how many valid binary strings of a given length do not contain consecutive 1s. This can be solved using a dynamic programming pattern similar to Fibonacci.

Let dp[i] represent the number of valid binary strings of length i without consecutive ones. A string ending with 0 can follow any valid string, while a string ending with 1 must follow one ending with 0. This leads to a recurrence similar to Fibonacci.

Traverse the bits of n from the most significant bit. When encountering a 1, add the number of valid combinations for the remaining bits using the precomputed DP values. If two consecutive 1s appear, stop early since further numbers would violate the constraint. This approach efficiently counts valid integers without brute force.

Time Complexity: O(log n) since we process each bit once. Space Complexity: O(log n) for the DP array.

Approach	Time Complexity	Space Complexity
Binary Digit DP with Fibonacci Pattern	O(log n)	O(log n)
Brute Force Checking Each Number	O(n log n)	O(1)

Solutions (8)

Dynamic Programming Approach

This approach utilizes dynamic programming to count the number of non-negative integers without consecutive ones. By breaking down the problem, we can avoid redundant work by storing solutions to subproblems.

Time Complexity: O(1) since we iterate over a fixed number of bits (30 bits for int).

Space Complexity: O(1) for storing a constant size dp array.

C C++Java Python C#JavaScript

1class Solution {
2    public int findIntegers(int num) {
3        int[] dp = new int[31];
4        dp[

Explanation

The Java implementation employs a dp array to precompute the number of valid integers without consecutive ones up to 31 bits in length. The main loop evaluates the bits of num to accumulate the result while checking for consecutive ones.

Recursive with Memoization

In this approach, we tackle the problem recursively and use memoization to store and retrieve solutions to subproblems, thereby optimizing overlapping subproblem calculations.

Time Complexity: Generally O(log n), as the recursion iterates over each bit once.

Space Complexity: O(log n) due to the recursive call stack and memo storage.

C++Python

1#include <iostream>
2#include <vector>
3#include <unordered_map>
4using namespace std;
5
class Solution {
private:
    unordered_map<int, int> memo;

    int dfs(int pos, bool is_tight, bool prev_one, vector<int>& bits) {
        if (pos == -1) return 1;
        if (!is_tight && memo.count(pos * 2 + prev_one)) return memo[pos * 2 + prev_one];

        int limit = is_tight ? bits[pos] : 1;
        int res = 0;
        for (int i = 0; i <= limit; ++i) {
            if (prev_one && i == 1) continue;
            res += dfs(pos - 1, is_tight && i == bits[pos], i == 1, bits);
        }

        if (!is_tight) memo[pos * 2 + prev_one] = res;

        return res;
    }

public:
    int findIntegers(int num) {
        vector<int> bits;
        while (num) {
            bits.push_back(num & 1);
            num >>= 1;
        }
        return dfs(bits.size() - 1, true, false, bits);
    }
};

int main() {
    Solution sol;
    int n = 5;
    cout << sol.findIntegers(n) << endl;
    return 0;
}