Watch 10 video solutions for Minimum Number of Operations to Make All Array Elements Equal to 1, a medium level problem involving Array, Math, Number Theory. This walkthrough by codestorywithMIK has 7,472 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 106Problem Overview: You are given an integer array where one operation replaces nums[i] with gcd(nums[i], nums[i+1]). The goal is to determine the minimum number of operations required to make every element equal to 1. If it’s impossible, return -1. The key observation is that once a single 1 exists in the array, you can propagate it across the array using adjacent GCD operations.
Approach 1: Brute Force by Iterating Over All Pairs (O(n² log A) time, O(1) space)
Start by checking how many elements are already equal to 1. If at least one exists, the remaining elements can be converted using adjacent operations in n - countOfOnes steps. If there are no 1s, search for the smallest subarray whose GCD becomes 1. Use two nested loops: fix a start index, expand the end index, and update the running GCD using gcd(currentGcd, nums[j]). The first time the GCD becomes 1, you know how many operations are required to create a 1 in that segment. Track the minimum length across all pairs.
This approach relies heavily on properties of the number theory concept of GCD. Each GCD computation takes O(log A), giving an overall complexity of O(n² log A). The algorithm uses only a few variables, so space complexity remains constant.
Approach 2: Optimized Scan from Left (O(n² log A) time, O(1) space)
This version improves the brute force idea by scanning the array from left to right and stopping early whenever the running GCD becomes 1. For each starting index i, compute the cumulative GCD while expanding the right pointer. As soon as the GCD becomes 1, the segment can generate a single 1 in length - 1 operations. Once that 1 exists, converting the rest of the array takes another n - 1 operations.
The algorithm keeps track of the shortest segment that produces GCD 1. If none exists, it means the overall array GCD is greater than 1, so producing a 1 is impossible. This optimized scan avoids unnecessary expansions once a valid segment is found and works well for typical constraints.
The logic combines array traversal with repeated GCD reduction from math. The main insight: create a single 1 as cheaply as possible, then spread it across the array.
Recommended for interviews: The optimized left‑scan approach. Interviewers expect you to recognize the GCD property and minimize the subarray length that yields 1. Starting with brute force shows you understand the mechanics, but identifying the shortest GCD‑1 segment demonstrates stronger algorithmic reasoning.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force by Iterating Over All Pairs | O(n² log A) | O(1) | When first exploring the problem and validating how GCD propagation works across subarrays. |
| Optimized Scan from Left | O(n² log A) | O(1) | General case. Finds the shortest subarray with GCD = 1 and minimizes operations. |