Problem Explanation:

The problem gives us an integer n and asks us to find how many numbers from 0 to n(inclusive) do not have consecutive ones in their binary representation. For example, if n is 5, in binary 5 is represented as '101', which does not have consecutive ones. However, 3 which is '11' in binary does have consecutive ones. For this problem, we need calculate how many numbers in the range 0 to n don't have consecutive ones.

Walk Through an Example

If we take the example where n=5, we would have the numbers 0,1,2,3,4 and 5 to consider. The binary representation of these numbers are 0,1,10,11,100 and 101 respectively.

From these numbers, 0,1,2,4 and 5 do not contain consecutive ones in their binary representation. But 3 which is represented as '11' in binary does have consecutive ones. Hence, the total number of non-negative integers without consecutive ones from 0 to 5 is 5.

Approach of the solution:

The approach involves dynamic programming. We implement this solution by first converting the input number into its binary representation. We then define two vectors (one and zero), which is used to store the count of the numbers that ends with 0 and 1 in their binary representation respectively. The core idea is that if the current number ends with 0, we could still append either 0 or 1 to this number to make a larger number. If it ends with 1, then we could only append 0.

Python Solution:

1
2python
3class Solution:
4    def findIntegers(self, num: int) -> int:
5        binary = bin(num)[2:][::-1]
6        n = len(binary)
7        dp = [0] * (n + 1)
8        dp[0] = 1
9        dp[1] = 2
10        for i in range(2, n + 1):
11            dp[i] = dp[i - 1] + dp[i - 2]
12        sum = 0
13        for i in range(n - 1, -1, -1):
14            if binary[i] == '1':
15                sum += dp[i]
16                if i < n - 1 and binary[i + 1] == '1':
17                    return sum
18        return sum + 1

Java solution:

1
2java
3public class Solution {
4    public int findIntegers(int num) {
5        int[] f = new int[32];
6        f[0] = 1;
7        f[1] = 2;
8        for (int i = 2; i<f.length; i++){
9            f[i] = f[i-1]+f[i-2];
10        }
11        int k = 30, pre_bit = 0, res = 0;
12        while (k >= 0){
13            if ((num & (1 << k)) != 0 ){
14                res += f[k];
15                if (pre_bit == 1 ){
16                    return res;
17                }
18                pre_bit = 1;
19            }else {
20                pre_bit = 0;
21            }
22            k--;
23        }
24        return res + 1;
25    } 
26}

JavaScript solution:

1
2javascript
3var findIntegers = function(num) {
4    var dp = new Array(32);
5    dp.fill(0);
6    
7    dp[0] = 1;
8    dp[1] = 2;
9    
10    for (var i = 2; i < 32; i++) {
11        dp[i] = dp[i-2] + dp[i-1];
12    }
13    
14    var prev_bit = 0;
15    var sum = 0;
16    for (var i = 31; i >= 0; i--) {
17        var bit = (num >> i) & 1;
18        if (bit === 1) {
19            sum += dp[i];
20            if (prev_bit === 1) {
21                sum--;
22                break;
23            }
24        }
25        prev_bit = bit;
26    }
27    
28    return sum+1;
29};

All the above solutions implement the same logic but in different programming languages (Python, Java, and JavaScript). The core idea is that for a binary number of length n, there are dp[n] such numbers, where dp[n] is the sum of dp[n-1] and dp[n-2] as in the Fibonacci series.

The dynamic programming values are pre-computed and the bitwise representation of the number is analyzed to determine if the current bit is 1. If so, dp[k] (where k is the current bit position) is added to the result. If the current bit and previous bit are both 1, the operation is stopped and the result is returned. If the current bit is 0, prev_bit is 0 and the process is continued. At the end of the loop, 1 is added to the result to adjust for the 0 and the result is returned.