Formatted question description: https://leetcode.ca/all/600.html

# 600. Non-negative Integers without Consecutive Ones (Hard)

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:5Output:5Explanation: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 <= 10^{9}

**Companies**:

Pocket Gems

**Related Topics**:

Dynamic Programming

## Solution 1.

Let `f(n)`

be the numbers less than or equal to `n`

whose binary representations DO contain consecutive ones.

x | binary(x) | has consecutive ones |
---|---|---|

0 | 0 | |

1 | 1 | |

2 | 10 | |

3 | 11 | 1 |

4 | 100 | |

5 | 101 | |

6 | 110 | 1 |

7 | 111 | 1 |

8 | 1000 | |

9 | 1001 | |

10 | 1010 | |

11 | 1011 | 1 |

12 | 1100 | 1 |

13 | 1101 | 1 |

14 | 1110 | 1 |

15 | 1111 | 1 |

16 | 10000 |

We can find pattern in this way:

- We separate the table rows according to count of bits. So 0~1 is the first group, 2~3 is the second group, 4~7 is the third group, 8~15 is the forth group…
- Starting from the second group, the numbers in the second half of the group all have consecutive ones, simply because they have leading
`11`

. - For the numbers in the first half of the groups, the pattern is the same after removing the leading
`10`

.

Take 14 as example which is in group 8~15, it’s in the second half, so 12~14 all have consecutive ones. And 8~11 has the same pattern as 0~3.

So we can get this equation:

```
let k = floor(log2(n))
let p = 2^k
f(n) = f(p-1) +
{ f(n-p) if n-(p-1)<= p/2
{ n-(p-1)-p/2 + f(p/2-1) if n-(p-1)>p/2
```

```
// OJ: https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/
// Time: O(logN)
// Space: O(logN)
class Solution {
private:
unordered_map<int, int> m;
int find(int num) {
if (num < 2) return 0;
if (m.find(num) != m.end()) return m[num];
int k = log2(num), p = pow(2, k);
int ans = find(p - 1);
if (num > p / 2 * 3 - 1) ans += num - p / 2 * 3 + 1 + find(p / 2 - 1);
else ans += find(num - p);
return m[num] = ans;
}
public:
int findIntegers(int num) {
return num + 1 - find(num);
}
};
```

Java

```
class Solution {
public int findIntegers(int num) {
if (num <= 2)
return num + 1;
int bits = (int) (Math.log(num) / Math.log(2));
int counts = 2;
int zeros = 0, ones = 1;
for (int i = 2; i <= bits; i++) {
int newZeros = zeros + ones;
ones = zeros;
zeros = newZeros;
counts += zeros;
counts += ones;
}
int zerosUnrestricted = 0, zerosRestricted = 0, onesUnrestricted = 0, onesRestricted = 1;
for (int i = 1; i <= bits; i++) {
int curBit = (num >> bits - i) & 1;
if (curBit == 0) {
int curZerosUnrestricted = zerosUnrestricted + onesUnrestricted;
int curZerosRestricted = zerosRestricted + onesRestricted;
int curOnesUnrestricted = zerosUnrestricted;
int curOnesRestricted = 0;
zerosUnrestricted = curZerosUnrestricted;
zerosRestricted = curZerosRestricted;
onesUnrestricted = curOnesUnrestricted;
onesRestricted = curOnesRestricted;
} else {
int curZerosUnrestricted = zerosUnrestricted + zerosRestricted + onesUnrestricted + onesRestricted;
int curZerosRestricted = 0;
int curOnesUnrestricted = zerosUnrestricted;
int curOnesRestricted = zerosRestricted;
zerosUnrestricted = curZerosUnrestricted;
zerosRestricted = curZerosRestricted;
onesUnrestricted = curOnesUnrestricted;
onesRestricted = curOnesRestricted;
}
}
counts += zerosUnrestricted + zerosRestricted + onesUnrestricted + onesRestricted;
return counts;
}
}
```