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
Approach #1: DP. [C++]
class Solution {
public:
int findIntegers(int num) {
vector<int> f(35, 0);
f[0] = 1;
f[1] = 2;
for (int i = 2; i < 32; ++i)
f[i] = f[i-1] + f[i-2];
int ans = 0, k = 30, pre_bit = 0;
while (k >= 0) {
if (num & (1 << k)) {
ans += f[k];
if (pre_bit == 1) return ans;
pre_bit = 1;
} else pre_bit = 0;
k--;
}
return ans+1;
}
};
Analysis:
The solution if based on 2 fact:
First: the number of length k string without consecutive 1 is Fibonacci sequence f(k);
For example, is k = 5, the range is 00000 - 11111. We can consider it as two ranges, which are 00000 - 01111 ans 10000 10111. any number >= 11000 is not allowed due to consecutive 1. The first case is actually f(4), and the second case is f(3), so f(5) = f(4) + f(3).
Second: Scan the number from most significant digit, i.e. left to right, in binary format. If we find a '1' with k digits to the right, count increases by f(k) beause we can put a '0' at this digit and any valid length k string behind; After that, we continue the loop to consider the remaining case, i.e. we put a '1' at this digit. If consecutive 1s are found, we exit the loop and return the answer. By the end of the loop, we return ans + 1 to include the number n itself.
Reference:
https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/discuss/103754/C%2B%2B-Non-DP-O(32)-Fibonacci-solution