3
\$\begingroup\$

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))
\$\endgroup\$
  • \$\begingroup\$ LGTM, though I'm not sure how I would actually prove that the algorithm always gives the correct answer. \$\endgroup\$ – Seth Tisue Oct 27 '15 at 15:41
  • \$\begingroup\$ @SethTisue I would compare it to bruteforce on some randomly generated testcases \$\endgroup\$ – Caridorc Oct 27 '15 at 17:48
  • \$\begingroup\$ Actually, I'm pretty sure that an induction proof would work just fine. Haven't done one in ages though. \$\endgroup\$ – Donald.McLean Oct 29 '15 at 22:44
2
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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