2654. Minimum Number of Operations to Make All Array Elements Equal to 1 LeetCode Solution
In this guide, you will get 2654. Minimum Number of Operations to Make All Array Elements Equal to 1 LeetCode Solution with the best time and space complexity. The solution to Minimum Number of Operations to Make All Array Elements Equal to problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Number of Operations to Make All Array Elements Equal to
You are given a 0-indexed array nums consisiting of positive integers. You can do the following operation on the array any number of times:
Select an index i such that 0 <= i < n – 1 and replace either of nums[i] or nums[i+1] with their gcd value.
Return the minimum number of operations to make all elements of nums equal to 1. If it is impossible, return -1.
The gcd of two integers is the greatest common divisor of the two integers.
Example 1:
Input: nums = [2,6,3,4]
Output: 4
Explanation: We can do the following operations:
– Choose index i = 2 and replace nums[2] with gcd(3,4) = 1. Now we have nums = [2,6,1,4].
– Choose index i = 1 and replace nums[1] with gcd(6,1) = 1. Now we have nums = [2,1,1,4].
– Choose index i = 0 and replace nums[0] with gcd(2,1) = 1. Now we have nums = [1,1,1,4].
– Choose index i = 2 and replace nums[3] with gcd(1,4) = 1. Now we have nums = [1,1,1,1].
Input: nums = [2,10,6,14]
Output: -1
Explanation: It can be shown that it is impossible to make all the elements equal to 1.
Constraints:
2 <= nums.length <= 50
1 <= nums[i] <= 106
Complexity Analysis
Time Complexity:
Space Complexity:
2654. Minimum Number of Operations to Make All Array Elements Equal to 1 LeetCode Solution in C++
class Solution {
public:
int minOperations(vector<int>& nums) {
const int n = nums.size();
const int ones = ranges::count(nums, 1);
if (ones > 0)
return n - ones;
// the minimum operations to make the shortest subarray with a gcd == 1
int minOps = INT_MAX;
for (int i = 0; i < n; ++i) {
int g = nums[i];
for (int j = i + 1; j < n; ++j) {
g = __gcd(g, nums[j]);
if (g == 1) { // gcd(nums[i..j]) == 1
minOps = min(minOps, j - i);
break;
}
}
}
// After making the shortest subarray with `minOps`, need additional n - 1
// operations to make the other numbers to 1.
return minOps == INT_MAX ? -1 : minOps + n - 1;
}
}; /* code provided by PROGIEZ */
2654. Minimum Number of Operations to Make All Array Elements Equal to 1 LeetCode Solution in Java
class Solution {
public int minOperations(int[] nums) {
final int n = nums.length;
final int ones = (int) Arrays.stream(nums).filter(num -> num == 1).count();
if (ones > 0)
return n - ones;
// the minimum operations to make the shortest subarray with a gcd == 1
int minOps = Integer.MAX_VALUE;
for (int i = 0; i < n; ++i) {
int g = nums[i];
for (int j = i + 1; j < n; ++j) {
g = gcd(g, nums[j]);
if (g == 1) { // gcd(nums[i..j]) == 1
minOps = Math.min(minOps, j - i);
break;
}
}
}
// After making the shortest subarray with `minOps`, need additional n - 1
// operations to make the other numbers to 1.
return minOps == Integer.MAX_VALUE ? -1 : minOps + n - 1;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
} // code provided by PROGIEZ
2654. Minimum Number of Operations to Make All Array Elements Equal to 1 LeetCode Solution in Python
class Solution:
def minOperations(self, nums: list[int]) -> int:
n = len(nums)
ones = nums.count(1)
if ones > 0:
return n - ones
# the minimum operations to make the shortest subarray with a gcd == 1
minOps = math.inf
for i, g in enumerate(nums):
for j in range(i + 1, n):
g = math.gcd(g, nums[j])
if g == 1: # gcd(nums[i..j]:== 1
minOps = min(minOps, j - i)
break
# After making the shortest subarray with `minOps`, need additional n - 1
# operations to make the other numbers to 1.
return -1 if minOps == math.inf else minOps + n - 1 # code by PROGIEZ
