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

Question

I have the following problem taken from Codility's code testing exercises:

A zero-indexed array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

class Solution { public int solution(int[] A); }

that, given a zero-indexed array A, returns the value of the missing element.

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.

Assume that:

N is an integer within the range [0..100,000]; the elements of A are all distinct; each element of array A is an integer within the range [1..(N + 1)].

Complexity:

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).

Elements of input arrays can be modified.

---

My approach was to convert the given array into an ArrayList, use the ArrayList to find the lowest and highest values inside the array, and iterate through all possible values from lowest to highest, and then return the missing value.

This solves the example problem, but my problem seems to be that I cannot get right answers under the following conditions of the given array:

"empty list and single element"

"the first or the last element is missing"

"single element"

"two elements"

What am I doing wrong, and what is the proper way to go about solving this problem?

Answer 1

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).

Answer 2

The problem statement clearly specifies that the array will consist of "N different integers", thus N must be at least 2. N=0 and N=1 simply do not make sense if we write them in English, e.g. "An array consisting of 0 different integers...".

A zero-indexed array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

With these initial conditions and stated assumptions, tests like "single element", "empty list", etc., are completely inappropriate.

Proper production code would most likely have to test for invalid conditions, but that wasn't a stated goal of the challenge.