1. Problem
Given a positive integer n, find the number of nonnegative integers less than or equal to n, whose binary representations do NOT contain consecutive ones.
2. Thinking process
2.1 Divide the whole problem into subproblems
Before introducing the way to calculate the number of nonnegative integers less than or equal to n without consecutive ones, we divide the problem into several parts.
It is clear that if an integer has less binary digits than n, it must be smaller than n.
That is to say.
Step 1: calculate the number of all integers without consecutive ones which has less binary digits than n.
Step 2: calculate the number of all integers less than or equal to n without consecutive ones which has the same binary digits as n.
Step 3: add them together.
Suppose integer n has k digits, k ≥ 2, the total number of integers can be divided into
Total
(Part 1)
= number of 1binarydigitintegers without consecutive ones
+ number of 2binarydigitintegers without consecutive ones
+ ......
+ number of (k1)binarydigitintegers without consecutive ones
(Part 2)
+ number of kbinarydigitintegers less than or equal to n without consecutive ones
2.2 Solve Part 1 by dynamic programming
The problem is
Calculate number of pbinarydigitintegers without consecutive ones (p ≥ 1).
2.2.1 Divide the problem
As a binary number is always ended by either 0 or 1, the number of integers can be divided into 2 parts.
Define Zero(p) and One(p) as
Zero(p): the number of pbinarydigitintegers ended by zero.
One(p): the number of pbinarydigitintegers ended by one.
Suppose the total is f(p), then
f(p) = Zero(p) + One(p), p ≥ 1.
2.2.2 Find recursive relation of Zero(p) and One(p)
As I use dynamic programming, I need to find out the recursive relation in the first part of subproblems.
It can be inferred that
A pbinarydigitinteger can be generated by attaching 0 or 1 to a (p  1)binarydigitinteger's Least Significant Bit (LSB), p ≥ 2.
For an integer with p  1 binary digits, p ≥ 2

If its LSB is '0'  CAN attach '0' or '1'. ("00" or "01")

If its LSB is '1'  CAN attach '0' ("10"), CAN NOT attach 1 ("11" is consecutive ones)
which means the recursive formula is
Zero(p) = Zero(p  1) + One(p  1), p ≥ 2.
One(p) = Zero(p  1), p ≥ 2.
The formula can be simplified to
Zero(p) = Zero(p  1) + Zero(p  2), p ≥ 3.
One(p) = One(p  1) + One(p  2), p ≥ 3.
As p ≥ 2, the Most Significant Digit (MSB) of all integers with p binary digits must be 1.
If treating 0 separately, the initial value for the recursive formula will be
Zero(1) = 0, don't take "0" into account.
Zero(2) = 1, only "10", ignore "00" whose MSB is "0".
One(1) = 1, only "1".
One(2) = 0. ignore "01" whose MSB is "0" and "11" which has consecutive ones.
2.2.3 calculate f(p)
It can be inferred that
f(p) = One(p) + Zero(p) + 1(stands for "0"), p = 1.
f(p) = One(p) + Zero(p), p ≥ 2.
The whole answer to the problem is simplified to
Total
(Part 1)
= 1 (stands for "0")
+ One(1) + Zero(1)
+ One(2) + Zero(2)
+ ......
+ One(k1) + Zero(k1)
(Part 2)
+ number of kbinarydigitintegers less than or equal to n without consecutive ones
2.3 Solve Part 2 by dynamic programming
The problem is
Calculate number of kbinarydigitintegers less than or equal to n without consecutive ones (k is the number of binary digits that n has).
2.3.1 Predefinition
Before introducing the algorithm, suppose n has k bits
n = a(1)a(2)a(3)...a(k), k ≥ 2.
Since "0" has been treated in Section 2.2.3, here
a(1) is ALWAYS 1.
Define part(n, p) as
part(n, p) = n >> (k  p) = a(1)a(2)a(3)...a(p), 1 ≤ p ≤ k.
As a binary number is always ended by either 0 or 1, the number of integers less than or equal to part(n, p) can be divided into 2 parts.
Define 2 new series Zero(n, p) and One(n, p), k ≥ 1:
Zero(n, p): the number of pbinarydigitintegers ended by zero which is less than or equal to part(n, p).
One(n, p): the number of pbinarydigitintegers ended by one which is less than or equal to part(n, p).
Since a(1) is always 1, and "0" has been treated in Section 2.2.3, define the initial value for One(n, p) and Zero(n, p) as
One(n, 1) = 1.
Zero(n, 1) = 0.
2.3.2 Find recursive relation of Zero(n, p) and One(n, p)
We can attach 0 or 1 to an integer's Least Significant Bit (LSB) and make sure the new integer has no consecutive ones,
if an integer with p binary digits is less than or equal to part(n, p),
after attaching 0 or 1 to it, how can I make sure the new integer is less than or equal to part(n, p + 1)?
In this way, the problem is different to the one in Section 2.2.
Suppose m is a pbinarydigitinteger less than or equal to part(n, p), p ≥ 2.
m = m(1)m(2)...m(p1)m(p) ≤ a(1)a(2)...a(p1)a(p), p ≥ 2.
After attaching 0 or 1 to m's LSB, according to a(p), a(p + 1) and m(p), there are several cases below for us to discuss.
As the cases are complicated, please read carefully.
For 1 ≤ p < k
Case 1: a(p) = 1, a(p+1) = 0
 m(p) = 1: m = m(1)m(2)...m(p1)1 ≤ a(1)a(2)...a(p1)1 = part(n, p).
 m(p + 1) = 0:
m' = m(1)m(2)...m(p1)10 ≤ a(1)a(2)...a(p1)10 = part(n, p + 1).
 m(p + 1) = 0:
 m(p) = 0: m = m(1)m(2)...m(p1)0 < a(1)a(2)...a(p1)1 = part(n, p).
 m(p + 1) = 0 :
m' = m(1)m(2)...m(p1)00 < a(1)a(2)...a(p1)10 = part(n, p + 1).  m(p + 1) = 1 :
Although m(p + 1) > a(p + 1),
since m(p) with higher significant is smaller than a(p),
m' = m(1)m(2)...m(p1)01 < a(1)a(2)...a(p1)10 = part(n, p + 1).
 m(p + 1) = 0 :
Case 2: a(p) = 0, a(p+1) = 1
 m(p) = 1 : m = m(1)m(2)...m(p1)1 < a(1)a(2)...a(p1)0 = part(n, p).
 m(p + 1) = 0 :
m' = m(1)m(2)...m(p1)10 < a(1)a(2)...a(p1)00 < a(1)a(2)...a(p1)01 = part(n, p + 1).
 m(p + 1) = 0 :
 m(p) = 0 : m = m(1)m(2)...m(p1)0 ≤ a(1)a(2)...a(p1)0 = part(n, p).
 m(p + 1) = 0 :
m' = m(1)m(2)...m(p1)00 < a(1)a(2)...a(p1)01 = part(n, p + 1).  m(p + 1) = 1:
m' = m(1)m(2)...m(p1)01 ≤ a(1)a(2)...a(p1)01 = part(n, p + 1).
 m(p + 1) = 0 :
Case 3: a(p) = 0, a(p+1) = 0
 m(p) = 1 : m = m(1)m(2)...m(p1)1 < a(1)a(2)...a(p1)0 = part(n, p).
 m(p + 1) = 0 :
m' = m(1)m(2)...m(p1)10 < a(1)a(2)...a(p1)00 = part(n, p+1).
 m(p + 1) = 0 :
 m(p) = 0 : m = m(1)m(2)...m(p1)0 ≤ a(1)a(2)...a(p1)0 = part(n, p).
 m(p + 1) = 0 :
m' = m(1)m(2)...m(p1)00 ≤ a(1)a(2)...a(p1)00 = part(n, p+1).  m(p + 1) = 1:
m' = m(1)m(2)...m(p1)01, part(n, p+1) = a(1)a(2)...a(p1)00.
Since m ≤ part(n, p) and have same LSB,
If m = part(n, p), then m' > part(n, p+1).
If m < part(n, p), then m' < part(n, p+1).
After attaching 1 to LSB of m, ONLY when m = part(n, p), m' doesn't meet the requirement.
 m(p + 1) = 0 :
Case 4: a(p) = 1, a(p+1) = 1
 m(p) = 1 : m = m(1)m(2)...m(p1)1 ≤ a(1)a(2)...a(p1)1 = part(n, p).
 m(p + 1) = 0 :
m' = m(1)m(2)...m(p1)10 < a(1)a(2)...a(p1)11 = part(n, p+1).
 m(p + 1) = 0 :
 m(p) = 0 : m = m(1)m(2)...m(p1)0 < a(1)a(2)...a(p1)1 = part(n, p).
 m(p + 1) = 0 :
m' = m(1)m(2)...m(p1)00 < a(1)a(2)...a(p1)11 = part(n, p+1).  m(p + 1) = 1:
m' = m(1)m(2)...m(p1)01 < a(1)a(2)...a(p1)11 = part(n, p+1).
 m(p + 1) = 0 :
If case 4 happens, since m' < part(n, p + 1), the later m without consecutive ones will ALWAYS be smaller than part(n ,q), q > p + 1.
We can directly use the formula in Section 2.2.2.
Till now, if
n = a(1)a(2)a(3)...a(k), k ≥ 2.
The recursive formula for Zero(n, p) and One(n, p), 1 ≤ p < k is
If a(p) ≠ a(p+1):

Zero(n, p+1) = Zero(n, p) + One(n, p).

One(n, p+1) = Zero(n, p).
If a(p) = a(p+1) = 0:

Zero(n, p+1) = Zero(n, p) + One(n, p).

One(n, p+1) = Zero(n, p)  1. (1 for the ONLY ONE case m' > part(n, p + 1))
If a(p) = a(p+1) = 1, for all p ≤ q ≤ k

Zero(n, q+1) = Zero(n, q) + One(n, q).

One(n, q+1) = Zero(n, q).
The number of kbinarydigitintegers less than or equal to n without consecutive ones is
Zero(n, k) + One(n, k), k ≥ 2
2.4 Summarize
If k = 1
When n = 0, Total = 1.
When n = 1, Total = 2.
If k ≥ 2, the total number is
Total
= 1 (stands for "0")
+ One(1) + Zero(1)
+ One(2) + Zero(2)
+ ......
+ One(k1) + Zero(k1)
+ One(n, k) + Zero(n, k)
3. Complexity analysis
3.1 Time complexity
Since the algothrim is divided into 2 parts
Part 1: iterate from a(1) to a(k  1)
Part 2: iterate from a(1) to a(k)
The time complexity is O(k) = O(logn).
3.2 Space complexity
Two sizekarrays are used to save Zero(p), One(p) in Part 1, and Zero(n, p), One(n, p) in Part 2.
One sizekarray is used to save k binary digits of n.
the total size is 3k.
The space complexity is O(k) = O(logn).
4. Code
class Solution {
public:
int findIntegers(int num) {
if(num == 0) return 1;
if(num == 1) return 2;
//STEP 1
int digit = 0;
while(num >= 1 << digit) digit++;
int *digitsOfNum = new int[digit];
int *zero = new int[digit];
int *one = new int[digit];
//not include 0 in DP
zero[0] = 0;
zero[1] = 1;
one[0] = 1;
one[1] = 0;
int sum = 1; //include 0
for(int i = 0; i < digit; i++)
{
if(i > 1)
{
zero[i] = zero[i  1] + zero[i  2];
one[i] = one[i  1] + one[i  2];
}
if(i < digit  1) sum += zero[i] + one[i];
digitsOfNum[digit  1  i] = num % 2;
num >>= 1;
}
// STEP 2
int i = 0;
bool isValid = true;
while(true)
{
if(i + 1 == digit)break;
if(isValid)
{
if(digitsOfNum[i] != digitsOfNum[i + 1])
{
zero[i + 1] = zero[i] + one[i];
one[i + 1] = zero[i];
i++;
}else{
if(digitsOfNum[i] == 1)
{
isValid = false;
}else{
zero[i + 1] = zero[i] + one[i];
one[i + 1] = zero[i]  1;
i++;
}
}
}else{
zero[i + 1] = zero[i] + one[i];
one[i + 1] = zero[i];
i++;
}
}
return sum + zero[digit  1] + one[digit  1];
}
};