# 600. Non-negative Integers without Consecutive Ones

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: 1 <= n <= 109

``````class Solution {
public:
int findIntegers(int num) {
int cnt = 0, n = num;
string t = "";
while (n > 0) {
++cnt;
t += (n & 1) ? "1" : "0";
n >>= 1;
}
vector<int> zero(cnt), one(cnt);
zero[0] = 1; one[0] = 1;
for (int i = 1; i < cnt; ++i) {
zero[i] = zero[i - 1] + one[i - 1];
one[i] = zero[i - 1];
}
int res = zero[cnt - 1] + one[cnt - 1];
for (int i = cnt - 2; i >= 0; --i) {
if (t[i] == '1' && t[i + 1] == '1') break;
if (t[i] == '0' && t[i + 1] == '0') res -= one[i];
}
return res;
}
};
``````

``````class Solution {
public:
int findIntegers(int num) {
int res = 0, k = 31, pre = 0;
vector<int> f(32, 0);
f[0] = 1; f[1] = 2;
for (int i = 2; i < 31; ++i) {
f[i] = f[i - 2] + f[i - 1];
}
while (k >= 0) {
if (num & (1 << k)) {
res += f[k];
if (pre) return res;
pre = 1;
} else pre = 0;
--k;
}
return res + 1;
}
};
``````

House Robber II

House Robber

Ones and Zeroes

https://discuss.leetcode.com/topic/90571/java-solution-dp

https://discuss.leetcode.com/topic/90639/c-non-dp-o-32-fibonacci-solution

https://discuss.leetcode.com/topic/90671/java-o-1-time-o-1-space-dp-solution

http://www.geeksforgeeks.org/count-number-binary-strings-without-consecutive-1s/

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation