nums holds n + 1 integers, and every one of them lies between 1 and n inclusive. There are more slots than possible values, so some value has to repeat. Exactly one value does: it shows up two or more times, and every other value shows up at most once. Return the value that repeats.
Solve it without changing nums and with only O(1) extra memory: no copy of the array, no set and no counting table. The judge only sees your answer, so it can't check either rule. The puzzle is finding the repeat under them.
Five numbers drawn from 1 to 4: each value appears once except 4, which sits at indices 2 and 3.
2 appears three times. Because of that, 4 never appears at all, which is allowed.
With n = 1 the only possible value is 1, so both slots hold it.
Constraints
1 <= n <= 10⁵nums.length == n + 11 <= nums[i] <= nn + 1.Treat each value as a pointer: from index i, step to index nums[i]. Index 0 has nothing pointing at it, so a walk from there must fall into a loop, and the repeated value is where the loop begins, because two different indices point at it.
Without the two rules this is a warm-up: drop every number into a set and stop at the first one already there. The rules take that away. No set, no counting table, and no sorting nums in place. What you have left is the array itself, read-only, and a few integer variables.
Time O(n)Space O(1)
The full walkthrough and code are part of Premium
4