But x is not necessarily smaller than n though. For example:
Duplicate array: [1,2,2,3,4]. If you do mod 2 sum, then you have 1+0+0+1+0 = 2 mod 0 = 0. But another possible duplicate set can be: [1,2,3,4,4].
10 + x = 0 mod 2
(see 4%2 = 0 and 2%2 = 0? So x can be either 2 or 4.) If you let modulus number N be larger than n (e.g. n = 5 in my example, just let N = 6. Then 10 + x = 0 mod 6 will yield only one possible solution that is 2) then I think your solution will definitely work.
But I think the big problem is: you said x = (b - a) % n. That is true, but how do we get "a" (the sum of all unique numbers from 1 to n) without overflowing? The reason we do modulus summation is for avoiding overflow, granted that can get "b" easily, yet now we have to find "a" still, I find we are still stuck. Any suggestion?
Even if assuming everything will work out and my previous question can be responded, still the modulus function is WAY MORE expensive to compute than xor operation.
> If you let modulus number N be larger than n (e.g. n = 5 in my example, just let N = 6. Then 10 + x = 0 mod 6 will yield only one possible solution that is 2) then I think your solution will definitely work.
That was entirely what I was suggesting, but we don't need N>n. N=n would work. (btw, I defined n to be the size of the list -1, therefore in your example, the number is 4)
> But I think the big problem is: you said x = (b - a) % n. That is true, but how do we get "a" (the sum of all unique numbers from 1 to n) without overflowing? The reason we do modulus summation is for avoiding overflow, granted that can get "b" easily, yet now we have to find "a" still, I find we are still stuck. Any suggestion?
We can compute a using the same function that computes b. just sum all numbers from 1 to n mod n.
Here is a quick demonstration in Haskell.
> Even if assuming everything will work out and my previous question can be responded, still the modulus function is WAY MORE expensive to compute than xor operation.
True. I just want to show how to modify another solution so there is no overflow.
If we did mod n addition the whole way, we have the result a+x mod n, and let that number be b.
Claim: if a + x = b mod n, then there is a unique solution x in between 0 and n-1. In fact x = (b - a) % n.
Now, if x = 0 from the above computation, you would know it is n instead of 0.