Write a function that given a list of non negative integers, arranges them such that they form the largest possible number

Question

My Problem

I have the following spec:

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.

My Results

I have taken a stab at a solution to the problem, but it fails. For example, given the input [90,91,89,999] the result of this code is [909199989], but it should have been [999919089].

A Description of My Algorithm

In simple words it is a reverse of radix sort.

Steps
1) Based on the values create buckets.
2) Each bucket has list of elements.
3) Sort the list in each bucket.
4) Display the result in the reverse order.

My code

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Scanner;

public class ReverseMaxPossibleNumber {
    public static void main(String[] args) {
        int[] a = { 50, 2, 1, 9 };
        int len = a.length;
        String ch = "";
        List<Map<String, ArrayList<String>>> list_map = new ArrayList<Map<String, ArrayList<String>>>();
        Map<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        for (int i = 0; i < len; i++) {
            ch = "" + a[i];
            String str = "";
            ArrayList<String> arraylist = new ArrayList<String>();
            for (int j = 0; j < len; j++) {
                str = "" + a[j];
                if (ch.charAt(0) == str.charAt(0)) {
                    arraylist.add(str);
                    Collections.sort(arraylist);
                    map.put("" + ch.charAt(0), arraylist);
                }
            }
        }
        list_map.add(map);
        String str = "";
        for (String key : map.keySet()) {
            str = map.get(key) + str;

        }
        str = str.replaceAll("\\D+", "");
        System.out.println(str);
    }
}

Answer 1

Here is realization on JS

https://jsfiddle.net/b6r81jv9/

let input = [
  {test: [1, 2, 3, 4, 5, 6, 7, 8], res: "87654321"},
  {test: [50, 2, 1, 9], res: "95021"},
  {test: [1, 19], res: "191"},
  {test: [9, 90], res: "990"},
  {test: [9, 90, 900], res: "990900"},
  {test: [9, 909, 9909, 999], res: "99999909909"}
];
function big_number_simplified(arr) {
    return [...arr].sort((a, b) => b.toString() + a > a.toString() + b ? 1 : -1);
}
input.forEach(item => {
  let res_1 = big_number_simplified(item.test).join('');
  if (res_1 === item.res) {
        console.log(`[${item.test.join(',')}]: "${res_1}"`);
  } else {
    console.error(`ERROR: [${item.test.join(',')}]: "${res_1}", expected: "${item.res}"`);
  }
});

Answer 2

No matter how you combine the numbers they produce a number with the same number of digits. This means you want to sort them to put the biggest digits first. In fact this is to opposite problem of sorting numbers inside a string because you want to sort the numbers like you would Strings (from the first digit first)

int[] a = {90, 91, 89, 999};
long num = Long.parseLong(
        IntStream.of(a)
                .mapToObj(Integer::toString)
                // reverse sort them as Strings.
                .sorted((x, y) -> (y + x).compareTo(x + y))
                .collect(Collectors.joining()));
System.out.println(num);

prints

999919089

Answer 3

Basically, the numbers need to be ordered in a certain way to form the maximum possible number. Consider this logic:

• Take any 2 numbers a and b
• If ab is bigger than ba then a should come before b. Right?
  • Where ab is a and b concatenated, so if a = 4 and b = 43 then ab is 443 and ba is 434

You could implement this in a custom comparator, and pass it to Collections.sort, like this:

public String maxNumber(int[] numbers) {
    // convert int[] -> List<String>
    List<String> list = new ArrayList<>(numbers.length);
    for (int num : numbers) {
        list.add(String.valueOf(num));
    }

    // sort using custom comparator
    Collections.sort(list, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));

    // join sorted items, forming max possible number
    return String.join("", list);
}

Here is basically the same code using Java 8: (thanks @marcospereira!)

public String maxNumber(Integer ... numbers) {
    return Stream.of(numbers)
            .filter(n -> n >= 0)
            .map(Object::toString)
            .sorted((s1, s2) -> (s2 + s1).compareTo(s1 + s2))
            .collect(Collectors.joining());
}