Solution to Problem 4

Let's talk a little bit about the Problem 4 presented in last night's post. This wasn't the most difficult of the problems (Problem 5 was), but it was interesting enough to get several people thinking about it for a while.

Here is the problem:

Write a function that given a list of non negative integers, arranges them such that they form the largest possible number. For example, given [50, 2, 1, 9], the largest formed number is 95021.

A lot of folks have rightly pointed out that this problem can be solved using a lexical comparison of strings. However, that's not all you need.

Consider the following example: [5, 50, 56]. A lexical comparison returns 56, 50, and 5, but that doesn't make the larger number (56, 5, 50 does). To solve this problem, you need to make sure all values have the same length (so 5 acts like 50 when compared to 56, or 2 acts like 200 when compared to 123.) A couple of people found that padding with zeros does not provide a valid solution for some combinations, so I went back to the drawing board and came up with this new solution:

import java.util.Arrays;
import java.util.Comparator;

public class Main {

    private static Integer[] VALUES = { 5, 2, 1, 9, 50, 56 };

    public static void main(String[] args) {
        Arrays.sort(VALUES, new Comparator() {

            @Override
            public int compare(Integer lhs, Integer rhs) {
                String v1 = lhs.toString();
                String v2 = rhs.toString();

                return (v1 + v2).compareTo(v2 + v1) * -1;
            }
        });

        String result = "";
        for (Integer integer : VALUES) {
            result += integer.toString();
        }

        System.out.println(result);
    }   
}    

(Thanks to everyone that tried to solve the problem and got back to me. I really appreciate it!)

What do you think?

Update: More about the padding solution

I've gotten a lot of messages saying that padding the numbers with the last digit (instead of 0) is also a solution. For example, to compare 5 and 56, you can pad 5 with the same digit to turn it into 55. To compare 51 and 123, you can pad 51 with 1 to make it 511.

Although it seems that it would work, it actually doesn't. As pointed to me by Kevin Tran, the padding solution for [420, 42, 423] returns 42342420 which is wrong (it should be 42423420).

Update: More programming challenges

I love these type of programming problems. I'm going to try to publish one problem every weekend, hoping I'll have the time to find a good one and solve it myself. Here is the first one to celebrate Mother's Day: Programming challenge: rotating a matrix 90 degrees in place.

Please, get in touch with me and send me your favorite challenges.

Have something to say about this post? Get in touch!

Want to read more? Visit the archive.