[kkdaemas]

The question is very unrealistic... how often do you know there is exactly one duplicate in a list?

Much more common is there are zero or more duplicates.

Here is what I came up with:

- We need a way to record what has been already seen

- A hash-map could work, but I think we can be more efficient

- We know that all elements are less than the array length in size...

- So we can allocate a single array of flags with the same length as the input

- The flag for value `n` is at position `n` in this array

    let findDuplicates xs =
      let seen = Array.create (Seq.length xs) false

      let mutable duplicates = []

      for x in xs do
        if seen[x] then
          duplicates <- x :: duplicates
        else
          seen[x] <- true

      duplicates

I'm pretty sure this is O(n)?

I think it's interesting that the mathematical trick (sum of numbers 1 to n formula) does not work in the more realistic variant. This fact is probably why leet-code problems are so disconnected from the real world. It's like AI for board-games.

[oriolid]

The question isn't really about finding duplicates in a list, but a slightly backhanded way to ask "do you remember high school math and can you apply it". A less artificial problem would just make things more complicated.

Also, your way is O(n) memory when O(1) would be enough for the original question.

[masto]

Always start a programming interview by asking questions. You know there is exactly one duplicate in the list because you wouldn’t start coding without thinking about what the problem left unspecified and getting the interviewer to clarify.