ThePower
SRM 437 · 2009-03-24 · by Vasyl[alphacom]
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.
Constraints
- n will be between 1 and 10^18, inclusive.
8 Returns: 2
1. Increment by 1: 1 + 1 = 2. 2. Raise to the power of 3: 2^3 = 8.
1 Returns: 0
We don't need any operations here.
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.
123456789 Returns: 2566
9 Returns: 3
Submissions are judged against all 78 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ThePower with a public method int count(long long n) · 78 test cases · 2 s / 256 MB per case