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] <= 106To solve #2654 Minimum Number of Operations to Make All Array Elements Equal to 1, the key observation comes from number theory and GCD properties. Since operations reduce numbers using the gcd, a value of 1 acts as a powerful element because gcd(1, x) = 1. If the array already contains one or more 1s, you can propagate them across the array, turning all other elements into 1 with minimal operations.
If no element is initially 1, the goal becomes creating the first 1. This can be done by finding the shortest subarray whose GCD equals 1. Using iterative GCD computation across subarrays helps determine the minimum length required. Once a single 1 is produced, it can be spread to the remaining elements.
The approach combines array traversal and GCD calculations. Efficient implementations rely on repeated gcd updates while expanding subarrays. Typical solutions run in around O(n^2 log A) time due to repeated GCD operations, with constant extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Check existing 1s and propagate | O(n) | O(1) |
| Find shortest subarray with GCD = 1 using iterative GCD | O(n^2 log A) | O(1) |
Algorithms Made Easy
Use these hints if you're stuck. Try solving on your own first.
Note that if you have at least one occurrence of 1 in the array, then you can make all the other elements equal to 1 with one operation each.
Try finding the shortest subarray with a gcd equal to 1.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
The operation effectively reduces values using the greatest common divisor. Because gcd(1, x) is always 1, once a single 1 appears in the array it can be used to transform every other element. This makes identifying or creating a 1 the central goal of the algorithm.
No complex data structure is required. Most solutions rely on simple array traversal combined with repeated GCD calculations using built-in math functions, making it primarily an array and number theory problem.
Problems involving GCD transformations and array operations are common in FAANG-style interviews. While this exact question may vary, the underlying concepts of number theory, greedy reasoning, and subarray GCD calculations are frequently tested.
The optimal strategy relies on GCD properties. If the array already contains 1s, you can convert all other elements to 1 using simple propagation. Otherwise, find the shortest subarray whose GCD equals 1 and use it to create the first 1 before spreading it across the array.