Exponents | Topcoder Archive

Problem Statement

A certain compiler would like to build in an exponentiation operand, '^'. It will only work with positive integer powers though, and in order to make the compiled code as fast as possible, the compiler writers will have to generate code with as few multiplications as possible, assuming that any intermediate results can be stored for later use. For examples, x^7 can be calculated in 4 multiplications. The first is x*x, which gives us ^2. Then we multiply x^2 by itself and get x^4. Then we multiply x^4 by x^2, and multiply the result by x.

Your task is to write a class Exponents, with a method fastest, which determines the fewest multiplications required to raise a number to a given power.

Definition

Class:: Exponents
Method:: fastest
Parameters:: int
Returns:: int
Method signature:: int fastest(int power)
(be sure your method is public)

Notes

Assume that division is prohibitively expensive. So, for example, x^63 would never be calculated as x^64 / x, even though this would be 1 less operation than the optimal sequence of multiplications (see example 3).

Constraints

power will be a positive (non-zero) number.
To attain the given power, between zero and ten multiplications will be required, inclusive.

Examples

```
2
```
```
Returns: 1
```
x^2 can be obtained with 1 multiplication.
```
6
```
```
Returns: 3
```
x^6 can be obtained in 3 multiplications, in a number of ways. One way is to square x giving us x^2. Then multiply x^2 by x to get x^3.x^3 * x^3 = x^6, for a total of 3 multiplications.
```
63
```
```
Returns: 8
```
```
127
```
```
Returns: 10
```
```
151
```
```
Returns: 10
```

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.