mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-01-10 18:48:13 +08:00
39 lines
1.6 KiB
HTML
39 lines
1.6 KiB
HTML
<p>You are given a <strong>0-indexed</strong> array <code>nums</code> consisiting of <strong>positive</strong> integers. You can do the following operation on the array <strong>any</strong> number of times:</p>
|
|
|
|
<ul>
|
|
<li>Select an index <code>i</code> such that <code>0 <= i < n - 1</code> and replace either of <code>nums[i]</code> or <code>nums[i+1]</code> with their gcd value.</li>
|
|
</ul>
|
|
|
|
<p>Return <em>the <strong>minimum</strong> number of operations to make all elements of </em><code>nums</code><em> equal to </em><code>1</code>. If it is impossible, return <code>-1</code>.</p>
|
|
|
|
<p>The gcd of two integers is the greatest common divisor of the two integers.</p>
|
|
|
|
<p> </p>
|
|
<p><strong class="example">Example 1:</strong></p>
|
|
|
|
<pre>
|
|
<strong>Input:</strong> nums = [2,6,3,4]
|
|
<strong>Output:</strong> 4
|
|
<strong>Explanation:</strong> 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].
|
|
</pre>
|
|
|
|
<p><strong class="example">Example 2:</strong></p>
|
|
|
|
<pre>
|
|
<strong>Input:</strong> nums = [2,10,6,14]
|
|
<strong>Output:</strong> -1
|
|
<strong>Explanation:</strong> It can be shown that it is impossible to make all the elements equal to 1.
|
|
</pre>
|
|
|
|
<p> </p>
|
|
<p><strong>Constraints:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>2 <= nums.length <= 50</code></li>
|
|
<li><code>1 <= nums[i] <= 10<sup>6</sup></code></li>
|
|
</ul>
|