4 ms·

I feel what you asked is a really nice follow up question, as tricks to not get a overflow could be highly non-trivial. One can do addition mod n. As long as 2

by chaoxu 13y ago

I feel what you asked is a really nice follow up question, as tricks to not get a overflow could be highly non-trivial. 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-overflow-in-finding-a-solution-toax-by-c http://cstheory.stackexchange.com/questions/19591/avoiding-o...

jw2013 13y ago
> One can do addition mod n. As long as 2n doesn't overflow, you are good. 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)))
- 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

jw2013 13y ago

> One can do addition mod n. As long as 2n doesn't overflow, you are good. 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)))

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.