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:
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].
Example 2:
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 <= 501 <= nums[i] <= 106This approach involves iterating over every possible subarray and calculating the GCD of the subarray. The idea is to find the shortest subarray that has a GCD of 1, indicating that the elements in this subarray can eventually be reduced to ones using successive GCD operations.
This C solution iterates over every subarray of nums. For each subarray, it computes the GCD and checks if it becomes 1. Once the GCD is 1, it determines the number of operations taken to reach that state. It keeps track of the shortest subarray that can become 1, thereby minimizing operations.
C++
Java
Python
C#
JavaScript
The time complexity of this solution is O(n^2) since it involves checking every subarray in the array. The space complexity is O(1) as it uses a fixed amount of space for the GCD calculation.
In this method, we take advantage of the properties of the GCD to search efficiently. We design an algorithm that tries to resolve the problem by linearly scanning for opportunities to achieve a GCD of 1, minimizing redundant calculations.
This C code first checks if the overall GCD of the array is greater than 1, which immediately means conversion to all 1s isn't possible. Next, it looks for the shortest subarray with a GCD of 1, counting needed operations.
C++
Java
Python
C#
JavaScript
The time complexity is O(n^2) due to nested loops, but optimizations reduce redundant calculations after overall GCD check. The space complexity remains O(1), with only a few temporary variables.
| Approach | Complexity |
|---|---|
| Brute Force by Iterating Over All Pairs | The time complexity of this solution is O(n^2) since it involves checking every subarray in the array. The space complexity is O(1) as it uses a fixed amount of space for the GCD calculation. |
| Optimized Scan from Left | The time complexity is O(n^2) due to nested loops, but optimizations reduce redundant calculations after overall GCD check. The space complexity remains O(1), with only a few temporary variables. |
Minimum Operations to Make Array Equal | Leetcode - 1551 • Algorithms Made Easy • 24,165 views views
Watch 9 more video solutions →Practice Minimum Number of Operations to Make All Array Elements Equal to 1 with our built-in code editor and test cases.
Practice on FleetCode