TopCoder problem "ThePower" used in SRM 437 (Division II Level Three)



Problem Statement

    

There is nothing more beautiful than just an integer number.

You start with the integer 1 and you apply a sequence of operations until you reach the integer n. Each operation can be one of the following:

  • Increment the current number by 1.
  • If the current number is greater than 1, decrement it by 1.
  • Raise the current number to any positive integral power.

Return the minimum possible number of operations required to reach n.

 

Definition

    
Class:ThePower
Method:count
Parameters:long
Returns:int
Method signature:int count(long n)
(be sure your method is public)
    
 

Constraints

-n will be between 1 and 10^18, inclusive.
 

Examples

0)
    
8
Returns: 2
1. Increment by 1: 1 + 1 = 2.

2. Raise to the power of 3: 2^3 = 8.
1)
    
1
Returns: 0
We don't need any operations here.
2)
    
80
Returns: 4
1. Increment by 1: 1 + 1 = 2.

2. Increment by 1: 2 + 1 = 3.

3. Raise to the power of 4: 3^4 = 81.

4. Decrement by 1: 81 - 1 = 80.
3)
    
123456789
Returns: 2566

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13699&pm=10235

Writer:

Vasyl[alphacom]

Testers:

PabloGilberto , bmerry , ivan_metelsky

Problem categories:

Search