Can you check for duplicates by taking the sum of the array and then the product of the array?

user_16538411 0
Viewed 73

Let's say we have an array of size N with values from 1 to N inside it. We want to check if this array has any duplicates. My friend suggested two ways that I showed him were wrong:

  1. Take the sum of the array and check it against the sum 1+2+3+...+N. I gave the example 1,1,4,4 which proves that this way is wrong since 1+1+4+4 = 1+2+3+4 despite there being duplicates in the array.

  2. Next he suggested the same thing but with multiplication. i.e. check if the product of the elements in the array is equal to N!, but again this fails with an array like 2,2,3,2, where 2x2x3x2 = 1x2x3x4.

Finally, he suggested doing both checks, and if one of them fails, then there is a duplicate in the array. I can't help but feel that this is still incorrect, but I can't prove it to him by giving him an example of an array with duplicates that passes both checks. I understand that the burden of proof lies with him, not me, but I can't help but want to find an example where this doesn't work.

P.S. I understand there are many more efficient ways to solve such a problem, but we are trying to discuss this particular approach.

Is there a way to prove that doing both checks doesn't necessarily mean there are no duplicates?

proof duplicates algorithm
2 Answers

Here's a counterexample: 1,3,3,3,4,6,7,8,10,10

Found by looking for a pair of composite numbers with factorizations that change the sum & count by the same amount.

I.e., 9 -> 3, 3 reduces the sum by 3 and increases the count by 1, and 10 -> 2, 5 does the same. So by converting 2,5 to 10 and 9 to 3,3, I leave both the sum and count unchanged. Also of course the product, since I'm replacing numbers with their factors & vice versa.

Here's a much longer one.

24 -> 2*3*4 increases the count by 2 and decreases the sum by 15
2*11 -> 22 decreases the count by 1 and increases the sum by 9
2*8 -> 16 decreases the count by 1 and increases the sum by 6.

We have a second 2 available because of the factorization of 24.

This gives us:

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24

Has the same sum, product, and count of elements as

1,3,3,4,4,5,6,7,9,10,12,13,14,15,16,16,17,18,19,20,21,22,22,23

In general you can find these by finding all factorizations of composite numbers, seeing how they change the sum & count (as above), and choosing changes in both directions (composite <-> factors) that cancel out.

user_20410770

I've just wrote a simple not very effective brute-force function. And it shows that there is for example

1 2 4 4 4 5 7 9 9

sequence that has the same sum and product as

1 2 3 4 5 6 7 8 9

For n = 10 there are more such sequences:

1 2 3 4 6 6 6 7 10 10 
1 2 4 4 4 5 7 9 9 10 
1 3 3 3 4 6 7 8 10 10 
1 3 3 4 4 4 7 9 10 10 
2 2 2 3 4 6 7 9 10 10

My write-only c++ code is here: https://ideone.com/2oRCbh

user_47592000
Related