TopCoder problem "TheSwap" used in SRM 437 (Division I Level One , Division II Level Two)



Problem Statement

    

There is nothing more beautiful than just an integer number.

You are given an integer n. Write down n in decimal notation with no leading zeroes, and let M be the number of written digits. Perform the following operation exactly k times:

  • Choose two different 1-based positions, i and j, such that 1 <= i < j <= M. Swap the digits at positions i and j. This swap must not cause the resulting number to have a leading zero, i.e., if the digit at position j is zero, then i must be strictly greater than 1.

Return the maximal possible number you can get at the end of this procedure. If it's not possible to perform k operations, return -1 instead.

 

Definition

    
Class:TheSwap
Method:findMax
Parameters:int, int
Returns:int
Method signature:int findMax(int n, int k)
(be sure your method is public)
    
 

Constraints

-n will be between 1 and 1,000,000, inclusive.
-k will be between 1 and 10, inclusive.
 

Examples

0)
    
16375
1
Returns: 76315
The optimal way is to swap 1 and 7.
1)
    
432
1
Returns: 423
In this case the result is less than the given number.
2)
    
90
4
Returns: -1
We can't make even a single operation because it would cause the resulting number to have a leading zero.
3)
    
5
2
Returns: -1
Here we can't choose two different positions for an operation.
4)
    
436659
2
Returns: 966354

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10369

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13699&pm=10369

Writer:

Vasyl[alphacom]

Testers:

PabloGilberto , bmerry , ivan_metelsky

Problem categories:

Recursion, Simple Search, Iteration