Introduction

In this blog post, we will explore how to solve the LeetCode problem "1627" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

We have n cities labeled from 1 to n. Two different cities with labels x and y are directly connected by a bidirectional road if and only if x and y share a common divisor strictly greater than some threshold. More formally, cities with labels x and y have a road between them if there exists an integer z such that all of the following are true: x % z == 0, y % z == 0, and z > threshold. Given the two integers, n and threshold, and an array of queries, you must determine for each queries[i] = [ai, bi] if cities ai and bi are connected directly or indirectly. (i.e. there is some path between them). Return an array answer, where answer.length == queries.length and answer[i] is true if for the ith query, there is a path between ai and bi, or answer[i] is false if there is no path. Example 1: Input: n = 6, threshold = 2, queries = [[1,4],[2,5],[3,6]] Output: [false,false,true] Explanation: The divisors for each number: 1: 1 2: 1, 2 3: 1, 3 4: 1, 2, 4 5: 1, 5 6: 1, 2, 3, 6 Using the underlined divisors above the threshold, only cities 3 and 6 share a common divisor, so they are the only ones directly connected. The result of each query: [1,4] 1 is not connected to 4 [2,5] 2 is not connected to 5 [3,6] 3 is connected to 6 through path 3--6 Example 2: Input: n = 6, threshold = 0, queries = [[4,5],[3,4],[3,2],[2,6],[1,3]] Output: [true,true,true,true,true] Explanation: The divisors for each number are the same as the previous example. However, since the threshold is 0, all divisors can be used. Since all numbers share 1 as a divisor, all cities are connected. Example 3: Input: n = 5, threshold = 1, queries = [[4,5],[4,5],[3,2],[2,3],[3,4]] Output: [false,false,false,false,false] Explanation: Only cities 2 and 4 share a common divisor 2 which is strictly greater than the threshold 1, so they are the only ones directly connected. Please notice that there can be multiple queries for the same pair of nodes [x, y], and that the query [x, y] is equivalent to the query [y, x]. Constraints: 2 <= n <= 104 0 <= threshold <= n 1 <= queries.length <= 105 queries[i].length == 2 1 <= ai, bi <= cities ai != bi

Explanation

Here's the solution to the problem:

• Union-Find: Utilize the Union-Find data structure to efficiently track connected components. Iterate through potential common divisors greater than the threshold. For each divisor, unite all cities divisible by that divisor into the same connected component.

• Query Processing: For each query, check if the two cities belong to the same connected component using the Find operation of the Union-Find data structure.

• Optimization: Optimize the divisor iteration by only considering divisors up to n/2 as if a number x and y share a common divisor z > n/2, it implies that both x and y must equal z.

• Runtime and Space Complexity: Time Complexity: O(n log n + q), where n is the number of cities, and q is the number of queries. Space Complexity: O(n)

Code

    class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.rank = [0] * (n + 1)

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            elif self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1


def are_connected(n: int, threshold: int, queries: list[list[int]]) -> list[bool]:
    """
    Determines if cities ai and bi are connected directly or indirectly for each query.

    Args:
        n: The number of cities labeled from 1 to n.
        threshold: The threshold for common divisors.
        queries: An array of queries, where queries[i] = [ai, bi].

    Returns:
        An array answer, where answer.length == queries.length and answer[i] is true if
        there is a path between ai and bi, or answer[i] is false if there is no path.
    """

    uf = UnionFind(n)

    for divisor in range(threshold + 1, n // 2 + 1):
        for i in range(divisor * 2, n + 1, divisor):
            uf.union(divisor, i)

    if threshold == 0:
        for i in range(1, n + 1):
            uf.union(1, i)

    answer = []
    for a, b in queries:
        answer.append(uf.find(a) == uf.find(b))

    return answer