Generating the maximum number possible from an array

Question

I have the following code in Scala as a solution to the problem:

Find the maximum number possible from the given Seq of Integers while keeping the individual numbers intact

e.g.

Seq(2,5,9,4) should result in 9542

Seq(4, 98, 10, 110, 91) should result in 9891411010

Note that in case of numbers with more than one digit, the entire number should remain together.

Solution in Scala:

import scala.util.Sorting
object MatheMagic {
  def getLargestPossibleNumber(numArray: Seq[Int]) = {
    numArray.sorted[Int](IntOrdering).mkString.toLong
  }
  object IntOrdering extends Ordering[Int] {
    def compare(x: Int, y: Int) = {
      -(x.toString.concat(y.toString).toInt compare y.toString.concat(x.toString).toInt)
    }
  }
}

Sample invocation:

MatheMagic.getLargestPossibleNumber(Seq(4, 98, 10, 110, 91))

Answer 1

Your algorithm is good, but the implementation is a bit wasteful:

• In IntOrdering.compare, x and y are converted to String twice, and then converted to Int
  • It's especially bad since the numbers in the sequence may pass through compare multiple times in different pairs, and get converted to String even more times
• You could reduce the casts:
  • Convert all numbers to String once in the beginning
  • Compare as strings. The algorithm will work with alphabetical comparison too
  • Convert to Long once at the end
• Creating a custom Ordering seems a bit overkill

This one-liner will do the job:

nums.map(_.toString).sortWith(
  (a, b) => (a concat b).compareTo(b concat a) > 0).mkString.toLong