0

I am solving a simple problem on one of the coding challenge websites where I need to find the missing element from the array.

Problem statement is that you have an input array from 1 to N+1 and you have to find the missing element from that array. 

For example, given array A such that:

  A[0] = 2
  A[1] = 3
  A[2] = 1
  A[3] = 5
the function should return 4, as it is the missing element.

For solving this I wrote a simple function that computed the result 

def sol(a: Array[Int]): Int = {
  ((a.length+1)*(a.length+2)/2)-a.sum
}

However on submitting the solution I got the correctness of the solution as 100% but was shocked to see the performance results at 60%. Can anybody point out any part of this one line code that can be optimised or is there any other way to achieve 100% performance for this ?

Note : I am looking out for functional style code.

Chaitanya
  • 3,590
  • 14
  • 33
  • The problem here is - how is that website measuring performance ? – sarveshseri Oct 01 '18 at 06:47
  • 1
    Unless the input array is not sorted all solutions are O(n). One downside of this solution is if N is too big you may end up with integer overflows. I don't think the problem is integer overflow, can you share the rest of the code? May be you are missing something there – Hüseyin Zengin Oct 01 '18 at 07:15
  • 1
    Also, you're calling `a.length` twice. Call it once and store the result instead. – Richard-Degenne Oct 01 '18 at 07:47
  • 5
    @Richard-Degenne; According to [this](https://stackoverflow.com/questions/1208320/what-is-the-cost-of-calling-array-length), there is little to no benefit in saving the `length` in a local variable. – jwvh Oct 01 '18 at 07:51
  • Good to know, thanks for pointing it out. – Richard-Degenne Oct 01 '18 at 07:55
  • It's really strange. I submitted almost the same solution on codility and got 100% – dyrkin Oct 01 '18 at 08:34
  • @dyrkin how is that possible – Chaitanya Oct 01 '18 at 08:49
  • 4
    I just ran your code on codility. And the error is not regarding performance but regarding the wrong answer `got -2147483647 expected 1`. To avoid integer overflow your sum must be of a Long type. To achieve this you can use `a.foldLeft(0L)(_ + _)` instead of `a.sum` – dyrkin Oct 01 '18 at 10:51

0 Answers0