3 ms·

If we sum all the numbers we get n(n+1)/2 + x, where x is the duplicate number. Assume n(n+1)/2 = a mod n. If we did mod n addition the whole way, we have the

by chaoxu 13y ago

If we sum all the numbers we get n(n+1)/2 + x, where x is the duplicate number. Assume n(n+1)/2 = a mod n. 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.

alttab 13y ago
I read a lot of this with my brow raised.
jw2013 13y ago
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.
- chaoxu 13y ago
  > 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. http://lpaste.net/101868 http://lpaste.net/101868 > 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.

by chaoxu 13y ago

alttab 13y ago

I read a lot of this with my brow raised.

jw2013 13y ago

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.

chaoxu 13y ago
> 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. http://lpaste.net/101868 http://lpaste.net/101868 > 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.