# 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，> **下次再刷的时候需要进一步理解这题**

```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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/dynamic-programming/600-non-negative-integers-without-consecutive-ones.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.