Обнаружение повторяющегося элемента в массиве

Существует массив размера n, и элементы, содержащиеся в нем, находятся в диапазоне от 1 до n-1, так что каждый элемент встречается один раз, а только один элемент встречается более одного раза. Нам нужно найти этот элемент.

Хотя это очень часто задаваемые вопросы, я все еще не нашел правильного ответа. Большинство предложений состоит в том, что я должен сложить все элементы в массиве, а затем вычесть из него сумму всех индексов, но это не сработает, если количество элементов очень велико. Он переполнится. Также были предложения относительно использования логического элемента XOR dup = dup ^ arr [i] ^ i , которые мне непонятны.

Я придумал этот алгоритм, который является улучшением алгоритм сложения и значительно снизит вероятность переполнения!

for i=0 to n-1
  begin :
    diff = A[i] - i;
    sum  = sum + diff;
  end

diff содержит повторяющийся элемент, но с помощью этого метода я не могу узнать индекс повторяющегося элемента. Для этого мне нужно пройти по массиву еще раз, что нежелательно. Может ли кто-нибудь предложить лучшее решение, которое не включает метод сложения или метод XOR работает в O (n)?