4 ms·
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.
by kd5bjo 4y ago
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 4y agoIt’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.
- deleted 4y ago[deleted]
- kd5bjo 4y agoIn 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).