LargestNotation | Topcoder Archive

Problem Statement

In base B, each digit has a value between 0 and B-1, inclusive. For example, the number 42 written in base 16 has two digits, and the values of those digits are 2 and 10 (42 = 2*16 + 10). Therefore, the sum of digits of the number 42 written in base 16 is 2 + 10 = 12.
You are given an int N. Consider the notations of N in bases 2, 3, ..., N-1. Compute and return the largest sum of digits among all these notations.

Definition

Class:: LargestNotation
Method:: maxDigitsSum
Parameters:: int
Returns:: int
Method signature:: int maxDigitsSum(int N)
(be sure your method is public)

Notes

In the example annotations we use subscripts to denote different bases. For example, 1110 represents the number eleven and 113 represents the number four written as 11 in ternary.

Constraints

N will be between 3 and 1,000,000, inclusive.

Examples

```
3
```
```
Returns: 2
```
The only valid base for N = 3 is 2. 310 = 112.
```
4
```
```
Returns: 2
```
There are two possible bases for N = 4: 2 and 3. 410 = 1002 = 113.
```
22
```
```
Returns: 11
```
```
1000000
```
```
Returns: 500000
```
```
12345
```
```
Returns: 6173
```

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.