Greatest Common Divisor Traversal

Hard

Asked by:

15 views

Topics:

ArraysGraphsGreedy Algorithms

You are given a 0-indexed integer array nums, and you are allowed to traverse between its indices. You can traverse between index i and index j, i != j, if and only if gcd(nums[i], nums[j]) > 1, where gcd is the greatest common divisor.

Your task is to determine if for every pair of indices i and j in nums, where i < j, there exists a sequence of traversals that can take us from i to j.

Return true if it is possible to traverse between all such pairs of indices, or false otherwise.

Example 1:

Input: nums = [2,3,6]
Output: true
Explanation: In this example, there are 3 possible pairs of indices: (0, 1), (0, 2), and (1, 2).
To go from index 0 to index 1, we can use the sequence of traversals 0 -> 2 -> 1, where we move from index 0 to index 2 because gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1, and then move from index 2 to index 1 because gcd(nums[2], nums[1]) = gcd(6, 3) = 3 > 1.
To go from index 0 to index 2, we can just go directly because gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1. Likewise, to go from index 1 to index 2, we can just go directly because gcd(nums[1], nums[2]) = gcd(3, 6) = 3 > 1.

Example 2:

Input: nums = [3,9,5]
Output: false
Explanation: No sequence of traversals can take us from index 0 to index 2 in this example. So, we return false.

Example 3:

Input: nums = [4,3,12,8]
Output: true
Explanation: There are 6 possible pairs of indices to traverse between: (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), and (2, 3). A valid sequence of traversals exists for each pair, so we return true.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the numbers in the input array, and can they be negative or zero?
If no traversal is possible connecting all numbers, what should the function return (e.g., false, null, throw an exception)?
Are there any constraints on the size of the input array?
If multiple traversals are possible, is any valid traversal acceptable, or is there a specific criterion to optimize for (e.g., shortest path)?
Are the numbers in the array guaranteed to be integers, or could they be floating-point numbers?

Brute Force Solution

Approach

Imagine you have a set of numbers and you want to find out if you can travel between any two numbers by only moving to numbers that share a common factor greater than 1. The brute force way is to just check every possible path between every pair of numbers.

Here's how the algorithm would work step-by-step:

For every number, consider every other number as a potential destination.
For each pair of starting and destination numbers, explore all possible routes through the other numbers.
To explore a route, start from the starting number and check if it shares a common factor with any other number in the set.
If it does, consider moving to that number.
From this new number, again check for common factors with other numbers (excluding the one you just came from) and continue exploring.
Keep track of the numbers visited in the current route. Make sure not to visit the same number twice in a single route to avoid going in circles.
If, at any point, you reach the destination number, then you've found a valid path for that pair.
Repeat this process, exploring all possible routes, until you have either found a valid path or exhausted all possibilities.
If after checking all pairs of numbers, you find a valid path between all pairs, the traversal is possible.

Code Implementation

def greatest_common_divisor_traversal(numbers):
    def gcd(first_number, second_number):
        while second_number:
            first_number, second_number = second_number, first_number % second_number
        return first_number

    def has_path(start_number_index, destination_number_index, number_list):
        number_of_numbers = len(number_list)
        visited = [False] * number_of_numbers
        queue = [start_number_index]
        visited[start_number_index] = True

        while queue:
            current_number_index = queue.pop(0)

            if current_number_index == destination_number_index:
                return True

            for next_number_index in range(number_of_numbers):
                # Avoid cycles and check if they share factors.
                if not visited[next_number_index] and gcd(number_list[current_number_index], number_list[next_number_index]) > 1:
                    visited[next_number_index] = True
                    queue.append(next_number_index)
        return False

    number_of_numbers = len(numbers)

    # Iterate through all possible pairs to check if a path exists between each
    for start_number_index in range(number_of_numbers):
        for destination_number_index in range(number_of_numbers):
            if start_number_index != destination_number_index:
                # If no path exists, immediately return False
                if not has_path(start_number_index, destination_number_index, numbers):
                    return False
    return True

Big(O) Analysis

Time Complexity

O(n^n) – The algorithm iterates through all possible pairs of numbers, leading to n * (n-1) pairs which is O(n^2). For each pair, it explores all possible routes. In the worst-case scenario, each number can be visited in a route, excluding cycles. The number of such routes can grow exponentially with n. The process of finding common factors within each route involves checking all other numbers, thus each hop in a path can take O(n) time to compute the GCD with remaining node options. The length of the paths can also scale to n so this can happen n times. Therefore, the overall time complexity becomes approximately O(n^2 * n^(n-2)) which simplifies to O(n^n).

Space Complexity

O(N^2) – The brute force approach explores all possible routes between pairs of numbers. To keep track of visited numbers in each route and avoid cycles, a set or array of size at most N (the number of input numbers) might be needed. Since this exploration is done for every possible pair of numbers, in the worst case, we could be storing N such sets or arrays, leading to a space complexity of O(N * N) = O(N^2). The recursion stack depth can also reach N in the worst case, further contributing to O(N) space, but the sets/arrays to track visited nodes for all pairs dominate the space complexity.

Optimal Solution

Approach

The challenge is to determine if you can travel between any two numbers in a list by repeatedly moving to a number that shares a common factor (greater than 1) with the current number. We will use a concept of connected groups and a way to efficiently find common factors to solve this.

Here's how the algorithm would work step-by-step:

First, find all the prime factors for each number in the list. Think of each number as having a collection of prime number building blocks.
Imagine each number and each prime factor as a separate 'island'. Connect 'islands' if a number's prime factors include that prime.
Now, use a process to group all the connected 'islands' together. If two 'islands' are connected, they belong to the same group.
Check if all the original numbers from the list belong to one big connected group. If they do, you can travel between any two numbers.
If there's more than one group, it means some numbers cannot be reached from others through shared prime factors, and you cannot make the required traversal.

Code Implementation

def greatest_common_divisor_traversal(numbers):
    number_count = len(numbers)
    prime_factor_map = [[] for _ in range(number_count)]

    def find_prime_factors(number):
        factors = set()
        divisor = 2
        while divisor * divisor <= number:
            if number % divisor == 0:
                factors.add(divisor)
                while number % divisor == 0:
                    number //= divisor
            divisor += 1
        if number > 1:
            factors.add(number)
        return factors

    for i in range(number_count):
        prime_factor_map[i] = find_prime_factors(numbers[i])

    parent = list(range(number_count + len(set(factor for factors in prime_factor_map for factor in factors))))
    size = [1] * len(parent)

    def find(node):
        if parent[node] != node:
            parent[node] = find(parent[node])
        return parent[node]

    def union(node_one, node_two):
        root_one = find(node_one)
        root_two = find(node_two)
        if root_one != root_two:
            if size[root_one] < size[root_two]:
                root_one, root_two = root_two, root_one
            parent[root_two] = root_one
            size[root_one] += size[root_two]

    prime_to_index = {}
    index_counter = number_count

    # Connect numbers to their prime factors
    for i in range(number_count):
        for factor in prime_factor_map[i]:
            if factor not in prime_to_index:
                prime_to_index[factor] = index_counter
                index_counter += 1
            union(i, prime_to_index[factor])

    # Find the root of the first number
    root_of_first = find(0)
    # Check if all numbers have the same root
    for i in range(1, number_count):
        if find(i) != root_of_first:
            return False

    return True

Big(O) Analysis

Time Complexity

O(n * sqrt(maxVal)) – Finding prime factors for each number takes O(sqrt(maxVal)) where maxVal is the maximum value in the input array nums. Since we perform this factorization for each of the n numbers in the input array, the overall time complexity is dominated by this factorization step. Union find operations are typically O(alpha(n)) which is nearly constant, so its contribution is insignificant compared to the factorization.

Space Complexity

O(N + sqrt(M)) – The space complexity is determined by storing prime factors for each number and the disjoint set union data structure. Storing prime factors for each of the N numbers uses O(sqrt(M)) space per number in the worst case, where M is the maximum value in the input array, because we iterate up to the square root of the number to find prime factors. The disjoint set union data structure for N numbers requires O(N) space to store the parent and rank information. Therefore, the auxiliary space complexity is O(N + N*sqrt(M)) which simplifies to O(N + sqrt(M)) assuming M > N.

Edge Cases

Case	How to Handle
Empty input array	Return true if the array is empty or contains only one element, as traversal is trivially possible.
Array with a single element	Return true, as traversal from a single element is always possible to itself.
Array with large numbers causing potential integer overflow in GCD calculation	Use appropriate data types (e.g., long) to prevent integer overflow during GCD calculations.
Array containing only prime numbers	If no two numbers share a common divisor (other than 1), the traversal should not be possible unless they are adjacent in the desired path; return false if path is not possible.
Array contains duplicate numbers that form disconnected components	The Union-Find algorithm correctly handles duplicates by merging their sets, and if the start and end points belong to the same connected component, traversal is possible; otherwise, return false.
The array is extremely large	Optimize the GCD calculation (e.g., using Euclidean algorithm) and Union-Find operations to maintain acceptable performance for large arrays.
No path exists between the start and end nodes	The Union-Find structure's connected components will not include both start and end if no path exists; return false in that scenario.
Numbers in the array are very close to each other	This may lead to many common divisors, so the Union-Find operations and the graph will be denser than sparse, but Union-Find should still handle this correctly.

Empty input array

How to Handle:

Return true if the array is empty or contains only one element, as traversal is trivially possible.

Array with a single element

How to Handle:

Return true, as traversal from a single element is always possible to itself.

Array with large numbers causing potential integer overflow in GCD calculation

How to Handle:

Use appropriate data types (e.g., long) to prevent integer overflow during GCD calculations.

Array containing only prime numbers

How to Handle:

If no two numbers share a common divisor (other than 1), the traversal should not be possible unless they are adjacent in the desired path; return false if path is not possible.

Array contains duplicate numbers that form disconnected components

How to Handle:

The Union-Find algorithm correctly handles duplicates by merging their sets, and if the start and end points belong to the same connected component, traversal is possible; otherwise, return false.

The array is extremely large

How to Handle:

Optimize the GCD calculation (e.g., using Euclidean algorithm) and Union-Find operations to maintain acceptable performance for large arrays.

No path exists between the start and end nodes

How to Handle:

The Union-Find structure's connected components will not include both start and end if no path exists; return false in that scenario.

Numbers in the array are very close to each other

How to Handle:

This may lead to many common divisors, so the Union-Find operations and the graph will be denser than sparse, but Union-Find should still handle this correctly.