LeetCode 600: Non-negative Integers without Consecutive Ones Solution

Master LeetCode problem 600 (Non-negative Integers without Consecutive Ones), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

600. Non-negative Integers without Consecutive Ones

Hard

Dynamic Programming

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We can keep track of the count of numbers without consecutive ones up to a certain length of binary representation. We can then build up the count iteratively until we reach the given number n.

We can use two arrays, endWithZero and endWithOne, to keep track of the count of numbers that end with 0 and 1 respectively, for each length of binary representation. At each step, we calculate the count of numbers without consecutive ones for the next length based on the counts for the previous length.

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

Solution Code

class Solution {
    public int findIntegers(int n) {
        int[] endWithZero = new int[32];
        int[] endWithOne = new int[32];
        endWithZero[0] = 1;
        endWithOne[0] = 1;
        
        for (int i = 1; i < 32; i++) {
            endWithZero[i] = endWithZero[i-1] + endWithOne[i-1];
            endWithOne[i] = endWithZero[i-1];
        }
        
        int result = 0;
        int prevBit = 0;
        
        for (int i = 30; i >= 0; i--) {
            int bit = (n >> i) & 1;
            if (bit == 1) {
                result += endWithZero[i];
            }
            
            if (prevBit == 1 && bit == 1) {
                break;
            }
            
            prevBit = bit;
            
            if (i == 0) {
                result++;
            }
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 600 (Non-negative Integers without Consecutive Ones)?

This page provides optimized solutions for LeetCode problem 600 (Non-negative Integers without Consecutive Ones) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 600 (Non-negative Integers without Consecutive Ones)?

The time complexity for LeetCode 600 (Non-negative Integers without Consecutive Ones) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 600 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 600 in Java, C++, or Python.

Back to LeetCode Solutions