The algorithm is actually a binary search.

- 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.
- 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.
- 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.
- 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; } };