Stokastik

Machine Learning, AI and Programming

Leetcode : Non-negative Integers without Consecutive Ones

Problem Statement

Solution:

The brute force approach is to scan all the integers less than equals to N, compute their binary representation and check if the binary representation has consecutive ones or not. The run-time complexity of this approach is O(N*logN) because scanning all the integers less than N is O(N) and scanning the binary representation for each integer is O(logN), because binary representation of an integer M is of length O(logM). We can improve this run-time by only working with the binary representation of N instead of the integers.

If the binary representation of a number N, denoted by M, is of length K, where K = O(logN), then the number of non-negative integers without consecutive ones less than equal to N can be found out by the following approach:

Let F(M, i) denote the number of non-negative integers without consecutive ones less than equal to the integer represented by the bits from the i-th index in M to the end of M, e.g. if M='1101' and i=1, then the corresponding bits are '101' i.e. the last 3 bits and the corresponding integer representation is 5.

Let's take an example, M='110011' (N=51). Now in order to find the count of all binary representations without consecutive ones, whose integer representations are less than equals to integer rep. for M i.e. 51, we can divide it into two parts:

count of all binary representations without consecutive ones for integers less than 51 with the bit at the 0-th index set to 0

+

count of all binary representations without consecutive ones for integers less than 51 with the bit at the 0-th index set to 1

For the 1st part, the maximum integer less than 51 for which the 1st bit is off is '011111' = 31, i.e. we need to find the the count of all binary representations without consecutive ones, whose integer representations are less than equals to 31.

For the 2nd part, if the 1st bit is set to 1 and the we need to count all binary representations without consecutive ones, then the 2nd bit must be set to 0 in order to avoid the first two bits forming consecutive ones. When the first two bits are fixed to '10', then the maximum integer less than 51 whose first two bits are '10' is '101111'=47.

Thus we need to find the the count of all binary representations without consecutive ones, whose integer representation is less than equals to '1111' = 15 because the first two bits are now fixed at '10'.

Thus,

F('110011', 0) = F('011111', 1) + F('101111', 2)

Note that if the 2nd bit in M was '0' instead of '1', i.e. M='100011' (N=35), then the 1st part would remain same i.e. F('011111', 1), but for the 2nd part, we cannot compute F('101111', 2) because '101111' is greater than '100011'. In such case:

F('100011', 0) = F('011111', 1) + F('100011', 2)

Because the maximum integer less than equal to M='100011' (N=35) with the first two bits set to '10' is 35 itself.

Thus we can formulate the recurrence relation as follows:

  • If M[i] == '1' and M[i+1] == '1', then F(M, i) = G[K-i-1] + G[K-i-2]
  • If M[i] == '1' and M[i+1] == '0', then F(M, i) = G[K-i-1] + F(M, i+1)
  • If M[i] == '0', then F(M, i) = F(M, i+1)
  • If i == K-1, then F(M, i) = 2 if M[i] == '1' else F(M, i) = 1

where we define G[n] as the the count of all binary representations without consecutive ones, whose integer representations are less than equals to '111...1', i.e. '1' repeated 'n' times or 2n-1.

F(M, i) is G[K-i-1] + G[K-i-2] because after the 1st bit is set to 0, the maximum integer less than N corresponds to '1' repeated K-i-1 times and after the first two bits are set to '10' the maximum integer less than N corresponds to '1' repeated K-i-2 times.

Computing the array G is easy because all the bits are set to 1 and we can pre-compute the array G for an array of size K+1, i.e. pre-compute G[0], G[1], ..., G[K]

G[0] = 1, G[1] = 2,  G[n] = G[n-1] + G[n-2] for n >= 2

Following is the code in Python:

class Solution(object):
    def findIntegers(self, num):
        bin_str = str(bin(num))[2:]
        n = len(bin_str)
        
        full_ints = [0]*(n+1)
        full_ints[0], full_ints[1] = 1, 2
        
        for i in range(2, n+1):
            full_ints[i] = full_ints[i-1] + full_ints[i-2]
            
        cnt = 0
        for i in reversed(range(n)):
            if i == n-1:
                cnt = 2 if bin_str[i] == '1' else 1
            else:
                if bin_str[i] == '1':
                    a = full_ints[n-i-2] if bin_str[i+1] == '1' else cnt
                    cnt = full_ints[n-i-1] + a
        
        return cnt

The run-time complexity of the above approach is O(logN).

Categories: PROBLEM SOLVING

Tags: , , , ,

Leave a Reply