fork(1) download
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. // Problem Description:
  6. // Reorder the digits of a number, in order to
  7. // get the least one which is greater than the input number
  8.  
  9. class Ideone
  10. {
  11. public static String getLeastGreaterNumber(String number) {
  12. List<Character> decreasingChars = new ArrayList();
  13. int firstDecreasing = getDecreasingChars(number, decreasingChars);
  14.  
  15. if(isGreatestNumber(firstDecreasing)) {
  16. return "";
  17. }
  18.  
  19. String prefix = "";
  20. if(firstDecreasing > 1) {
  21. prefix = number.substring(0, firstDecreasing - 1);
  22. }
  23.  
  24. StringBuilder resultBuilder = new StringBuilder(prefix);
  25.  
  26. char target = number.charAt(firstDecreasing - 1);
  27. char leastGreater = swapLeastGreater(decreasingChars, target);
  28. resultBuilder.append(leastGreater);
  29.  
  30. Collections.sort(decreasingChars);
  31. appendList(resultBuilder, decreasingChars);
  32.  
  33. return resultBuilder.toString();
  34. }
  35.  
  36. private static Boolean isGreatestNumber(int firstDecreasing) {
  37. return firstDecreasing == 0;
  38. }
  39.  
  40. private static int getDecreasingChars(String number, List<Character> decreasing) {
  41. int firstDecreasing = number.length() - 1;
  42.  
  43. for(; firstDecreasing > 0; --firstDecreasing) {
  44. char curChar = number.charAt(firstDecreasing);
  45. char preChar = number.charAt(firstDecreasing - 1);
  46. decreasing.add(curChar);
  47.  
  48. if(curChar > preChar) {
  49. break;
  50. }
  51. }
  52.  
  53. return firstDecreasing;
  54. }
  55.  
  56. private static char swapLeastGreater(List<Character> chars, char target) {
  57. Iterator it=chars.iterator();
  58. char finding = '9';
  59. while(it.hasNext()) {
  60. char value = ((Character)it.next()).charValue();
  61. if(value > target && value < finding) {
  62. finding = value;
  63. }
  64. }
  65.  
  66. chars.remove(new Character(finding));
  67. chars.add(new Character(target));
  68.  
  69. return finding;
  70. }
  71.  
  72. private static void appendList(StringBuilder str, List<Character> chars) {
  73. Iterator it=chars.iterator();
  74. while(it.hasNext()) {
  75. char value = ((Character)it.next()).charValue();
  76. str.append(value);
  77. }
  78. }
  79.  
  80. //////////////////////////////////////////////////////////////
  81. // Test Code Begins
  82. //////////////////////////////////////////////////////////////
  83. private static void test(String number, String expected) {
  84. String result = getLeastGreaterNumber(number);
  85. if(result.equals(expected)) {
  86. System.out.println("Test passed with number " + number);
  87. }
  88. else {
  89. System.out.println("Test FAILED with number " + number);
  90. }
  91. }
  92.  
  93. private static void test1() {
  94. String number = "38276";
  95. String expected = "38627";
  96. test(number, expected);
  97. }
  98.  
  99. private static void test2() {
  100. String number = "34722641";
  101. String expected = "34724126";
  102. test(number, expected);
  103. }
  104.  
  105. private static void test3() {
  106. String number = "12345";
  107. String expected = "12354";
  108. test(number, expected);
  109. }
  110.  
  111. private static void test4() {
  112. String number = "987654";
  113. String expected = "";
  114. test(number, expected);
  115. }
  116.  
  117. private static void test5() {
  118. String number = "6";
  119. String expected = "";
  120. test(number, expected);
  121. }
  122.  
  123. private static void test6() {
  124. String number = "111111";
  125. String expected = "";
  126. test(number, expected);
  127. }
  128.  
  129. private static void test7() {
  130. String number = "111222333";
  131. String expected = "111223233";
  132. test(number, expected);
  133. }
  134.  
  135. private static void test8() {
  136. String number = "333222111";
  137. String expected = "";
  138. test(number, expected);
  139. }
  140.  
  141. private static void test9() {
  142. String number = "8987654321";
  143. String expected = "9123456788";
  144. test(number, expected);
  145. }
  146.  
  147. public static void main (String[] args) {
  148. test1();
  149. test2();
  150. test3();
  151. test4();
  152. test5();
  153. test6();
  154. test7();
  155. test8();
  156. test9();
  157. }
  158. }
Success #stdin #stdout 0.08s 380160KB
stdin
Standard input is empty
stdout
Test passed with number 38276
Test passed with number 34722641
Test passed with number 12345
Test passed with number 987654
Test passed with number 6
Test passed with number 111111
Test passed with number 111222333
Test passed with number 333222111
Test passed with number 8987654321