1

Lets say i have an array:

int[] arr = {23, 4, 46, 720, 56};

How would i find the order of numbers which would give the largest number?

Eg., in the array arr, the order is

7205646423

Edit : There can be n digit numbers also i.e., not necessarily limited to 3.

Eg.,

int[] arr = {223, 23, 72, 7, 64, 9};

The answer being

97726423223
6
  • 6
    Just (string)-sort the numbers and then concatenate.
    – Sirko
    Sep 4, 2013 at 11:17
  • 7205646423 is the largest i guess
    – sr01853
    Sep 4, 2013 at 11:18
  • 2
    @nhahtdh correct. More interesting example would be 72 and 720, where 72 should come first.
    – Sirko
    Sep 4, 2013 at 11:19
  • @nhahtdh You're right.
    – Pavan
    Sep 4, 2013 at 11:24
  • 4
    possible duplicate of How can I manipulate an array to make the largest number?
    – nhahtdh
    Sep 4, 2013 at 11:28

1 Answer 1

6

A lexicographic sort is a good start.

However, the difficulty comes in when considering that, for example, [854, 854853, 854855] needs to be sorted to [854855, 854, 854853].

One way to fix this is to define a comparator that compares concatenated versions of the numbers (i.e. comparing abc and def translates to comparing abcdef and defabc).

The simplest version:

// processing numbers as strings
List<String> array = Arrays.asList("854", "854853", "854855");
Collections.sort(array, new Comparator<String>() {
   @Override
   public int compare(String o1, String o2)
   {
      // negative since we want biggest first
      return -(o1+o2).compareTo(o2+o1);
   }
});

Test.

The compare function without the overhead of actually having to concatenate the numbers, just doing the checking in-place:

@Override
public int compare(String s1, String s2)
{
   int i;
   int length = s1.length() + s2.length();
   for (i = 0; i < length; i++)
   {
      char c1 = get(s1, s2, i),
           c2 = get(s2, s1, i);
      if (c1 != c2)
      {
         return (c1 > c2 ? -1 : 1);
      }
   }
   return 0;
}

private char get(String s1, String s2, int index)
{
   if (index < s1.length())
      return s1.charAt(index);
   else
      return s2.charAt(index - s1.length());
}

Test.

I originally has a much more complex version which should theoretically be a little faster as it had a few for-loops, having the indices wrap around into the other array, instead of one loop, checking the lengths, but simplicity beats the performance difference for me here. If you're interested, feel free to check the post history (rev 3), but note that that version had a bug in - after the last loop, the other index should wrap into the other array.

3
  • The second method seems to be wrong for this test case: 72562 72562725627256273 7272727272 72 727 7270 72727272727, 727 should come before 72. This is the modified program that takes input from stdin: ideone.com/RoM8hP
    – nhahtdh
    Sep 4, 2013 at 11:52
  • @nhahtdh Fixed. Well, rewritten. Sep 4, 2013 at 12:19
  • +1. The in-place comparison method is clean, much more understandable than my old code.
    – nhahtdh
    Sep 4, 2013 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.