How can I manipulate an array to make the largest number?

Question

Say you have an array of positive integers, manipulate them so that the concatenation of the integers of the resultant array is the largest number possible. Ex: {9,1,95,17,5}, result: 9955171

Homework police: This was a google phone interview question and no NDAs were signed ;).

Answer 1

Looking at the example {5,54,56}, the proper way to order these numbers is when comparing strings A and B, we should consider lexicographic ordering of A+B with B+A.

For example:

• Comparing (5,54) becomes lexicographic comparison of ("554" with "545")
• Comparing (5,56) becomes lexicographic comparison of ("556" with "565")
• Comparing (54,56) becomes lexicographic comparison of ("5456" with "5654")

If we sort them this way, the resulting array is {56,5,54}.

Here's a Java implementation of this idea:

public class LexicographicSort implements Comparator<Integer> {      public int compare(Integer o1, Integer o2) {         String s1 = o1.toString();         String s2 = o2.toString();         return (s2+s1).compareTo(s1+s2);     }      public static void main(String[] args) {         LexicographicSort ls = new LexicographicSort();         Integer[] nums = {9,1,95,17,5};         Arrays.sort(nums, ls);         System.out.println(Arrays.toString(nums));     } } 

Answer 2

As others have pointed out, a lexicographic sort and concatenation is close, but not quite correct. For example, for the numbers 5, 54, and 56 a lexicographic sort will produce {5, 54, 56} (in increasing order) or {56, 54, 5} (in decreasing order), but what we really want is {56, 5, 54}, since that produces the largest number possible.

So we want a comparator for two numbers that somehow puts the biggest digits first.

1. We can do that by comparing individual digits of the two numbers, but we have to be careful when we step off the end of one number if the other number still has remaining digits. There are lots of counters, arithmetic, and edge cases that we have to get right.

2. A cuter solution (also mentioned by @Sarp Centel) achieves the same result as (1) but with a lot less code. The idea is to compare the concatenation of two numbers with the reverse concatenation of those numbers. All of the cruft that we have to explicitly handle in (1) is handled implicitly.

   For example, to compare 56 and 5, we'd do a regular lexicographic comparison of 565 to 556. Since 565 > 556, we'll say that 56 is "bigger" than 5, and should come first. Similarly, comparing 54 and 5 means we'll test 545 < 554, which tells us that 5 is "bigger" than 54.

Here's a simple example:

// C++0x: compile with g++ -std=c++0x <filename> #include <iostream> #include <string> #include <algorithm> #include <vector>  int main() {   std::vector<std::string> v = {     "95", "96", "9", "54", "56", "5", "55", "556", "554", "1", "2", "3"   };   std::sort(v.begin(), v.end(),       [](const std::string &lhs, const std::string &rhs) {         // reverse the order of comparison to sort in descending order,         // otherwise we'll get the "big" numbers at the end of the vector         return rhs+lhs < lhs+rhs;       });    for (size_t i = 0; i < v.size(); ++i) {     std::cout << v[i] << ' ';   } } 

When run, this code displays:

9 96 95 56 556 5 55 554 54 3 2 1