[vitiral]

That problem is a terrible interview question, mainly because it's completely trivial with O(n) memory (just use a Set), but requires a different branch of comp sci at O(1).

Personally I also feel that any question that needs an O(1) memory when you _start with an array_ is disingenuous. O(1) memory was used for things like tape storage, where N was some huge external storage. If you already have an array, then the chance you don't have double that memory are dibcus.

[sanedigital]

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.

[kd5bjo]

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.

[sanedigital]

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.

[kd5bjo]

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).

[kd5bjo]

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.

[dullcrisp]

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