# Share my O(logn) C++ DP solution with thinking process and explanation

• ## 1. Problem

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.

## 2. Thinking process

#### 2.1 Divide the whole problem into sub-problems

Before introducing the way to calculate the number of non-negative 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 3: add them together.

Suppose integer n has k digits, k ≥ 2, the total number of integers can be divided into

#### 2.2 Solve Part 1 by dynamic programming

The problem is

#### Calculate number of p-binary-digit-integers 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

#### One(p): the number of p-binary-digit-integers 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 sub-problems.

It can be inferred that

#### A p-binary-digit-integer can be generated by attaching 0 or 1 to a (p - 1)-binary-digit-integer'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

#### One(p) = Zero(p - 1), p ≥ 2.

The formula can be simplified to

#### 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

#### 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), p ≥ 2.

The whole answer to the problem is simplified to

#### 2.3 Solve Part 2 by dynamic programming

The problem is

#### Calculate number of k-binary-digit-integers less than or equal to n without consecutive ones (k is the number of binary digits that n has).

##### 2.3.1 Pre-definition

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:

#### One(n, p): the number of p-binary-digit-integers 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

#### In this way, the problem is different to the one in Section 2.2.

Suppose m is a p-binary-digit-integer less than or equal to part(n, p), p ≥ 2.

#### m = m(1)m(2)...m(p-1)m(p) ≤ a(1)a(2)...a(p-1)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(p-1)1 ≤ a(1)a(2)...a(p-1)1 = part(n, p).
• m(p + 1) = 0:
m' = m(1)m(2)...m(p-1)10 ≤ a(1)a(2)...a(p-1)10 = part(n, p + 1).

• m(p) = 0: m = m(1)m(2)...m(p-1)0 < a(1)a(2)...a(p-1)1 = part(n, p).
• m(p + 1) = 0 :
m' = m(1)m(2)...m(p-1)00 < a(1)a(2)...a(p-1)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(p-1)01 < a(1)a(2)...a(p-1)10 = part(n, p + 1).

#### Case 2: a(p) = 0, a(p+1) = 1

• m(p) = 1 : m = m(1)m(2)...m(p-1)1 < a(1)a(2)...a(p-1)0 = part(n, p).
• m(p + 1) = 0 :
m' = m(1)m(2)...m(p-1)10 < a(1)a(2)...a(p-1)00 < a(1)a(2)...a(p-1)01 = part(n, p + 1).

• m(p) = 0 : m = m(1)m(2)...m(p-1)0 ≤ a(1)a(2)...a(p-1)0 = part(n, p).
• m(p + 1) = 0 :
m' = m(1)m(2)...m(p-1)00 < a(1)a(2)...a(p-1)01 = part(n, p + 1).
• m(p + 1) = 1:
m' = m(1)m(2)...m(p-1)01 ≤ a(1)a(2)...a(p-1)01 = part(n, p + 1).

#### Case 3: a(p) = 0, a(p+1) = 0

• m(p) = 1 : m = m(1)m(2)...m(p-1)1 < a(1)a(2)...a(p-1)0 = part(n, p).
• m(p + 1) = 0 :
m' = m(1)m(2)...m(p-1)10 < a(1)a(2)...a(p-1)00 = part(n, p+1).

• m(p) = 0 : m = m(1)m(2)...m(p-1)0 ≤ a(1)a(2)...a(p-1)0 = part(n, p).
• m(p + 1) = 0 :
m' = m(1)m(2)...m(p-1)00 ≤ a(1)a(2)...a(p-1)00 = part(n, p+1).
• m(p + 1) = 1:
m' = m(1)m(2)...m(p-1)01, part(n, p+1) = a(1)a(2)...a(p-1)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.

#### Case 4: a(p) = 1, a(p+1) = 1

• m(p) = 1 : m = m(1)m(2)...m(p-1)1 ≤ a(1)a(2)...a(p-1)1 = part(n, p).
• m(p + 1) = 0 :
m' = m(1)m(2)...m(p-1)10 < a(1)a(2)...a(p-1)11 = part(n, p+1).

• m(p) = 0 : m = m(1)m(2)...m(p-1)0 < a(1)a(2)...a(p-1)1 = part(n, p).
• m(p + 1) = 0 :
m' = m(1)m(2)...m(p-1)00 < a(1)a(2)...a(p-1)11 = part(n, p+1).
• m(p + 1) = 1:
m' = m(1)m(2)...m(p-1)01 < a(1)a(2)...a(p-1)11 = part(n, p+1).

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 k-binary-digit-integers less than or equal to n without consecutive ones is

If k = 1

#### When n = 1, Total = 2.

If k ≥ 2, the total number is

## 3. Complexity analysis

#### 3.1 Time complexity

Since the algothrim is divided into 2 parts

#### One size-k-array is used to save k binary digits of n.

the total size is 3k.

## 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];
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.