We would like to find the smallest number created from the digits of a given long.
We are doing the following programming task: https://www.codewars.com/kata/573992c724fc289553000e95
You have a positive number n consisting of digits. You can do at most one operation: Choosing the index of a digit in the number, remove this digit at that index and insert it back to another or at the same place in the number in order to find the smallest number you can get.
#Task: Return an array or a tuple or a string depending on the language (see "Sample Tests") with
1) the smallest number you got
2) the index i of the digit d you took, i as small as possible
3) the index j (as small as possible) where you insert this digit d to have the smallest number.
Example:
smallest(261235) --> [126235, 2, 0] or (126235, 2, 0) or "126235, 2, 0"
126235 is the smallest number gotten by taking 1 at index 2 and putting it at index 0
smallest(209917) --> [29917, 0, 1] or ...
[29917, 1, 0] could be a solution too but index `i` in [29917, 1, 0] is greater than
index `i` in [29917, 0, 1].
29917 is the smallest number gotten by taking 2 at index 0 and putting it at index 1 which gave 029917 which is the number 29917.
smallest(1000000) --> [1, 0, 6] or ...
-> We have written:
public class ToSmallest {
public static long[] smallest /**/ (long n) {
System.out.println("\n\nn: "+n);
StringBuilder input = new StringBuilder(String.valueOf(n));
long min = Long.MAX_VALUE;
int minIndex = -1;
//We find the minimum and its index
for(int i=input.length()-1; n>0; i--){
long digit = n%10;
if(min!=Math.min(min,digit)){
minIndex='\0'+i;
}
min = Math.min(min, digit);
n /= 10;
}
System.out.println("min: "+min);
System.out.println("minIndex: "+minIndex);
//We put the minimum as first digit
input = input.deleteCharAt(minIndex);
System.out.println("input: "+input);
input = input.insert(0,min);
System.out.println("input: "+input);
return new long[]{Long.parseLong(input.toString()),minIndex,0};
}
}
We think that is is incomplete because of we are assuming that in all cases we could create the minimum by:
1) Find the min digit
2) Remove it from where it was
3) Insert it at start
However, being the unit tests:
import static org.junit.Assert.*;
import java.util.Arrays;
import org.junit.Test;
public class ToSmallestTest {
private static void testing(long n, String res) {
assertEquals(res,
Arrays.toString(ToSmallest.smallest(n)));
}
@Test
public void test() {
System.out.println("Basic Tests smallest");
testing(261235, "[126235, 2, 0]");
testing(209917, "[29917, 0, 1]");
testing(285365, "[238565, 3, 1]");
testing(269045, "[26945, 3, 0]");
testing(296837, "[239687, 4, 1]");
}
}
-> The code is failing at the second test.
How could we improve the algorithm?
EDIT: After reading Norbert Dopjera's answer we have tried:
public class ToSmallest {
public static long[] smallest (long n) {
System.out.println("\n\nn: "+n);
StringBuilder input = new StringBuilder(String.valueOf(n));
long min = Long.MAX_VALUE;
int minIndex = -1;
int numberMinsFound = -1; //
//We find the minimum and its index
while(numberMinsFound == minIndex){ //
for(int i=input.length()-1; n>0; i--){
long digit = n%10;
if(min!=Math.min(min,digit)){
minIndex='\0'+i;
}
min = Math.min(min, digit);
n /= 10;
numberMinsFound++; //
}
}
System.out.println("min: "+min);
System.out.println("minIndex: "+minIndex);
//We put the minimum as first digit
input = input.deleteCharAt(minIndex);
System.out.println("input: "+input);
input = input.insert(0,min);
System.out.println("input: "+input);
return new long[]{Long.parseLong(input.toString()),minIndex,0};
}
}
However it stills being wrong with the second test:
n: 209917
min: 0
minIndex: 1
input: 29917
input: 029917
expected:<[29917, [0, 1]]> but was:<[29917, [1, 0]]>