What is the right way to solve Codility's PermMissingElem test? (Java)

This problem has a mathematical solution, based on the fact that the sum of consecutive integers from 1 to n is equal to n(n+1)/2.

Using this formula we can calculate the sum from 1 to N+1. Then with O(N) time complexity we calculate the actual sum of all elements in the array.

The difference between the full and actual totals will yield the value of the missing element.

Space complexity is O(1).

Another 100% solution:

There is actually not even a need to use 64-bit integers to avoid the overflows that a couple of tests try to trigger (the ones with array size of 100000 at the time of writing). And you can get away with only one sum variable. The last line avoids overflows further by implementing n(n+1)/2 differently so that the division by two occurs "early":

C#: class Solution { public int solution(int[] A) { var sum = 0; for(int i = 0; i < A.Length; i++) sum += A[i];
return A.Length % 2 == 0 ? -sum + (A.Length/2 + 1) * (A.Length+1) : -sum + (A.Length/2 + 1) * (A.Length+2); } }

This problem is part of the Lessons of Time Complexity.

https://codility.com/media/train/1-TimeComplexity.pdf

In fact at the end there is the explanation on how to compute the sum of the elements in an array, without do any loop.

This is the final solution in Python3:

def solution(A):

    n = len(A)+1
    result = n * (n + 1)//2

    return result - sum(A)