O(log(log(n)) solution with C++ implementation


  • 1
    Y

    The algorithm is actually a binary search.

    1. We calculate 3^(2^i) from i=0, 1, ... until k, where 3^(2^k) is bigger than n, or 3^(2^(k+1)) overflows.
    2. Now we know log3(n) is in a range. The initial range is from 2^(k-1) to 2^k (or, in the overflow case, it is from 2^(k) to 2^(k+1)).. Then we record the lower limit of the range, and the length of the range.
    3. Every time we get the middle point of the range, "m", and calculate the 3^m (we can multiply the range's lower limit by 3^(2^i), which is a number we already computed in step 1) , and compare it to n. This will tell us which half of the current range we should use next. Therefore, we get a smaller range.
    4. Repeat 3 until we find a 3^m that equals n, or the range can no longer be split.

    The both space complexity and time are O(log(log(n)).

    class Solution {
    public:
        bool isPowerOfThree(int n) {
            if (!n) return false;
            if (n == 1) return true;
            int powers[5];
            int k = 0;
            powers[0] = 3;
            bool bigNumber = false;
            while (powers[k] < n) {
                int next = k + 1;
                if (next == 5) {
                    bigNumber = true;
                    break;
                }
                powers[next] = powers[k] * powers[k];
                k = next;
            }
    	if (powers[k] == n) {
    	    return true;
    	}
            if (k <= 1) {
                return false;
            }
            int range = bigNumber ? 2 /* trick */ : k - 1;
            int current = powers[bigNumber ? k : k - 1];
            do {
                --range;
                int mid = current * powers[range];
                if (mid == n) {
                    return true;
                }
                if (mid > 0 && mid < n) {
                    current = mid;
                }
            } while (range > 0);
            return false;
        }
    };
    

Log in to reply
 

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