Skip to content

Instantly share code, notes, and snippets.

@ryanlecompte
Created July 26, 2013 03:23
Show Gist options
  • Select an option

  • Save ryanlecompte/6085895 to your computer and use it in GitHub Desktop.

Select an option

Save ryanlecompte/6085895 to your computer and use it in GitHub Desktop.
My solution to a Scala programming problem by codility
// my solution to the sample codility problem for finding
// any equilibrium index in an array of ints with up to
// 10 million entries. Description of problem is here:
// http://blog.codility.com/2011/03/solutions-for-task-equi.html
def solution(a: Array[Int]): Int = {
var i = 0
var current = BigInt(0)
var remaining = BigInt(0)
a.foreach { remaining += _ }
var found = Option.empty[Int]
while (i < a.size && found.isEmpty) {
if (current == remaining - a(i)) {
// found equilibrium
found = Some(i)
} else {
current += a(i)
remaining -= a(i)
i += 1
}
}
found.getOrElse(-1)
}
// sample runs:
scala> solution(Array(-7, 1, 5, 2, -4, 3, 0))
res37: Int = 3
scala> solution(Array(1,2,3,1,2))
res38: Int = 2
scala> solution(Array.fill(5000000)(1) ++ Array(100) ++ Array.fill(5000000)(1))
res39: Int = 5000000
@kastoestoramadus
Copy link
Copy Markdown

kastoestoramadus commented Aug 23, 2016

a.foreach { remaining += _ }
better version:
remaining += a.sum

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment