Minimum Operations to Make Every Array Element One
Otter.ai● MediumFULLTIMEPHONE SCREENProblem statement
Given an array of positive integers, one operation chooses two adjacent elements and replaces either one of them with their greatest common divisor.
Return the minimum number of operations needed to make every element equal to 1, or -1 when it is impossible.
Function
minOperationsToOne(nums: int[]) → intExamples
Example 1
nums = [2,6,3,4]return = 4The shortest adjacent subarray with gcd 1 has length 3; creating one 1 takes two operations and spreading it to the other three positions takes three more, but one position was already in the subarray, for four total.
Example 2
nums = [2,10,6,14]return = -1The gcd of every element is 2, so no operation can create a 1.
Constraints
2 <= nums.length <= 50.1 <= nums[i] <= 10^6.