Next smaller number with the same digits in Java

The challenge

Write a function that takes a positive integer and returns the next smaller positive integer containing the same digits.

For example:

nextSmaller(21) == 12 nextSmaller(531) == 513 nextSmaller(2071) == 2017

Return -1 (for Haskell: return Nothing, for Rust: return None), when there is no smaller number that contains the same digits. Also return -1 when the next smaller number with the same digits would require the leading digit to be zero.

nextSmaller(9) == -1 nextSmaller(111) == -1 nextSmaller(135) == -1 nextSmaller(1027) == -1 // 0721 is out since we don't write numbers with leading zeros
Code language: JavaScript (javascript)
  • some tests will include very large numbers.
  • test data only employs positive integers.

The solution in Java

Option 1:

import java.util.Arrays; import java.util.Collections; import java.util.stream.Stream; public class Solution { public static long nextSmaller(long n) { Integer[] val = Long.toString(n).chars().map(c -> c - '0').boxed().toArray(Integer[]::new); int len = val.length; for (int i = len - 1; i > 0; i--) { if (val[i - 1] > val[i]) { int maxIdx = i; for (int j = i + 1; j < len; j++) { if (val[i - 1] > val[j] && val[j] > val[maxIdx]) maxIdx = j; } val[i - 1] = val[i - 1] + val[maxIdx]; val[i - 1] = val[i - 1] - (val[maxIdx] = val[i - 1] - val[maxIdx]); Arrays.sort(val, i, len, Collections.reverseOrder()); return val[0] == 0 ? - 1L : Long.valueOf(String.join("", Stream.of(val).map(String::valueOf).toArray(String[]::new))); } } return -1L; } }
Code language: Java (java)

Option 2:

public class Solution { public static long nextSmaller(long n) { final char[] cs = Long.toString(n).toCharArray(); for (int l = cs.length, p = l-1, i; 0 < (i = p); p--) { while (i < l && cs[i] < cs[p-1]) i++; if (p < i) return (p-1 == 0 && cs[i-1] == '0') ? -1 : Long.parseLong(new StringBuilder(l) .append(cs, p, i-1 - p).append(cs[p-1]) .append(cs, i, l - i).append(cs[i-1]) .reverse().insert(0, cs, 0, p-1).toString()); } return -1; } }
Code language: Java (java)

Option 3:

public class Solution { public static long nextSmaller(long n) { final char[] chars = Long.toString(n).toCharArray(); for (int i = chars.length; 0 < i; i--) { char digit = chars[i-1]; for (int j = i; j < chars.length; j++) { if (chars[j] < digit) { chars[i-1] = chars[j]; chars[j] = digit; return (chars[0] == '0') ? -1 : Long.parseLong(new String(chars)); } } System.arraycopy(chars, i, chars, i-1, chars.length - i); chars[chars.length-1] = digit; } return -1; } }
Code language: Java (java)

Test cases to validate our solution

import org.junit.Test; import static org.junit.Assert.assertEquals; import org.junit.runners.JUnit4; public class SolutionTests { @Test public void basicTests() { assertEquals(12, Solution.nextSmaller(21)); assertEquals(790, Solution.nextSmaller(907)); assertEquals(513, Solution.nextSmaller(531)); assertEquals(-1, Solution.nextSmaller(1027)); assertEquals(414, Solution.nextSmaller(441)); assertEquals(123456789, Solution.nextSmaller(123456798)); } }
Code language: Java (java)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments