Problem

**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; }
set.add(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.

Solution

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)$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$d$, the array would be at least d⋅(N−1)+1$d\cdot (N-1)+1$ long. Since we know that it is 2N$2N$ long, we can conclude that d≤2N−1N−1$d\le {\displaystyle \frac{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.

I see in revision 3 that the `else`

keyword and block was replaced by the single line that was in the block. That is a good simplification. Some developers aim to avoid the `else`

keyword with techniques like returning early (like this code) and other similar techniques.

The function declaration uses the `var`

keyword. Unless the scope needs to be broader or it needs to be re-assigned, `const`

could have been used.

The suggestion in vnp’s answer to check each element with the following two is a good one to reduce the space complexity. Another technique to do so would be to utilize `Array.prototype.indexOf()`

passing the current index + 1 as the second argument (i.e. `fromIndex`

). If that returns a value greater than -1 (or even the current index) then you would know the value is repeated. However this may be sub-optimal because it would require an extra function call.

**Beware**: the above answers and comments are not optimal! (although VNP above provides a good mathematical explanation of the following)

Using the Boyer-Moore Voting algorithm, a solution can be determined in O(n) time but also **O(1) space.** Any repeated digit will be the answer. Therefore, spreading out the N digits of the repeated value results in two cases:

- The two values are side-by-side: in that case check every tuple for equality (when A[i] == A[i + 1] your answer is at A[i]).
- The repeated digit is spread out evenly (this occurs at most every second value, therefore, if the above fails, check A[i] == A[i + 2]).

This algorithm is a rough explanation, but crucially eliminates the need for a set. There is one edge case when the length of the values is four and the majority item is spread out on the edges.