The problem involving a duplicate number from 1..n... The sum 1+2+...+n is just n(n+1)/2. Something worth knowing for this sort of "trick" problem.
One can do addition mod n. As long as 2n doesn't overflow, you are good.
You can further improve it by not using any number larger than n. Say we want to sum a+b mod n, wlog assume a<b. If a+b<=n, we are good. If not, then b>n-a. Note a+b mod n = a+(n-a)+(b-(n-a)) mod n = (b-(n-a)) mod n. Now the calculation doesn't overflow.
Here is something to show avoid overflow can be quite difficult... http://cstheory.stackexchange.com/questions/19591/avoiding-o...
I wonder if the result will still be correct. It's possible to have multiple answers. e.g. (7 + 10) % 6 = 5. But both 5, 11, 17 % 5 == 5. Can you find which one is the actual sum though?
---btw, the xor solution--- (defn find-dup [dup_set test_set] (reduce #(. clojure.lang.Numbers xor %1 %2) (into dup_set test_set)))
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.
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.
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.