C++ Simple O(1) Space Solution. (NOT O(32) which is actually O(lgN))


  • 0
    F

    The below algorithm runs in O(lgN*k) time, where k is the number of 1's in N before the first pair of consecutive 1's.
    The space is O(1), not O(32) which is O(log10(N)) in fact.
    The idea is simple:
    For example: 1110
    We count all valid numbers from 000 to 111 first, that's all valid cases below 1000,
    Then we count 1000 ~ 1100's valid cases, that's the same as 00~11.
    Then we count 1100 ~ 1110's valid cases, BUT this time it is different, because anything starting with 11XX is already invalid, so we don't need to count anymore. we have covered all valid cases.

    It's certainly possible that N itself is valid (the BUT statement doesn't apply anywhere in N), like 10101, then the algorithm counting range will look like:

    Count [0, 10000)     == [0, 1111]    
    Count [10000, 10100) == [0, 11]
    Count [10100, 10101) == [0, 0]
    

    Note the last step counts toward 10101, but it doesn't include it. So you need to add 1 (N itself) before return (I got a WA in my first submission during the contest because of this ...)

    As for how to count the valid numbers between [0, 111..1], you can refer to the calc function below. It's a simple O(1) space DP.

    class Solution {
        int calc(int len)
        {
            int l0 = 1, l1 = 0;
            for (int i = 0; i < len; ++i)
                l0 += l1, l1 = l0 - l1;
            return l1 + l0;
        }
    public:
        int findIntegers(int num) {
            int sum = 0;
            bool is_last_one = false;
            for (int i = 31; i >= 0; i --)
                if ((1 << i & num) > 0)
                {
                    sum += calc(i);
                    if ((1 << i+1 & num) > 0)
                        return sum;
                }
            return sum + 1;
        }
    };
    

    And if we take advantage of int being 32 here, we can pre-calculate all calc(len) first, make it an array, and reduce the time complexity from O(lgN*k) to O(lgN), but increase space complexity to O(lgN) too.:

    class Solution {
    public:
        int findIntegers(int num) {
            int calc[32] = {1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765
            ,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309};
            int sum = 0;
            bool is_last_one = false;
            for (int i = 31; i >= 0; i --)
                if ((1 << i & num) > 0)
                {
                    sum += calc[i];
                    if ((1 << i+1 & num) > 0)
                        return sum;
                }
            return sum + 1;
        }
    };
    

Log in to reply
 

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