Minimum Number of Operations to Make All Array Elements Equal to 1
You are given a 0-indexed array nums consisting of positive integers. You can do the following operation on the array any number of times:
- Select an index
isuch that0 <= i < n - 1and replace either ofnums[i]ornums[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
4By first creating a
1 from adjacent values 3 and 4, the remaining elements can each be converted to 1 using adjacent gcd operations, for a total of 4 operations.Example 2
Input
nums = [2,10,6,14]Output
-1It can be shown that it is impossible to make all the elements equal to 1.
Constraints
- 2 <= nums.length <= 50
- 1 <= nums[i] <= 10^6