Not sure I agree. It's very simple if you look at what's "wrong" with the input: it has a duplicated number, which means there's a "right" version of it without. That right version is just the count from 1->n. Once you see that, you can see that all you have to do is sum each list and calculate the difference.

This algorithm fails in the case that the duplicated number appears more than twice in the list, which is explicitly allowed by the problem statement.

It’s not, on Leetcode. I submitted it as an answer and it worked. In the case where the number is repeated more than once (m times), you have an array of n+m elements. Divide the sum by m, subtract, problem solved.

In that case, their test suite doesn’t cover all relevant cases. Consider nums = [1,1,1,1,4]: There are 5 elements, so n=4, and all elements are within the range [1,4]; only the 1 is duplicated. This fulfills all of the listed requirements.

The actual sum is 8, and the 4th triangular number is 10, so the duplicated number according to your algorithm must be -2 (or some fraction thereof, depending on how you calculate m).

The LeetCode version doesn't require linear time, and caps the number of elements to 10^5, so the brute-force O(n^2) time solution seems perfectly acceptable.

Tried it with a simple loop, got time limit exceeded unfortunately.