Vultr DocsLatest Content

Non-negative Integers without Consecutive Ones

Updated on 19 June, 2025
Non-negative Integers without Consecutive Ones header image

Problem Statement

Given a positive integer n, the task is to determine how many integers within the inclusive range from 0 to n have binary representations that do not contain consecutive ones. The binary representation of a number refers to its expression in base-2 numeral system where each digit is either 0 or 1. This problem requires counting all valid numbers whose binary form adheres to the specific pattern of not having two 1s in a row.

Examples

Example 1

Input:

n = 5

Output:

5

Explanation:

Here are the non-negative integers <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule.

Example 2

Input:

n = 1

Output:

2

Example 3

Input:

n = 2

Output:

3

Constraints

  • 1 <= n <= 109

Approach and Intuition

  1. Understanding the Binary constraint: The core challenge lies in checking each number's binary form within the given range for consecutive ones.

  2. Brute Force Method:

    • Iterate from 0 to n.
    • Convert each number to its binary representation.
    • Check if the binary string has any consecutive ones.
    • Count those numbers which do not have consecutive ones.

  3. Optimization Insight:

    • Directly checking each number up to n is computationally expensive, especially when n is large (up to 1 billion).
    • An optimized approach involves using dynamic programming or bitwise manipulation to skip directly checking each number.

  4. Example Breakdown:

    • For n = 5, convert each number (0 to 5) to binary:
      • 0: 0 -> no ones
      • 1: 1 -> single one
      • 2: 10 -> one followed by zero
      • 3: 11 -> consecutive ones
      • 4: 100 -> one followed by two zeros
      • 5: 101 -> alternating one and zero
    • Among these, only the number 3 fails the condition. Therefore, the count of valid numbers is 5.

  5. Dynamic Programming Consideration:

    • Utilize two arrays where one tracks the count of valid binary strings ending in 0 and the other for strings ending in 1.
    • Base cases are for single digit binary numbers.
    • Transition involves building numbers using safe combinations from previous counts, avoiding direct placement of ones after one.

By applying the above considerations, the solution can be both efficient and accurate, thus solving the problem within the constraints provided.

Solutions

  • Java
java 
public class Solution {
    public int countValidNumbers(int n) {
        int[] fibonacci = new int[32];
        fibonacci[0] = 1;
        fibonacci[1] = 2;
        for (int index = 2; index < fibonacci.length; index++)
            fibonacci[index] = fibonacci[index - 1] + fibonacci[index - 2];
        int i = 30, result = 0, lastBit = 0;
        while (i >= 0) {
            if ((n & (1 << i)) != 0) {
                result += fibonacci[i];
                if (lastBit == 1) {
                    result--;
                    break;
                }
                lastBit = 1;
            } else
                lastBit = 0;
            i--;
        }
        return result + 1;
    }
}

The solution provided in Java tackles the problem of counting valid numbers up to 'n' that do not have consecutive ones in their binary representation. Here is how this solution operates:

  • An array called fibonacci is initialized to represent the number of valid binary numbers up to a certain number of digits based on the Fibonacci sequence. The size of the array is specified by int[32] assuming a 32-bit integer.
  • The Fibonacci sequence is pertinent because the count of valid binary numbers without consecutive ones closely follows this sequence. Each position index in fibonacci is calculated as the sum of the two preceding values, akin to the Fibonacci sequence (fibonacci[index - 1] + fibonacci[index - 2]).
  • Variables i, result, and lastBit are used to traverse the binary representation of the number from the most significant bit to the least significant bit. i starts at 30, considering up to 31 bits for an integer.
  • A loop then checks each bit of n from the highest to the lowest:
    • If the ith bit of n is set (i.e., equals 1), the result is incremented by the value in fibonacci[i] to account for all valid numbers that can be formed with the lower bits.
    • A check is made for consecutive ones: if lastBit is also 1 (indicating consecutive ones), the loop breaks after decrementing the result (to revert the last incorrect addition).
    • lastBit is updated based on whether the current bit is 1 or 0.
  • After the loop, 1 is added to the result to include zero in the count of valid numbers.
  • Finally, the function returns the result, which gives the number of valid non-negative integers up to n that do not have consecutive ones in their binary representation.

This algorithm skillfully uses the properties of the Fibonacci sequence to convert the combinatorial problem into a simple computation involving checking bits and summing corresponding Fibonacci numbers. Ensure to create a test case to verify that the code input matches the expected output for accuracy in numbering various cases from 0 up to any given n.

Comments

No comments yet.