Gcd Sort Of An Array - Leetcode Solution

Problem statement:

Given an integer array nums, your task is to make all elements of the array equal. You can perform the following operations any number of times:

• Choose a subarray of nums and replace all elements with any positive integer. The cost of this operation is the size of the subarray.
• Choose two adjacent elements nums[i] and nums[i + 1], and replace them with their greatest common divisor. The cost of this operation is 1.

Return the minimum cost to make all elements of nums equal.

Solution: To make all elements of the array equal, we can choose the GCD of all the numbers as the final number. But to apply the second operation, we need to check if the GCD of any two adjacent numbers is greater than 1. If it is, we can replace these two numbers with their GCD, and the cost of this operation is 1.

We can use a Union-Find Data Structure to group all the prime factors of the numbers in the array. We first calculate the prime factors of all the numbers in the array and add them to the Union-Find data structure. Then we scan the array and for each adjacent pair of numbers, we check if their GCD is greater than 1. If it is, we find the sets of prime factors for both numbers and merge them in the Union-Find data structure. At the end of this step, we will have all the prime factors of the GCD in a single set.

Finally, we calculate the cost of making all the elements equal. For each prime factor in the set, we count the number of times it appears in the array and add the cost of replacing those elements with the prime factor. The total cost is the sum of costs for all the prime factors.

Implementation: We will use a Union-Find data structure to group all the prime factors of the numbers in the array. We will create a class to represent the Union-Find data structure as follows:

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

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

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False

        if self.rank[px] > self.rank[py]:
            px, py = py, px
        self.parent[px] = py
        if self.rank[px] == self.rank[py]:
            self.rank[py] += 1

        return True

We will also create a function to calculate the prime factors of a number using a sieve of Eratosthenes.

def sieve(n):
    is_prime = [True] * (n + 1)
    primes = []
    for i in range(2, n + 1):
        if is_prime[i]:
            primes.append(i)
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    return primes

def prime_factors(n, primes):
    factors = []
    for p in primes:
        if p > n:
            break
        while n % p == 0:
            factors.append(p)
            n //= p
    if n > 1:
        factors.append(n)
    return factors

Then we can implement the main function to solve the problem.

def gcdSort(nums: List[int]) -> bool:
    n = len(nums)
    primes = sieve(max(nums))
    uf = UnionFind(len(primes))

    for i, num in enumerate(nums):
        factors = prime_factors(num, primes)
        for j in range(1, len(factors)):
            uf.union(primes.index(factors[j-1]), primes.index(factors[j]))

    for i in range(n-1):
        if math.gcd(nums[i], nums[i+1]) > 1:
            uf.union(primes.index(prime_factors(nums[i], primes)[0]), 
                     primes.index(prime_factors(nums[i+1], primes)[0]))

    groups = {}
    for i in range(n):
        p = primes[uf.find(primes.index(prime_factors(nums[i], primes)[0]))]
        if p not in groups:
            groups[p] = []
        groups[p].append(nums[i])

    cost = 0
    for p, nums in groups.items():
        cost += len(nums) - 1

    return cost

Complexity Analysis:

• Time Complexity: O(n * log(n) * log(max(nums))), where n is the length of the input array. We need to calculate the prime factors of each number in the array, which takes O(log(n) * log(max(nums))) time. We also need to use the Union-Find data structure to merge the prime factors of neighboring numbers, which takes O(n * log(n)) time.
• Space Complexity: O(max(nums) + log(max(nums))), to store the prime numbers up to max(nums) and prime factors of each number.

1