Non-negative Integers without Consecutive Ones

Introduction

Given a positive integer n, find the number of non-negative integers less than or equal to n, whose binary representations do NOT contain consecutive ones.

Example 1:
Input: 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.

Note: 1 <= n <= 109

Solution

A naive solution to check all numbers smaller or equal to n won’t work as it will give you TLE (Time Limit Exceeded) error on leetcode Online Judgement. Here I use dynamic programming method to recursively search solutions.

First of all, Compute cache[] like Fibonacci sequence, cache[i] means the number of Non-consecutive integers without consecutive ones for all integers of length i in its binary form. For example, cache[1] = 2 for both 0 and 1, cache[2] = 3 for 00, 01 and 10, cache[3] = 5 for 000, 001, 010, 100 and 101, so cache[i] = cache[i-1] + cache[i-2], because if the most significant digit of number in length i is 0, then the remaining i-1 digits have cache[i-1] Non-consecutive integers without consecutive ones. If it is 1, then the second most significant digit must be 0 to avoid consecutive ones, thus the remaining i-2 digits have cache[i-2] Non-consecutive integers without consecutive ones. Before we solve the problem, cache[] array can be pre-computated for future use and save some time.

Secondly, I came up with a equation to recursively find the solution. Given a number num, we define a function find(num) that equals to the number of Non-consecutive integers without consecutive ones, which are either smaller or equal to num. d[r] is used to denote the digit in position r. For a number in binary format like 11001, d[3] = 1, d[2] = 0, etc. We also define a new function rm2() to remove first two digits in binary form like from 110100 to 000100 by using mask to calculate 110100 & 001111.

$$ find(num)= \cases{ find(rm2(num)) + cache[r], & \text{if second most significant digit is 0.} \cr cache[r-1] + cache[r], & \text{otherwise} } $$

For example num = 11011, Use bit shift operation to find the position of most significant digit is r = 4, which is the same as the length of remaining digits without most significant digit. One part of the sum is the number of Non-consecutive integers without consecutive ones, which are less than num and d[r] = 0, is equal to cache[r]. The other part is the sum for cases when d[r] = 1, then the next digit of all integers must be 0 and there are two different conditions to consider: * For number num d[r-1] = 0, add find(rm2(num)) as we try to find all Non-consecutive integers without consecutive ones between 10000 and 10011, which is exactly equal to find(rm2(num)). * For number num d[r-1] = 1, add cache[r-1] as we try to find all Non-consecutive integers without consecutive ones between 10000 and 10111.

public class NonNegativeIntegersWithoutConsecutiveOnes {
  public NonNegativeIntegersWithoutConsecutiveOnes() {
    cache = new int[32];
    cache[1] = 2;
    cache[2] = 3;
    for(int i=3; i<32; i++) {
      cache[i] = cache[i-1] + cache[i-2];
    }
  }

  // Hard code cached array here for performance gain and beats 80% submission so far.
  public int[] cache = {0, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578};

  public Map<Integer, Integer> map = new HashMap<>();

  public int findIntegers(int num) {
    if(num == 0) return 1;
    else if(num == 1) return 2;
    else if(num == 2 || num == 3) return 3;

    int r = 30, mask = 1, i = 0;
    while((num & (1 << r)) == 0) r--;		
    while(i < r-2) {
      mask = (mask << 1) + 1;
      i++;
    } 		
    int sum1 = ((1 << (r-1) & num) == 0)? findIntegers(num & mask) : cache[r-1];
    int sum2 = cache[r];
    return  sum1 + sum2;
  }
}