Non-negative Integers without Consecutive Ones

HARD

Description

Given a positive integer n, return the number of the integers in the range [0, n] whose binary representations do not contain consecutive ones.

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 <= 10⁹

Approaches

Checkout 3 different approaches to solve Non-negative Integers without Consecutive Ones. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

The most straightforward approach is to iterate through every number from 0 to n and, for each number, check if its binary representation contains consecutive ones. If it doesn't, we increment a counter. This method is easy to understand but inefficient for large values of n.

Algorithm

Initialize a counter count to 0.
Iterate through each integer i from 0 to n.
For each integer i, check if its binary representation contains consecutive ones.
A simple way to check this is using bit manipulation. If (i & (i >> 1)) is non-zero, it means there was at least one position where a bit and its adjacent bit to the right were both 1.
If i does not have consecutive ones, increment the count.
After the loop finishes, return count.

This approach involves a simple loop from 0 to n. Inside the loop, for each number i, we perform a check. The check for consecutive ones can be done by converting the number to a binary string and searching for the substring "11", but a more efficient bitwise trick exists. By taking the number i and bitwise ANDing it with itself right-shifted by one (i >> 1), we can detect consecutive ones. If the result of i & (i >> 1) is not zero, it implies that there was some bit position k where both the k-th bit and (k-1)-th bit were 1, indicating consecutive ones. While the check for each number is very fast (O(1)), the overall algorithm's performance is limited by the loop that runs n+1 times.

class Solution {
    public int findIntegers(int n) {
        int count = 0;
        for (int i = 0; i <= n; i++) {
            // Check for consecutive ones using a bitwise trick.
            // If (i & (i >> 1)) is non-zero, it means there was a '11' pattern.
            if ((i & (i >> 1)) == 0) {
                count++;
            }
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n). The loop runs `n+1` times, and the check inside is a constant time operation. This will result in a Time Limit Exceeded error for large `n`.Space Complexity: O(1)

Pros and Cons

Pros:

Very simple to understand and implement.
Requires minimal space.

Cons:

The time complexity is directly proportional to n, which is too slow for the given constraint of n <= 10^9.

Code Solutions

Checking out 3 solutions in different languages for Non-negative Integers without Consecutive Ones. Click on different languages to view the code.

class Solution {
private
  int[] a = new int[33];
private
  int[][] dp = new int[33][2];
public
  int findIntegers(int n) {
    int len = 0;
    while (n > 0) {
      a[++len] = n & 1;
      n >>= 1;
    }
    for (var e : dp) {
      Arrays.fill(e, -1);
    }
    return dfs(len, 0, true);
  }
private
  int dfs(int pos, int pre, boolean limit) {
    if (pos <= 0) {
      return 1;
    }
    if (!limit && dp[pos][pre] != -1) {
      return dp[pos][pre];
    }
    int up = limit ? a[pos] : 1;
    int ans = 0;
    for (int i = 0; i <= up; ++i) {
      if (!(pre == 1 && i == 1)) {
        ans += dfs(pos - 1, i, limit && i == up);
      }
    }
    if (!limit) {
      dp[pos][pre] = ans;
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Non-negative Integers without Consecutive Ones

Patterns:

Dynamic Programming

Companies:

Pocket Gems |