RemissiveSwaps | Topcoder Archive

Problem Statement

You are given an integer N, and you are allowed to perform the following operation: take two nonzero digits of N, decrease each of them by one and swap the resulting digits. For example, if N is 166, you can reach the following numbers in one operation: 506 (swap '1' and the first '6'), 155 (swap the '6's) and 560 (swap '1' and the last '6'). You are allowed to perform the operation zero or more times consecutively. Return the largest number you can reach.

Definition

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

Constraints

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

Examples

```
166
```
```
Returns: 560
```
The example from the problem statement.
```
3499
```
```
Returns: 8832
```
The following sequence of operations is optimal: 3499 -> 8492 -> 8832.
```
34199
```
```
Returns: 88220
```
The following sequence of operations is optimal: 34199 -> 84129 -> 88123 -> 88220.
```
809070
```
```
Returns: 809070
```
No operations can increase the number.

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.