# 600     Non-negative Integers without Consecutive Ones

## 600. [Non-negative Integers without Consecutive Ones](https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/description/)

## 1. Question

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:**&#x31; <= n <= 109

## 2. Implementation

**(1) DP**

思路: 详细解析可以参考 [https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/discuss/103749/Java-Solution-DP，](https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/discuss/103749/Java-Solution-DP%EF%BC%8C) **下次再刷的时候需要进一步理解这题**

```java
class Solution {
    public int findIntegers(int num) {
        if (num < 0) {
            return 0;
        }

        // Step 1: Get the binary format of num
        // Notice that the binary format is reversed, that is LSB is at the beginning
        StringBuilder sb = new StringBuilder();
        while (num > 0) {
            if ((num & 1) == 1) {
                sb.append(1);
            }
            else {
                sb.append(0);
            }
            num >>>= 1;
        }

        String bit = sb.toString();
        int n = bit.length();

        // Step 2: Count number of binary without consecutive ones with length n 
        // Idea: https://www.geeksforgeeks.org/count-number-binary-strings-without-consecutive-1s/

        // Binary without consecutive one that ends with one
        int[] ones = new int[n];
        // Binary without consecutive one that ends with zero
        int[] zeroes = new int[n];
        ones[0] = 1;
        zeroes[0] = 1;

        for (int i = 1; i < n; i++) {
            zeroes[i] = ones[i - 1] + zeroes[i - 1];
            ones[i] = zeroes[i - 1];
        }

        // Total number of binary without consecutive ones with length n
        int total = ones[n - 1] + zeroes[n - 1];


        // Step 3: Remove binary without consecutive ones which is greater than num
        // Check this from Most Significant Bit to Least Significant Bit
        for (int i = n - 2; i >= 0; i--) {
            // When we find consecutive 1s in the binary format, we know total doesn't contain bianry consecutive ones
            // So we break here
            if (bit.charAt(i) == '1' && bit.charAt(i + 1) == '1') break;

            // When we find consecutive 0s in the binary format, we need to substract the binary format ending with one at length
            // i, for example with length 3, when number is 8 (whose binary format is 100), the total will count into 101,
            // so we need to remove the case 101 since it is greater than 8
            if (bit.charAt(i) == '0' && bit.charAt(i + 1) == '0') total -= ones[i];
        }
        return total;
    }
}
```

## 3. Time & Space Complexity

**DP**: 时间复杂度O(n), 空间复杂度O(n)
