Finding the only duplicate in the list-CodePudding

I was trying to solve a challenge where, you're given a list which will contain only one duplicate. The constraint is that you must do it in O(N) time and O(1) space.

Seems like a no brainer, we simply need to use the sum of N natural numbers formula and return the difference between the sum calculated using the formula and the sum of the elements in the list.

But, when trying using the formula N * (N 1)/2 I wasn't able to arrive at the correct result when subtracting the together. For eg, when

nums = [1,2,3,3] 
nums = [1,1,2,3]

the formula gives us the result = 10 but the list sums are 9 and 7 respectively. So, from the above we can clearly see that if we subtract the two, we won't be able to arrive at the result.

So, I tried a variation of the formula and used N * (N-1) / 2 which worked perfectly for all the cases as you can see.

What is the significance of the above formula I'm not able to understand as to why this formula works in this particular situation instead of the standard one.

I'm attaching my code below :

class Solution:
    def solve(self, nums):
        # Calculating the sum
        listSum = sum(nums)

        length = len(nums)

        actual = int(length * ((length-1)/2))

        return (abs(listSum - actual))

CodePudding user response：

If your list has N elements they are the first N-1 natural numbers, plus the duplicate. That is why the formula for the sum of the first N-1 natural numbers gives you the correct solution.