n. A box holds n + 1 tags, all numbered within that range, so at least one number must repeat. Exactly one number repeats (it may appear twice or more), and every other number appears at most once.
Given the array tags of length n + 1, return the number that repeats.
Extra requirement: do not modify tags and use only O(1) extra memory. Sorting or a set of seen values won't do.tags=[2, 4, 1, 3, 4] → 4
Numbers go from 1 to 4 and there are five tags; 4 shows up twice.
tags=[1, 1] → 1
The smallest case: n = 1, so the 1 has to repeat.
tags=[5, 2, 5, 1, 5, 5] → 5
The repeated number may appear more than twice: here 5 appears four times.
tags=[2, 4, 1, 3, 4]
4
Run checks the first 3 tests in your browser. Submit checks all 80 tests on the server, hidden ones included.