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.