Как правильно решить тест PermMissingElem Codility на Java? ⇐ JAVA

[Anonymous]

ВНИМАНИЕ: НЕ публикуйте ответы на этот вопрос, написанные на языках, отличных от Java. В этом вопросе конкретно спрашивается, как решить эту проблему на Java.

У меня есть следующая проблема, взятая из упражнений по тестированию кода Codility. :

Дан массив A с нулевым индексом, состоящий из N различных целых чисел.
Массив содержит целые числа в диапазоне [1..(N + 1)], что означает
что ровно один элемент является отсутствует.
Ваша цель — найти недостающий элемент.
Напишите функцию:

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

что для массива A с нулевым индексом возвращается значение отсутствующего
элемента.
Например, дан массив A такой, что:

A[0] = 2
A[1] = 3
А[2] = 1
А[3] = 5

функция должна возвращать 4, так как это недостающий элемент.
Предположим, что:

N — целое число в диапазоне [0..100 000];
все элементы A различны;
каждый элемент массива A целое число в диапазоне [1..(N + 1)].

Сложность:

ожидаемая временная сложность в наихудшем случае равна O(N);
ожидаемая сложность пространства в наихудшем случае равна O(1), за пределами входной памяти (не >с учетом памяти, необходимой для входных аргументов).

Элементы входных массивов можно изменять.

Мой подход заключался в том, чтобы преобразовать данный массив в ArrayList, использовать ArrayList для поиска самых низких и самых высоких значений внутри массива и перебрать все возможные значения от самого низкого до самого высокого, а затем вернуть пропущенное значение.
Это решает проблему примера, но моя проблема, похоже, заключается в том, что я не могу получить правильные ответы при следующих условиях данного массива:
"пусто список и один элемент"
"первый или последний элемент отсутствует"
"одиночный элемент"
"два элемента"

Что я делаю неправильно и как правильно решить эту проблему?

Подробнее здесь: https://stackoverflow.com/questions/298 ... st-in-java