时间戳

首页 > 解决方案 > python - 如何在python中的两个给定数组中找到非互质数对的数量？

python - python - 如何在python中的两个给定数组中找到非互质数对的数量？

问题描述

如何查找给定数组中非互质数的数量？认为

a = [2, 5, 6, 7]
b = [4, 9, 10, 12]

那么非互质数将是 3，因为您可以删除：

(2, 4)
(5, 10)
(6, 9)

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
count = 0
len_a = len(a)
len_b = len(b)
for i in range(len_a):
    for j in range(len_b):
        x = a[i]
        y = b[j]
        if(math.gcd(x,y) != 1):
            count += 1
print(count)

这是参考：https ://www.hackerrank.com/challenges/computer-game/problem

我收到 8 作为输出。

标签： pythonpython-3.x

解决方案

为什么你期望答案是 3？
您将 5 和 10 配对，因此您显然是在查看成对的元素，a而b忽略了它们的位置。

只需打印出这些对，您就会明白为什么会得到 8 个...

import math
from itertools import product

a=[2, 5, 6, 7]
b=[4, 9, 10, 12] 
print(sum([math.gcd(x, y) != 1 for x, y in product(a, b)]))  # 8
print([(x, y) for x, y in product(a, b) if math.gcd(x, y) != 1])  # the pairs

更新：在阅读了 OP 试图处理的问题之后，值得指出的是，预期输出 (3) 是另一个问题的答案！
不是有多少对元素不是互质的，而是有多少非互质对可以被删除而不会将它们返回到数组中。
这个问题实际上难度要高一个数量级，不是修复代码的问题，而是给实际问题大量的数学和算法思想。

在这里查看一些讨论

最后一次编辑，一种解决方案，尽管效率极低。唯一的一点是通过查看某种形式的解决方案来建议一些可以帮助 OP 理解原始问题的代码的代码，无论它是低质量还是运行时差。

import math
from itertools import product, permutations

n = 4

def get_pairs_list_not_coprime_count(pairs_list):
    x, y = zip(*pairs_list)
    return min(i for i in range(n) if math.gcd(x[i], y[i]) == 1)  # number of pairs before hitting a coprime pair


a = [2, 5, 6, 7]
b = [4, 9, 10, 12]

a_perms = permutations(a)  # so that the pairing product with b includes all pairing options
b_perms = permutations(b)  # so that the pairing product with a includes all pairing options

pairing_options = product(a_perms, b_perms)  # pairs-off different orderings of a and b
actual_pairs = [zip(*p) for p in pairing_options]  # turn a pair of a&b orderings into number-pairs (for each of the orderings possible as realized by the product)

print(max(get_pairs_list_not_coprime_count(pairs_list) for pairs_list in actual_pairs))  # The most pairings managed over all possible options: 3 for this example

推荐阅读