-
Notifications
You must be signed in to change notification settings - Fork 2
/
Kata.java
69 lines (60 loc) · 1.88 KB
/
Kata.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import java.util.*;
public class Kata {
public static long nextSmaller(long n) {
// convert to array of ints
char[] chars = Long.toString(n).toCharArray();
int[] ints = new int[chars.length];
for (int i = 0; i < chars.length; i++) {
ints[i] = Character.digit(chars[i], 10);
}
// iterate through the digits from right to left
// at each iteration try to find the largest digit to the right
// that is smaller than the current digit
int startingIndex = ints.length - 1;
for (int i = ints.length - 2; i >= 0; i--) {
// Don't allow 0 to be a max when comparing for the first digit
// This stops leading zero issues
int max = i == 0 ? 0 : Integer.MIN_VALUE;
int maxIndex = -1;
for (int j = i + 1; j < ints.length; j++) {
// find and save max less than ints[i]
if (ints[j] > max && ints[j] < ints[i]) {
max = ints[j];
maxIndex = j;
}
}
// If we found a digit swap and break out of the loop.
if (maxIndex >= 0) {
// Swap
int temp = ints[maxIndex];
ints[maxIndex] = ints[i];
ints[i] = temp;
// Update startingIndex
startingIndex = i;
break;
}
}
// Now sort the remainign digits descending to get the largest
// number that is less than n
for (int i = startingIndex + 1; i < ints.length - 1; i++) {
int max = ints[i];
int sortIndex = i;
for (int j = i; j < ints.length; j++) {
if (ints[j] > max) {
max = ints[j];
sortIndex = j;
}
}
int temp = ints[i];
ints[i] = max;
ints[sortIndex] = temp;
}
// Convert back to a long and return
String newNum = "";
for (int i = 0; i < ints.length; i++) {
newNum += ints[i];
}
long newValue = Long.valueOf(newNum);
return newValue == n ? -1 : newValue;
}
}