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
public class Solution {
public int findIntegers(int num) {
StringBuilder sb = new StringBuilder(Integer.toBinaryString(num)).reverse();
int n = sb.length();
// a[i] means length of i and ends with 0.
// b[i] means length of i and ends with 1.
int a[] = new int[n];
int b[] = new int[n];
a[0] = b[0] = 1;
for (int i = 1; i < n; i++) {
a[i] = a[i - 1] + b[i - 1];
b[i] = a[i - 1];
}
// all possible strings of length n with no consecutive ones
int result = a[n - 1] + b[n - 1];
for (int i = n - 2; i >= 0; i--) {
// if we encounter a 11 that is not possible in any of our solutions , that
// means we dont need to substract anything and everything in result is < num
if (sb.charAt(i) == '1' && sb.charAt(i + 1) == '1')
break;
// If we encounter a 00 that means we need to reduce those counts ending with 1s
// because they will be > num
if (sb.charAt(i) == '0' && sb.charAt(i + 1) == '0')
result -= b[i];
}
return result;
}
}