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

Question

I am trying to work through this hackerrank problem:

This is my attempt:

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

But for an input of:

10
1
4
10
4
3
6
4
3
6
2
9

My output is:

Your Output (stdout)
0
1
0
1


Expected Output
1
1
1
1

Answer 1

i have absolutly no idea if this is good or not but it solves the problem all right.

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]))