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.
1
Returns: 1
7
Returns: 7
9
Returns: 9
10
Returns: 10
634
Returns: 634
10000
Returns: 10000
100000
Returns: 100000
13579
Returns: 86520
12398
Returns: 87301
11999
Returns: 88900
79698
Returns: 89765
57246
Returns: 65410
87539
Returns: 88640
79268
Returns: 87612
75469
Returns: 86540
79815
Returns: 87540
68247
Returns: 76510
59147
Returns: 86400
68744
Returns: 76444
79186
Returns: 87620
19708
Returns: 87004
57146
Returns: 65400
61428
Returns: 75100
28645
Returns: 75410
19667
Returns: 86603
75339
Returns: 86430
62748
Returns: 76510
75469
Returns: 86540
51472
Returns: 64100
18767
Returns: 76703
79875
Returns: 87650
49263
Returns: 85300
68743
Returns: 76443
19607
Returns: 86003
87169
Returns: 88603
18425
Returns: 74100
68744
Returns: 76444
69247
Returns: 86510
95818
Returns: 97830
39781
Returns: 87711
50216
Returns: 50511
31279
Returns: 86202
52252
Returns: 54212
89646
Returns: 89653
27027
Returns: 67021
35040
Returns: 43010
46215
Returns: 54212
93039
Returns: 98032
45747
Returns: 66443
80920
Returns: 80920
43069
Returns: 85030
86357
Returns: 86652
55568
Returns: 75564
95
Returns: 95
87088
Returns: 87088
80110
Returns: 80110
53877
Returns: 76632
30105
Returns: 40102
16897
Returns: 87620
61334
Returns: 63330
93051
Returns: 94021
36492
Returns: 86422
69506
Returns: 85506
37004
Returns: 63001
38843
Returns: 78320
66268
Returns: 76560
46292
Returns: 86302
69438
Returns: 87531
17711
Returns: 67011
88850
Returns: 88850
38601
Returns: 75101
86041
Returns: 86041
68961
Returns: 88561
76977
Returns: 86677
97890
Returns: 98860
30056
Returns: 50052
35898
Returns: 87840
41374
Returns: 63330
592247
Returns: 864210
697352
Returns: 864422
668744
Returns: 766444
697635
Returns: 865432
487599
Returns: 888640
462315
Returns: 543010
475499
Returns: 886440
182567
Returns: 765100
631589
Returns: 875200
747235
Returns: 764300
162425
Returns: 542100
695843
Returns: 875443
690835
Returns: 870442
482263
Returns: 753200
185227
Returns: 761201
531476
Returns: 654100
275847
Returns: 776410
753490
Returns: 864400
297445
Returns: 864410
528796
Returns: 876510
1000000
Returns: 1000000
700000
Returns: 700000
102121
Returns: 102121
999999
Returns: 999999
898898
Returns: 898898
888998
Returns: 888998
989989
Returns: 989989
988999
Returns: 988999
998898
Returns: 998898
889977
Returns: 889977
811497
Returns: 886400
757874
Returns: 777634
156211
Returns: 550211
952641
Returns: 955301
244154
Returns: 444310
660444
Returns: 660444
389818
Returns: 887811
726955
Returns: 866420
528545
Returns: 744541
701435
Returns: 704430
345210
Returns: 442210
140096
Returns: 850010
377374
Returns: 677331
866183
Returns: 876500
549512
Returns: 844512
681697
Returns: 886650
967567
Returns: 967664
573130
Returns: 643200
867089
Returns: 887085
599857
Returns: 897652
426
Returns: 530
678999
Returns: 888965
537
Returns: 641
912349
Returns: 983310
888888
Returns: 888888
456789
Returns: 876743
648
Returns: 752
529
Returns: 840
989798
Returns: 989875
183043
Returns: 733000
999989
Returns: 999989
685193
Returns: 885500
6409
Returns: 8502
527
Returns: 640
919
Returns: 980
945679
Returns: 986643
199
Returns: 890
99913
Returns: 99920
3299
Returns: 8821
709
Returns: 806
193333
Returns: 823300
447249
Returns: 863340
763482
Returns: 775412
739
Returns: 861
9166
Returns: 9560
753009
Returns: 864000
517836
Returns: 765400
599
Returns: 894
735437
Returns: 765432