TopCoder problem "PowerOfInteger" used in TCCC07 Round 2 (Division I Level One)



Problem Statement

    

A number y is said to be the k-th power of a number x if y = x^k, i.e., y is the product of k copies of x.

You are given two Strings left and right. Return the greatest k such that there is an integer y (left <= y <= right) such that y is the k-th power of some integer x.

 

Definition

    
Class:PowerOfInteger
Method:greatestPower
Parameters:String, String
Returns:int
Method signature:int greatestPower(String left, String right)
(be sure your method is public)
    
 

Constraints

-left will be an integer between 2 and 10^12, inclusive, without extra leading zeroes.
-right will be an integer between left and 10^12, inclusive, without extra leading zeroes.
 

Examples

0)
    
"5"
"20"
Returns: 4
The greatest power between 5 and 20 is 16=2^4.
1)
    
"10"
"12"
Returns: 1
No nontrivial power of integer between 10 and 12, so return 1.
2)
    
"2"
"100"
Returns: 6
3)
    
"1000000000000"
"1000000000000"
Returns: 12

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7554

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10891&pm=7554

Writer:

andrewzta

Testers:

PabloGilberto , radeye , Olexiy , ivan_metelsky

Problem categories:

Math, Search, Simple Math