您可以通过获取阵列的总和，然后是数组的乘积来检查重复项吗？
假设我们有一个大小为n的数组，其中的值是1到n。我们想检查此数组是否具有任何重复。我的朋友建议我向他展示的两种方法是错误的：
拿走数组的总和，并根据总和1+2+3+...+n进行检查。我给了示例1,1,4,4，这证明了这种方式是错误的，因为1+1+1+4 = 1+2+3+4，尽管数组中有重复。
接下来，他提出了同样的事情，但是乘以乘法。 IE检查阵列中元素的乘积是否等于n！
最后，他建议进行两次检查，如果其中一个失败，那么数组中有一个重复。我忍不住觉得这仍然是不正确的，但是我不能通过给他一个带有复制品的数组的例子来证明这一点。我知道举证责任在于他，而不是我，但我不禁想找到一个不起作用的例子。
PS我知道有许多更有效的方法可以解决此类问题，但我们正在尝试讨论这种特殊的方法。
有没有办法证明执行两项检查并不一定意味着没有重复项？
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:
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.
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这是一个反例：
通过寻找一对复合数字和因素化可以改变总和＆amp;计数相同的数量。
即9-＆GT; 3，3将总和减少3，并将计数增加1，而10-＆gt; 2，5也一样。因此，通过将2,5转换为10和9至3,3，我同时将总和不变。当然也是产品，因为我要替换数字用它们的因素＆amp;反之亦然。
这是更长的一个。
由于24分解，我们有第二个可用的2。
这给了我们：
具有与一般的元素相同的总和，产品和计数，
您可以通过查找复合数字的所有因素来找到它们，看看它们如何更改总和＆amp ;计数（如上所述），并在两个方向（复合＆lt; - ＆gt;因素）中选择更改。
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.
We have a second 2 available because of the factorization of 24.
This gives us:
Has the same sum, product, and count of elements as
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.
我刚刚写了一个简单的不是非常有效的蛮力功能。它表明，例如序列具有
相同的总和和产品的
与n = 10
序列：我的仅写入C ++代码在这里： https://ideone.com/2orcbh
I've just wrote a simple not very effective brute-force function. And it shows that there is for example
sequence that has the same sum and product as
For n = 10 there are more such sequences:
My write-only c++ code is here: https://ideone.com/2oRCbh