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\$
3
  • \$\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, 2015 at 15:41
  • \$\begingroup\$ @SethTisue I would compare it to bruteforce on some randomly generated testcases \$\endgroup\$
    – Caridorc
    Oct 27, 2015 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\$ Oct 29, 2015 at 22:44

1 Answer 1

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

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.