Comment by 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.