My solution to a Scala programming problem by codility

gistfile1.scala

// 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

Ahh, non-fp solutions is cheating :) But it sure has much better memory properties.

here's a super-slow variant. It seems to be correct, but awfully slow. Oops, first submission will overflow on A.sum.

def solution(A: Array[Int]): Int = {                                            
  @tailrec def recEqui(A: Array[Int], leftSum: Long, rightSum: Long, n: Int = 0): Int = {
    if(A.isEmpty)                                                                
      return -1                                                                 
    if(leftSum == rightSum - A.head)                                            
      return n                                                                  

    recEqui(A.tail, leftSum + A.head, rightSum - A.head, n+1)                   
  }                                                                             

  recEqui(A, 0L, A.map(_.toLong).sum, 0)                                               
}                                                                               

Here is a functional version that is O(N)
head and tail is faster on a List (slow on an Array) since a List is optimized for Head/Tail operations.
Also, if you convert the Array[Int] to an Array[Long] only 1 time, you save some cycles.
This returns in less than a second and scores 100%.

import scala.annotation.tailrec

object Solution {
  def solution(A: Array[Int]): Int = {
    // convert to Long to avoid overflows, then to List[Long]
    val B: List[Long] = A.map(_.toLong).toList
    testEquil(B, 0L, B.sum, 0)
  }

  @tailrec
  def testEquil(A: List[Long], leftSum: Long, rightSum: Long, P: Int): Int = {
    if (A.isEmpty) return -1
    if (leftSum == rightSum - A.head) return P
    testEquil(A.tail, leftSum + A.head, rightSum - A.head, P+1)
  }
}

// example call with 10 million entries
val result = Solution.solution(Array.fill(5000000)(1) ++ Array(100) ++ Array.fill(5000000)(1))
println(result)

// I have skipped conversion to List. Also head and tail operations
// Though this gives best performance, I am not sure whether it is good to pass on original array in recursive calls.

def solution_Rec_Array(A: Array[Int]): Int = {
testEquil_Array(A, 0L, A.sum, 0)
}
@tailrec
def testEquil_Array(A: Array[Int], leftSum: Long, rightSum: Long, index: Int): Int = {
if (A.isEmpty) return -1
if (leftSum == rightSum - A(index)) return index
testEquil_Array(A, leftSum + A(index), rightSum - A(index), index+1)
}

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