Problem Description
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. Given the two integers, n and threshold, and an array of queries, you must determine for each queries[i] = [a_i, b_i] if cities a_i and b_i are connected directly or indirectly. Return an array answer, where answer.length == queries.length and answer[i] is true if for the i-th query, there is a path between a_i and b_i, or answer[i] is false if there is no path.
Key Insights
- Cities are connected if they share a common divisor greater than the threshold.
- This problem can be modeled as a graph where nodes are cities and edges represent connections based on shared divisors.
- Efficiently determining connections requires union-find (disjoint-set) data structure to manage connections dynamically.
- Preprocess the cities to build connections based on divisors greater than the threshold.
Space and Time Complexity
Time Complexity: O(n log n + q α(n)), where n is the number of cities, q is the number of queries, and α is the inverse Ackermann function. Space Complexity: O(n), for storing the parent and rank arrays in the union-find structure.
Solution
To solve the problem, we can use the union-find data structure to group cities that are directly or indirectly connected. We will iterate through possible divisors greater than the threshold and connect cities that share these divisors. After processing, we can answer each query by checking if two cities belong to the same connected component.