Find duplicate in unsorted array with best time Complexity

Question

I know there were similar questions, but not of such specificity

Input: n-elements array with unsorted emelents with values from 1 to (n-1). one of the values is duplicate (eg. n=5, tab[n] = {3,4,2,4,1}.

Task: find duplicate with best Complexity.

I wrote alghoritm:

int tab[] = { 1,6,7,8,9,4,2,2,3,5 };
int arrSize = sizeof(tab)/sizeof(tab[0]);

for (int i = 0; i < arrSize; i++) {
    tab[tab[i] % arrSize] = tab[tab[i] % arrSize] + arrSize;
}

for (int i = 0; i < arrSize; i++) {
    if (tab[i] >= arrSize * 2) {
        std::cout << i;
        break;
    }

but i dont think it is with best possible Complexity. Do You know better method/alghoritm? I can use any c++ library, but i don't have any idea.

Is it possible to get better complexity than O(n) ?

Answer 1

In terms of big-O notation, you cannot beat O(n) (same as your solution here). But you can have better constants and simpler algorithm, by using the property that the sum of elements 1,...,n-1 is well known.

int sum = 0;
for (int x : tab) {
  sum += x;
}

duplicate = sum - ((n*(n-1)/2))

The constants here will be significntly better - as each array index is accessed exactly once, which is much more cache friendly and efficient to modern architectures.

(Note, this solution does ignore integer overflow, but it's easy to account for it by using 2x more bits in sum than there are in the array's elements).