HackerRank Equal with Scala

Question

For studying Scala, I wrote some code to solve the Equal problem on HackerRank. But I am stuck on test case #15 due to timeout.

Christy is interning at HackerRank. One day she has to distribute some chocolates to her colleagues. She is biased towards her friends and may have distributed the chocolates unequally. One of the program managers gets to know this and orders Christy to make sure everyone gets equal number of chocolates.

But to make things difficult for the intern, she is ordered to equalize the number of chocolates for every colleague in the following manner,

For every operation, she can choose one of her colleagues and can do one of the three things.

1. She can give one chocolate to every colleague other than chosen one.
2. She can give two chocolates to every colleague other than chosen one.
3. She can give five chocolates to every colleague other than chosen one.

Calculate minimum number of such operations needed to ensure that every colleague has the same number of chocolates.

My code is like below I will appreciate your advice to improve performance.

object EqualsTest {
  def main(args: Array[String]): Unit = {
    val numOfTestCases = readInt();
    Range(0, numOfTestCases).foreach(i => {
      val numberCount = readInt();
      var numbers = Array.ofDim[Int](numberCount)
      val inputNumbers = scala.io.StdIn.readLine().split("""\s+""")
      0.until(numberCount).foreach(i => {
        numbers(i) = inputNumbers(i).trim.toInt
      })
      // val numbers = scala.io.StdIn.readLine().split(" ").map(s => s.toInt);
      var baseLine = numbers.min
      println(calOpCount(numbers, baseLine))
    })

    def f(b: Int)(s: Int): Int = {
      val i = s - b
      if (i==0) 0
      else if (i == 1 || i == 2 || i == 5) 1
      else (i/5 + (i%5)/2 + ((i%5)%2))
    }

    def calOpCount(source: Array[Int], baseLine: Int): Int = {
       val baseLines = 0.to(baseLine)
       val result = for {i <- baseLines; f1 = f(i)(_)} yield (source.map(s => f1(s.toInt)).sum)
       result.min
    }
  }
}

Answer 1

The performance issue and the bug

The program essentially looks for the minimum operations to reduce the numbers to some base line. There are two problems with the choice of base lines.

The performance issue is that you try base lines from 0 until the minimum value. Consider this input:

999

The program will check base lines from 0 to 999, in vain. You need up check only the 3 baselines: min, min - 1 and min - 2.

The second problem is a bug, and it is a related issue. Consider this input:

0 4 4

The program will check only one base line, 0. And that will give the incorrect result 4. Checking -1 would give the correct result 3.

Working with user input

The readInt method is deprecated in favor of StdIn.readInt.

The way you parsed the input is unnecessarily complicated. This line is commented out, even though it was really on the right track:

val numbers = scala.io.StdIn.readLine().split(" ").map(s => s.toInt);

Scala style

Some of the var could have been val or unnecessary altogether, and semicolons at end of lines are not recommended. Also, you used Range(0, numOfTestCases) at one point, even though you used the more idiomatic x.until(y) syntax elsewhere.

Alternative implementation

Putting the above tips together:

import scala.io.StdIn

object Solution {

  def main(args: Array[String]): Unit = {
    val numOfTestCases = StdIn.readInt()
    0.until(numOfTestCases).foreach(_ => {
      StdIn.readInt()
      val numbers = StdIn.readLine().split(" ").map(s => s.toInt)
      println(calOpCount(numbers))
    })
  }

  def steps(i: Int): Int = {
    if (i == 0) 0
    else if (i == 1 || i == 2 || i == 5) 1
    else i / 5 + (i % 5) / 2 + ((i % 5) % 2)
  }

  def calOpCount(source: Array[Int]): Int = {
    val min = source.min
    (for {base <- 0.to(2)} yield source.map(s => steps(s - min + base)).sum).min
  }
}