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:

• Select an index?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 <= 50

• 1 <= nums[i] <= 106

?其實(shí)就是判斷最大公約數(shù)為1的最小數(shù)組大小。

如果存在1，那么就一定可以。

剩下就是找最大公約數(shù)了，

先寫一個(gè)函數(shù)找最大公約數(shù)，也就是遞歸的輾轉(zhuǎn)相除的方法，

再寫一個(gè)函數(shù)計(jì)算每個(gè)子數(shù)組能不能實(shí)現(xiàn)最大公約數(shù)是1；

依次返回min值；即可；

下面是代碼：

Runtime:?2 ms, faster than?59.08%?of?Java?online submissions for?Minimum Number of Operations to Make All Array Elements Equal to 1.

Memory Usage:?42.2 MB, less than?60.27%?of?Java?online submissions for?Minimum Number of Operations to Make All Array Elements Equal to 1.