How could we fix this algorithm to find the smallest number

Question

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]]>

Answer 1

Really, the question is : What makes that an edge case ? What are the general features of this specific example that we need to address ?

For example, an initial reaction might be "well, we're putting the zero up front, so resulting in a number with a smaller number of digits ...... so, solution is : check if we're moving a zero to the front" (and yes, that was my initial reaction ;) )

Bzzzzt, wrong ! That would only be solving THIS particular case, not the general.

For example, consider a test case : 439987, resulting in the smallest number 349987. But : was is solution "[349987, 1, 0]" (moving the 3), or "[349987, 0, 1]" (moving the 4) ?

By the terms of the challenge, it's the smallest index ("smallest i") - so the answer you want to generate is "[349987, 0, 1]"

This also doesn't have to be at the front ! For example, consider : 124356 - again, smallest number is 123456 - but that would be "[123456, 3, 4]" (moving the 4), not "[123456, 4, 3]" (moving the 3)

So, forget the fact that your failing case has a zero - that's irrelevant. What's important is the general rule :

If you have decided that the smallest number involves swapping around adjacent digits, then the solution is "smallest i" - ie, it is moving the (larger) digit back one spot, rather than moving the (smaller) digit forward.

EDIT TO ADD PSEUDOCODE

Before I do though, couple of points : Consider that example 124356, where the 3 and 4 swap places. Neither '3' nor '4' are the smallest digit in the number (which is the digit '1'), so you can't assume that it is always going to be the smallest digit that's going to move.

What this means is you are going to have to have a loop.

As soon as you talk about a loop, then all sorts of performance optimisations are possible - but I don't see that consideration as a factor in the challenge, so I'm not interested in that either.

So, with that in mind, pseudocode will be :

long minValue = MAX_LONG;
int fromIndex;
int toIndex;
for (int i=1; i < numDigits; i++) {    // Move digit from position i
    for (int j=0; j < i; j++) {        // Bring forward to position j
        if (digit[j] > digit[i]) {     // So long as it's smaller
            long value = <value of number after moving the digit>
            if (value < minValue) {
                minValue = value;

                if (j == i-1) {    // Adjacent digits? (as per last paragraph)
                    fromIndex = j;  // the move from the smaller index
                    toIndex = i;

                 } else {          // More general case, similar to what you wrote
                    fromIndex = i;
                    toIndex = j;
                 }
              }
          }
      }

Remember - the criteria is NOT that you identify the smallest digit that moves, but that you identify the smallest INDEX ("smallest i") that gives the smallest result.

Hope this helps :)

Answer 2

Second test is actually failing because you are working with string's. You'r algorithm will find minimum number 0 put it in front and therefore it create's following string: "029917" but since you are testing against a string with value "29917" test will fail. Your obtained number is lowest number you can get from provided digit's with the operation's you are allowed to do. Your approach is therefore here valid.

Edit: you can actualy improve your code with following. If minimum is only found at lowest index, i.e minimum is already first number then you should search for second minimum. If second minimum is again at second position already find 3rd minimum etc.. until you find N-th minimum which is not placed at it's lowest possible index and place it there. This is what 3rd test is actually testing. You will find number 2 as minimum number but since it's already at first position you should continue to find second minimum, number 3, and place it right after previous minimum you found and didn't have to move.