ThePower | Topcoder Archive

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

```
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
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.