Python 无法比较最大公约数的值

Question

我正在尝试解决这个 hackerrank 问题：

这是我的尝试：

from fractions import gcd

def connectedCities(numCities, threshold, originCities, destinationCities):
    # Write your code here
    output = []
    
    for i in range(0, len(originCities)):
        if gcd(originCities[i], destinationCities[i]) > threshold:
            output.append(1)
        else:
            output.append(0)
    
    return output

但对于输入：

我的输出是：

Your Output (stdout)
0
1
0
1


Expected Output
1
1
1
1

Answer 1

我也不完全明白如何读取输入。但我想我知道为什么你的代码没有吐出预期的输出。您忽略了传递属性.

两个城市直接相连，当且仅当城市编号的 gcd > 阈值。然而，它们也可以通过其他城市间接连接。您的代码忽略了这种可能性。

Example:
numOfCities = 8
threshold = 1
2 is directly connected to 4, 6, 8 (gcd = 2)
6 is directly connected to 3 (gcd = 3)
therefore 2,4,8 can also reach 3

一种方法：循环遍历所有城市编号并找到直接相连的城市（这会给你一个邻接字典）然后使用该邻接字典（使用广度或深度搜索）查看出发城市是否可以到达目的地城市。

Answer 2

我完全不知道这是否好，但它解决了问题。

from math import gcd

def exists(a, b, t):
    return gcd(a, b) > t

# find goes trough everithing it can
def find(paths, seen, start, end, true, path):
    for i in paths[start]:
        if i in seen or i == true:
            continue
        # creating shortcuts, it may backfire or help performance, it depends
        for j in path:
            paths[i].add(j)
        path.append(i)
        if i == end:
            return True
        seen.add(i)
        if find(paths, seen, i, end, true, path):
            return True
    return False


def solve(nc, t, sc, ec):
    ew = sc + ec

    # create lookup table
    paths = [None] * len(ew)
    for i in range(len(ew)):
        paths[i] = set()

    # fill it
    for i in range(len(ew)):
        for j in range(i+1, len(ew)):
            if exists(ew[i], ew[j], t):
                paths[i].add(j)
                paths[j].add(i)

    # traverse paths to find a values
    res = []
    seen = set()
    path = []
    for i in range(len(sc)):
        if exists(sc[i], ec[i], t) or find(paths, seen, i, i + len(sc), i, path):
            res.append(1)
        else:
            res.append(0)
        seen.clear()
        path.clear()
    return res
            
        

print(solve(10, 1, [4, 10, 4, 3, 6], [4, 3, 6, 2, 9]))

Python 无法比较最大公约数的值

Python can't compare between values from the greatest common divisor

python

algorithm

greatest-common-divisor