#2654
Minimum Number of Operations to Make All Array Elements Equal to 1
specialist · 800 · lc medium +31 · verified · 54.7% accepted · 783 likes · top 47%
Description
You are given a 0-indexed positive integer array nums. In each operation, pick adjacent indices i and i+1 and replace either element with their GCD. Return the minimum operations to make all elements equal to 1, or -1 if it is impossible.
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.
Code
1
2
3