Determine whether a node is reachable I am working on this HackerRank problem but running into time constraint issues.

Basically, given two arrays, we need to determine if the ith element of the second array is reachable by the ith element of the first array, where edges are determined by whether or not the gcd of the two node values is greater than some threshold. Below is my attempt but it times out for large inputs.

def computeGCD(x, y):   
   while(y): 
       x, y = y, x % y   
   return x 

def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    if start not in graph.keys():
        return []
    paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, end, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths


def connectedCities(n, g, originCities, destinationCities):
    res = []
    graph = {i+1:[] for i in range(n)}
    for i in originCities:
        for j in range(n):
            if i != j+1 and computeGCD(i, j+1) &gt; g:
                graph[i].append(j+1)

    for i in range(len(originCities)):
        paths = find_all_paths(graph, originCities[i], destinationCities[i])
        if len(paths) &gt; 0:
            res.append(1)
        else:
            res.append(0)

    return res


Can you help me determine if there is something I can be doing more efficiently here, or if solving this via a graph is even the most appropriate way?
def computeGCD(x, y):



Just call it gcd. It's part of a computer program: you don't need to say that it computes.




    graph = {i+1:[] for i in range(n)}
    for i in originCities:
        for j in range(n):
            if i != j+1 and computeGCD(i, j+1) &gt; g:
                graph[i].append(j+1)



This is buggy: it doesn't build the whole graph. Consider test case connectedCities(16, 1, [14], [15]): there is a path 14 -- 6 -- 15 with GCDs respectively 2 and 3.

As a matter of style, I would find the code more readable if it iterated over range(1, n+1) and didn't have to continually increment the variable.




    for i in range(len(originCities)):
        paths = find_all_paths(graph, originCities[i], destinationCities[i])
        if len(paths) &gt; 0:
            res.append(1)
        else:
            res.append(0)



Spot the big performance problem: to determine whether any foo exists, it suffices to find one foo. You don't need to find every foo in the universe and then count them.

But just fixing that still leaves a smaller performance problem: if there are a lot of queries (i.e. if originCities and destinationCities are long) then it's quicker to do an expensive preprocessing to get an object which answers queries fast than it is to evaluate each query separately. As a big hint, in graph-theoretic terms the queries are "Are these two vertices in the same connected component?".

Note that if you really want to squeeze the asymptotic complexity (and it's not too bad for practical performance either), \$O(n \lg \lg n + q)\$ is achievable1 where \$q\$ is the number of queries.

1 Technically there's also a factor of \$\alpha(n)\$ where \$\alpha\$ is the inverse Ackermann function, but for practical purposes it's constant.