Daily DSA: Minimum Operations to Equalize Array via GCD (Medium)
Advertisement
Problem Statement
You are given an array of positive integers nums. In one operation, you can choose any two elements nums[i] and nums[j] ($i \neq j$) and replace one of them with their greatest common divisor (GCD).
Return the minimum number of operations required to make all elements in the array equal to 1. If it is impossible to make all elements equal to 1, return -1.
Examples
Example 1:
Input: nums = [2, 6, 3, 4]
Output: 4
Explanation:
- Replace
nums[1](6) withgcd(nums[1], nums[0]) = gcd(6, 2) = 2. Array becomes[2, 2, 3, 4]. - Replace
nums[2](3) withgcd(nums[2], nums[1]) = gcd(3, 2) = 1. Array becomes[2, 2, 1, 4]. - Replace
nums[0](2) withgcd(nums[0], nums[2]) = gcd(2, 1) = 1. Array becomes[1, 2, 1, 4]. - Replace
nums[1](2) withgcd(nums[1], nums[0]) = gcd(2, 1) = 1. Array becomes[1, 1, 1, 4]. - Replace
nums[3](4) withgcd(nums[3], nums[2]) = gcd(4, 1) = 1. Array becomes[1, 1, 1, 1]. Total operations: 4.
Example 2:
Input: nums = [2, 10, 6, 14]
Output: -1
Explanation: The overall GCD of the array is 2, which is greater than 1. It is impossible to reduce the elements to 1.
Constraints
1 <= nums.length <= 501 <= nums[i] <= 10^9
Approach & Hints
- Check Base Cases:
- If the array already contains all
1s, the answer is the count of elements that are not1(which is0). - If the overall GCD of the entire array is greater than
1and there are no existing1s, itβs impossible to create a1, so return-1.
- If the array already contains all
- Count Existing Ones: If there is at least one
1in the array, say there are $C$ ones, we can convert every other element to1using one operation per element. Thus, the answer isn - count_ones. - Find Subarrays with GCD = 1: If there are no
1s initially, we must find the shortest contiguous subarray whose GCD is1. Suppose the minimum length of such a subarray is $L$. We can reduce this subarray to a single1using $L - 1$ operations. Then, we can propagate this1to the rest of the $n - 1$ elements using an additional $n - 1$ operations. Total operations = $(L - 1) + (n - 1) = n + L - 2$.
C++ Solution
#include <vector>
#include <numeric>
#include <algorithm>
class Solution {
public:
int minOperations(std::vector<int>& nums) {
int n = nums.size();
int ones = 0;
int overall_gcd = 0;
for (int x : nums) {
if (x == 1) ones++;
overall_gcd = std::gcd(overall_gcd, x);
}
// If there are already 1s, we just need to convert the non-1 elements.
if (ones > 0) {
return n - ones;
}
// If the total GCD is not 1, we can never produce a 1.
if (overall_gcd > 1) {
return -1;
}
// Find the shortest subarray with GCD equal to 1
int min_len = n + 1;
for (int i = 0; i < n; ++i) {
int current_gcd = 0;
for (int j = i; j < n; ++j) {
current_gcd = std::gcd(current_gcd, nums[j]);
if (current_gcd == 1) {
min_len = std::min(min_len, j - i + 1);
break;
}
}
}
// Operations to form the first 1: min_len - 1
// Operations to spread the 1 to all other elements: n - 1
return (min_len - 1) + (n - 1);
}
};
Complexity Analysis
- Time Complexity: $O(n^2 \log(\text{MAX}))$, where $n$ is the size of the array and $\text{MAX}$ is the maximum element in
nums. The nested loops check all subarrays, taking logarithmic time for each GCD computation. - Space Complexity: $O(1)$ auxiliary space.
Advertisement