Statistics

Problem Statement for "TheSwap"

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 &lt= i &lt j &lt= 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

  1. 16375

    1

    Returns: 76315

    The optimal way is to swap 1 and 7.

  2. 432

    1

    Returns: 423

    In this case the result is less than the given number.

  3. 90

    4

    Returns: -1

    We can't make even a single operation because it would cause the resulting number to have a leading zero.

  4. 5

    2

    Returns: -1

    Here we can't choose two different positions for an operation.

  5. 91

    3

    Returns: 19

  6. 65

    7

    Returns: 56

  7. 45

    7

    Returns: 54

  8. 757148

    1

    Returns: 857147

  9. 301413

    5

    Returns: 433110

  10. 659598

    6

    Returns: 998655

  11. 391749

    2

    Returns: 997143

  12. 35766

    3

    Returns: 76653

  13. 473038

    7

    Returns: 874330

  14. 3615

    7

    Returns: 6531

  15. 392289

    3

    Returns: 998322

  16. 100757

    1

    Returns: 700751

  17. 401413

    1

    Returns: 441013

  18. 759598

    2

    Returns: 997558

  19. 491749

    2

    Returns: 997144

  20. 135766

    1

    Returns: 735166

  21. 900757

    9

    Returns: 977500

  22. 901413

    9

    Returns: 943110

  23. 959598

    10

    Returns: 999855

  24. 991749

    10

    Returns: 999741

  25. 935766

    9

    Returns: 976653

  26. 999996

    1

    Returns: 999996

  27. 999992

    5

    Returns: 999992

  28. 999990

    6

    Returns: 999990

  29. 999997

    2

    Returns: 999997

  30. 1000000

    3

    Returns: 1000000

  31. 1000000

    1

    Returns: 1000000

  32. 1000000

    10

    Returns: 1000000

  33. 999999

    10

    Returns: 999999

  34. 999999

    1

    Returns: 999999

  35. 2199

    2

    Returns: 9921

  36. 1299

    2

    Returns: 9921

  37. 543219

    10

    Returns: 954312

  38. 543219

    6

    Returns: 954312

  39. 543219

    4

    Returns: 954312

  40. 543219

    5

    Returns: 954321

  41. 70

    8

    Returns: -1

  42. 10

    1

    Returns: -1

  43. 4

    7

    Returns: -1

  44. 33445

    3

    Returns: 54433

  45. 5

    1

    Returns: -1

  46. 436659

    2

    Returns: 966354

  47. 436659

    10

    Returns: 966543

  48. 21996

    2

    Returns: 99216

  49. 579201

    7

    Returns: 975201

  50. 194523

    10

    Returns: 954312

  51. 87993

    2

    Returns: 99873

  52. 331

    2

    Returns: 331

  53. 800

    3

    Returns: 800

  54. 123456

    10

    Returns: 654312

  55. 120000

    10

    Returns: 210000

  56. 30199

    2

    Returns: 99130

  57. 721865

    10

    Returns: 876512

  58. 10033

    2

    Returns: 33010

  59. 6399

    2

    Returns: 9963

  60. 100

    2

    Returns: 100

  61. 436659

    4

    Returns: 966543

  62. 8699

    2

    Returns: 9986

  63. 967983

    7

    Returns: 998763

  64. 101

    2

    Returns: 110

  65. 665

    1

    Returns: 665

  66. 654321

    9

    Returns: 654312

  67. 10022

    2

    Returns: 22010

  68. 1022

    2

    Returns: 2210

  69. 3445

    2

    Returns: 5443

  70. 120

    1

    Returns: 210

  71. 1000

    1

    Returns: 1000

  72. 3221

    1

    Returns: 3221

  73. 900

    10

    Returns: 900

  74. 10000

    1

    Returns: 10000

  75. 765432

    10

    Returns: 765432

  76. 332

    1

    Returns: 332

  77. 992307

    9

    Returns: 997320

  78. 100

    1

    Returns: 100

  79. 986541

    10

    Returns: 986541

  80. 1000000

    2

    Returns: 1000000

  81. 6577

    2

    Returns: 7765

  82. 654332

    9

    Returns: 654332

  83. 122

    2

    Returns: 221

  84. 554321

    1

    Returns: 554321

  85. 1234

    5

    Returns: 4312

  86. 1000000

    8

    Returns: 1000000

  87. 999999

    2

    Returns: 999999

  88. 9000

    3

    Returns: 9000

  89. 1000000

    5

    Returns: 1000000

  90. 100

    10

    Returns: 100

  91. 325664

    2

    Returns: 665324

  92. 5000

    4

    Returns: 5000

  93. 512939

    2

    Returns: 992531

  94. 991

    1

    Returns: 991

  95. 99999

    10

    Returns: 99999

  96. 90000

    4

    Returns: 90000

  97. 109

    3

    Returns: 901

  98. 311222

    10

    Returns: 322211

  99. 436659

    7

    Returns: 966543

  100. 970903

    7

    Returns: 997300

  101. 967845

    10

    Returns: 987654

  102. 849769

    2

    Returns: 998764

  103. 12

    1

    Returns: 21

  104. 3321

    1

    Returns: 3321

  105. 76455

    2

    Returns: 76554

  106. 456789

    10

    Returns: 987645

  107. 951491

    10

    Returns: 995411

  108. 16373

    2

    Returns: 76331

  109. 897654

    9

    Returns: 987654

  110. 10000

    10

    Returns: 10000

  111. 900

    1

    Returns: 900

  112. 1000

    2

    Returns: 1000

  113. 10000

    3

    Returns: 10000

  114. 2000

    2

    Returns: 2000

  115. 53662

    2

    Returns: 66532

  116. 1252

    6

    Returns: 5221

  117. 9443

    1

    Returns: 9443

  118. 626

    1

    Returns: 662

  119. 544321

    1

    Returns: 544321

  120. 1001

    1

    Returns: 1100

  121. 900

    4

    Returns: 900

  122. 6477

    2

    Returns: 7764

  123. 436659

    5

    Returns: 966543

  124. 21772

    2

    Returns: 77212

  125. 440

    1

    Returns: 440

  126. 12

    5

    Returns: 21

  127. 909

    2

    Returns: 990

  128. 10

    2

    Returns: -1

  129. 919

    1

    Returns: 991

  130. 32888

    2

    Returns: 88832

  131. 1000000

    6

    Returns: 1000000

  132. 1000

    7

    Returns: 1000

  133. 11100

    1

    Returns: 11100

  134. 12345

    10

    Returns: 54321

  135. 101

    3

    Returns: 110

  136. 987654

    9

    Returns: 987645

  137. 984566

    2

    Returns: 986654

  138. 101128

    4

    Returns: 821110

  139. 4332

    1

    Returns: 4332

  140. 987654

    10

    Returns: 987654

  141. 9000

    1

    Returns: 9000

  142. 200

    1

    Returns: 200

  143. 500

    1

    Returns: 500

  144. 100

    9

    Returns: 100

  145. 198765

    10

    Returns: 987615

  146. 400

    1

    Returns: 400

  147. 90

    1

    Returns: -1

  148. 2199

    9

    Returns: 9921

  149. 4366

    2

    Returns: 6643

  150. 101

    1

    Returns: 110

  151. 723623

    9

    Returns: 763322

  152. 1000

    10

    Returns: 1000

  153. 91

    2

    Returns: 91

  154. 109

    1

    Returns: 901

  155. 552

    1

    Returns: 552

  156. 439494

    3

    Returns: 994443

  157. 22222

    10

    Returns: 22222

  158. 999990

    10

    Returns: 999990

  159. 9661

    1

    Returns: 9661

  160. 40000

    1

    Returns: 40000

  161. 9910

    1

    Returns: 9910

  162. 9000

    2

    Returns: 9000

  163. 312

    2

    Returns: 312

  164. 661

    2

    Returns: 661

  165. 9810

    1

    Returns: 9801

  166. 123345

    3

    Returns: 543321

  167. 983472

    9

    Returns: 987432

  168. 25

    5

    Returns: 52

  169. 210

    1

    Returns: 201

  170. 901421

    10

    Returns: 942110

  171. 978909

    5

    Returns: 999870

  172. 99

    3

    Returns: 99

  173. 432

    2

    Returns: 432

  174. 234

    2

    Returns: 423

  175. 165432

    10

    Returns: 654312

  176. 30000

    2

    Returns: 30000

  177. 222222

    10

    Returns: 222222

  178. 5552

    1

    Returns: 5552

  179. 983657

    9

    Returns: 987653

  180. 12345

    4

    Returns: 54321

  181. 654321

    7

    Returns: 654312

  182. 985466

    2

    Returns: 986654

  183. 466639

    3

    Returns: 966643

  184. 510

    1

    Returns: 501

  185. 50

    1

    Returns: -1

  186. 3166

    2

    Returns: 6631

  187. 9921

    1

    Returns: 9921

  188. 636

    1

    Returns: 663

  189. 700

    1

    Returns: 700

  190. 4402

    1

    Returns: 4420

  191. 31188

    2

    Returns: 88131

  192. 90000

    2

    Returns: 90000

  193. 6263

    1

    Returns: 6623

  194. 2155

    2

    Returns: 5521

  195. 10000

    2

    Returns: 10000

  196. 22

    6

    Returns: 22

  197. 661

    1

    Returns: 661

  198. 512909

    2

    Returns: 992501

  199. 3456

    7

    Returns: 6534

  200. 8799

    2

    Returns: 9987

  201. 10000

    5

    Returns: 10000

  202. 9818

    2

    Returns: 9881

  203. 23

    3

    Returns: 32

  204. 231268

    9

    Returns: 863221

  205. 849991

    3

    Returns: 999841

  206. 982313

    3

    Returns: 983321

  207. 2055

    2

    Returns: 5520

  208. 436659

    9

    Returns: 966543

  209. 123

    3

    Returns: 321

  210. 1055

    2

    Returns: 5510

  211. 321000

    1

    Returns: 321000

  212. 654321

    6

    Returns: 654321

  213. 354

    6

    Returns: 543

  214. 476890

    4

    Returns: 987604

  215. 123321

    3

    Returns: 332211

  216. 1000000

    4

    Returns: 1000000

  217. 11

    1

    Returns: 11

  218. 100000

    8

    Returns: 100000

  219. 100000

    1

    Returns: 100000

  220. 13

    10

    Returns: 13

  221. 6000

    4

    Returns: 6000

  222. 135790

    10

    Returns: 975310

  223. 89

    3

    Returns: 98

  224. 12

    3

    Returns: 21

  225. 362858

    3

    Returns: 886352

  226. 96632

    1

    Returns: 96632

  227. 987656

    4

    Returns: 987665

  228. 110

    1

    Returns: 110

  229. 481102

    8

    Returns: 842110

  230. 3312

    1

    Returns: 3321

  231. 25536

    3

    Returns: 65532

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.
This problem was used for: