Find the Super Cool Number

Problem: A Super Cool number is a nature number which can be represented as a^b (a and b are both nature number and b>1. Given a nature number N, find the super cool number that is closest to N.

Solution: The key is to know the upper bound of the exponent, ceiling (log_2_(N)). If we have functions such as log(), then it is easy. Otherwise, we need to guess an upper bound, we can use N/2.  Then we do a series of binary search,

• find a value n between 1 and N such that n^exponent is closest to N.
• for all the possible exponent, repeat the previous step.
• binary search over the exponent is quicker than search over the base (i.e., 1~N)

Then the total complexity is around O(logN*logN).