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

• 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;
}
};
```

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