This is a DP problem.
Step 1: build a sequence f where f[k] indicates the count of binary number without consecutive 1.
Indeed, f is the Fibonacci sequence.
For instance, f[5] is the count within 00000 to 11111, which consists of two following parts:
00000 to 01111; and10000 to 10111.Note that numbers start with 11 are invalid.
The first part is f[4] and the second part is f[3], thus f[5] = f[4] + f[3].
Step 2: go through the digits of the given number from left to right, adds the count in
corresponding sub-range, until encountered a consecutive 1.
See the code for details.
Finally, add one to include the number itself.
public class Solution {
public int findIntegers(int num) {
// fib[k]: valid counts with length = k
int[] fib = new int[32];
fib[0] = 1;
fib[1] = 2;
for (int i = 2; i < 32; ++i) fib[i] = fib[i - 1] + fib[i - 2];
List<Integer> digits = new LinkedList<>();
while (num > 0) {
digits.add(num % 2);
num /= 2;
}
int ans = 0;
for (int i = digits.size() - 1; i >= 0; --i) {
ans += digits.get(i) * fib[i];
if (i == digits.size() - 1 || digits.get(i) == 0 || digits.get(i + 1) == 0) continue;
--ans;
break;
}
return ans + 1;
}
}