Non Negative Integers Without Consecutive Ones - Leetcode Solution

The Non Negative Integers Without Consecutive Ones problem on Leetcode asks us to find the number of non-negative integers that can be represented by a binary number without consecutive ones.

Let's take an example to understand the problem statement: Suppose we have a binary number with n bits. We need to find out how many non-negative integers can be represented by this binary number so that no two consecutive bits are equal to 1.

For example, if n = 3, we can represent the following 4 non-negative integers:

• 0 = 000
• 1 = 001
• 2 = 010
• 4 = 100

We cannot represent the following non-negative integers because they contain consecutive ones:

• 3 = 011
• 5 = 101
• 6 = 110
• 7 = 111

To solve the problem, we can use dynamic programming. Let f(i) be the number of non-negative integers that can be represented by a binary number with i bits so that no two consecutive bits are equal to 1.

If we have a binary number with i bits, we can determine the last digit of the number in two ways:

• If the last digit is 0, we can use any binary number with i-1 bits that follows the rule (no consecutive ones)
• If the last digit is 1, we must have a 0 before it. We can use any binary number with i-2 bits that follows the rule.

Therefore, we can write the following recurrence relation:

f(i) = f(i-1) + f(i-2)

To calculate the value of f(i), we can start with base cases:

• f(0) = 1, because there is only one way to represent 0 with 0 bits (i.e., an empty string)
• f(1) = 2, because we can represent 0 and 1 with 1 bit

We can then use the recurrence relation to calculate f(i) for larger values of i.

Once we have calculated f(n), we can use it to count the number of non-negative integers that can be represented by a binary number with n bits:

count = f(n)

This is because each binary number with n bits can be mapped to a non-negative integer, and each non-negative integer can be represented by a binary number with n bits.

The time complexity of this algorithm is O(n) and the space complexity is O(1) as we need only two variables to store f(i-1) and f(i-2) while calculating f(i).

1