N-Repeated Element in Size 2N Array

The task is taken from leetcode

In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.

Return the element repeated N times.

Example 1:

Input: [1,2,3,3] Output: 3

Example 2:

Input: [2,1,2,5,3,2] Output: 2

Example 3:

Input: [5,1,5,2,5,3,5,4] Output: 5

Note:

4 <= A.length <= 10000 0 <= A[i] < 10000 A.length is even

My solution

var repeatedNTimes = function(A) {
const set = new Set();
for (const n of A) {
if (set.has(n)) { return n; }
}
};

I didn't do much with the information size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times. I think these information is not needed to solve the problem efficiently. I also wonder whether there is a bitwise or purely math based solution to the task.

• Your solution is optimal.All that could be improved is the hashing of each item, In JS you can not write low level and thus improve the hashing (with exception of webAsm (if you consider it JS) but that is still very immature and would only give advantage for very large data sets) – Blindman67 Apr 22 at 15:02

In the worst case (the repeated element occupies the second half of the array), the set will accommodate all N non-repeated elements, therefore the space complexity of the solution is $$\O(N)\$$.
Your intuition is correct; the solution doesn't use the important information. It is used to find out how far apart the repeated elements are. If a distance between them is at least $$\d\$$, the array would be at least $$\d\cdot(N-1) + 1\$$ long. Since we know that it is $$\2N\$$ long, we can conclude that $$\d \le \dfrac{2N-1}{N-1}\$$, which is effectively 2 for N > 2. It is enough to compare each a[i] with a[i+1] and a[i+2]. The space complexity is now constant.