Lesson 1: PermMissingElem (Perm Missing Elem)

As the expected worst-case space complexity is O(1), this problem is made a bit harder.

The strategy is to computer the expected sum when there is no lacking first, then subtract the actual sum you obtain from it.

=================================================================================

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

=================================================================================

int solution(int A[], int N) 
{
    long sum = ((long)N + 1) * (N + 2) / 2;
    
    int i;

    for (i = 0; i < N; i++){
        sum -= A[i];
    }
    
    return sum;
}