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


  • 1
    K

    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 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 1-binary-digit-integers without consecutive ones

    + number of 2-binary-digit-integers without consecutive ones

    + ......

    + number of (k-1)-binary-digit-integers without consecutive ones


    (Part 2)

    + number of k-binary-digit-integers less than or equal to n without consecutive ones


    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


    Zero(p): the number of p-binary-digit-integers ended by zero.

    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

    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(k-1) + Zero(k-1)


    (Part 2)

    + number of k-binary-digit-integers less than or equal to n without consecutive ones


    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:


    Zero(n, p): the number of p-binary-digit-integers ended by zero which is less than or equal to part(n, p).

    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


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

    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(k-1) + Zero(k-1)

    + 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 size-k-arrays are used to save Zero(p), One(p) in Part 1, and Zero(n, p), One(n, p) in Part 2.

    One size-k-array 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];
        }
    };
    


Log in to reply
 

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