Skip to main content

Non-negative Integers without Consecutive Ones

1. Problem Description​

Given a non-negative integer nn, find the number of non-negative integers less than or equal to nn that do not contain consecutive ones in their binary representation.

2. Examples​

Example 1:​

Input: n=5n = 5
Output: 55
Explanation:
There are five such numbers: 0, 1, 2, 4, 5.
Their binary representations are: 0 (0), 1 (1), 2 (10), 4 (100), 5 (101).

Example 2:​

Input: n=10n = 10
Output: 88 Explanation:
There are eight such numbers: 0, 1, 2, 4, 5, 8, 9, 10.
Their binary representations are: 0 (0), 1 (1), 2 (10), 4 (100), 5 (101), 8 (1000), 9 (1001), 10 (1010).

3. Constraints​

  • 0<=n<=1090 <= n <= 10^9

4. Algorithm​

Approach:​

The problem can be approached using dynamic programming. We need to count the numbers up to nn that do not have consecutive ones in their binary representation. This can be solved by considering the binary digits of nn.

  1. Initialize Variables:

    • dp0[i]dp0[i]: Number of valid integers of length ii ending with 00.
    • dp1[i]dp1[i]: Number of valid integers of length ii ending with 11.
  2. Base Case:

    • dp0[1]=1dp0[1] = 1: Only one number of length 1 ending with 00 (i.e., 00).
    • dp1[1]=1dp1[1] = 1: Only one number of length 1 ending with 11 (i.e., 11).
  3. DP Transition:

    • For each bit position from 2 to the length of nn in binary:
      • dp0[i]=dp0[i−1]+dp1[i−1]dp0[i] = dp0[i-1] + dp1[i-1] : If the current bit is 00, the previous bit can be either 00 or 11.
      • dp1[i]=dp0[i−1]dp1[i] = dp0[i-1] : If the current bit is 11, the previous bit must be 00.
  4. Calculate Result:

    • Sum up all the valid numbers up to the highest bit of nn.

Example Calculation:​

For n=5n = 5 (binary 101101):

  1. Calculate the number of valid integers for each bit length.
  2. Use the DP arrays to count valid integers.

5. Implementation (Code for 4 Languages)​

def findIntegers(n):
bin_n = bin(n)[2:]
length = len(bin_n)
dp0 = [0] * (length + 1)
dp1 = [0] * (length + 1)
dp0[1] = dp1[1] = 1
for i in range(2, length + 1):
dp0[i] = dp0[i - 1] + dp1[i - 1]
dp1[i] = dp0[i - 1]
result = dp0[length] + dp1[length]
for i in range(1, length):
if bin_n[i] == '1' and bin_n[i - 1] == '1':
break
if bin_n[i] == '0' and bin_n[i - 1] == '0':
result -= dp1[length - i]
return result

# Example usage:
print(findIntegers(5)) # Output: 5

8. Complexity Analysis​

  • Time Complexity: O(logn)O(log n), where nn is the input number. This is because we are working with the binary representation of nn, which has a length of O(logn)O(log n).
  • Space Complexity: O(logn)O(log n), due to the storage of the dp0dp0 and dp1dp1 arrays and the binary representation of nn.

9. Advantages and Disadvantages​

Advantages:​

  • Efficiently solves the problem using dynamic programming.
  • Works well for large values of nn up to (109)(10^9).

Disadvantages:​

  • Requires understanding of bit manipulation and dynamic programming concepts.

10. References​

This Markdown file includes a detailed explanation of the problem, an algorithmic approach, code implementations in four programming languages, complexity analysis, advantages and disadvantages, and references.