**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)

## No comments:

## Post a Comment