4 ms·

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

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 4y ago
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 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 ago
    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.
    - deleted 4y ago
      [deleted]
    - kd5bjo 4y ago
      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 4y ago
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 4y ago
  Tried it with a simple loop, got time limit exceeded unfortunately.

sanedigital 4y ago

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 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 ago
  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.
  - deleted 4y ago
    [deleted]
  - kd5bjo 4y ago
    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 4y ago

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 4y ago
Tried it with a simple loop, got time limit exceeded unfortunately.