Reorder numbers in a int number to get minimum value

Question

How can I reorder numbers in a int number to get minimum value. Ex: I input a number: $71440 and I want my output is: $1447 (this is minimum value after reordering). I think I will spits the numbers in my input number first like this , after that I will reorder them. That is good algorithm?

Possible duplicate of [Ukkonen's suffix tree algorithm in plain English](https://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english) — user234461, Apr 05 '18 at 13:58
And I got 2 devote because you guys think this question is dup? — Minh Thanh, Apr 05 '18 at 14:19
You probably got the downvotes because you haven't shown that you tried anything before asking the question. To make it better you should have included whatever code you had written to try to solve the problem. — Diasiare, Apr 05 '18 at 14:26
Got it, my mistake. I just think this is almost Algorithm problem, no need to show my code. I will not do like that in the next question. Thanks for your explaining — Minh Thanh, Apr 05 '18 at 14:31

score 2 · Answer 1 · answered Apr 05 '18 at 13:57

2

Yes it is good if you

split by digit
sort digits
make number out of those digits

answered Apr 05 '18 at 13:57

Bartosz Bilicki

12,599
13
71
113

After each splitting, must I append it into a arrays of int, then sort array? Can I do that in Java? – Minh Thanh Apr 05 '18 at 14:00
@MinhThanh yes, you can sort an array of ints in java with `Arrays.sort()` – kyriakosSt Apr 05 '18 at 14:02
@KyrSt Bucket sort will be a lot faster for big numbers. – Dave Apr 05 '18 at 14:20

score 0 · Answer 2 · answered Apr 05 '18 at 14:00

0

What you need is essentially a sorting of the digits of the number. So yes, your proposed method will work and it seems as a reasonable practice.

answered Apr 05 '18 at 14:00

kyriakosSt

1,754
2
15
33

Thanks for your comment – Minh Thanh Apr 05 '18 at 14:24

score 0 · Answer 3 · answered Apr 05 '18 at 14:04

I think this does roughly what you want it to do. Assumes that the input is positive, I'm sure you can figure out how to modify it to work with negative numbers if you need that.

public static int leastValue(int input) {
    String s = Integer.toString(input);
    char[] c = s.toCharArray();
    Arrays.sort(c);
    s = new String(c);   
    return Integer.parseInt(s);
}

The basic idea is:

Turn value into a string
Put each character into an array
Sort the array of characters, in most character sets this will order the numbers from smallest to largest.
Turn it into a string again
Parse it into an int

The sort order of `char` is such that the zeros will end up at the begining of the number in string form. So for `"71440"` you will get `"01447"`. `Integer.parseInt` will skip the leading zeros. — Diasiare, Apr 05 '18 at 14:24

score 0 · Answer 4 · answered Apr 05 '18 at 14:15

For readability I think Diasiares answer is better. However a different approach would be something like this. It sorts a long with a "merge sort like" algorithm. To understand how it works please view the gif file from wikipedia

public static long sort(long num) {
    long res;
    if (num > 9) {
        //split num into two parts(n1, n2)
        int numberOfDigits = (int) Math.log10(num) + 1;
        long n1 = num / (long) Math.pow(10, numberOfDigits / 2);
        long n2 = num % (long) Math.pow(10, numberOfDigits / 2);

        //sort each part
        long s1 = sort(n1);
        long s2 = sort(n2);

        //merge them into one number
        res = merge(s1, s2);
    } else {
        res = num;
    }
    return res;
}

/**
 * merges two sorted long into on long e.g 149 and 345 will give 134459
 */
public static long merge(long num1, long num2) {
    return (num1 == 0 || num2 == 0)
            ? num1 + num2
            : num1 % 10 < num2 % 10
                    ? num2 % 10 + merge(num1, num2 / 10) * 10
                    : num1 % 10 + merge(num1 / 10, num2) * 10;
}

Reorder numbers in a int number to get minimum value

4 Answers4