Package g2601_2700.s2654_minimum_number_of_operations_to_make_all_array_elements_equal_to_1

Class Solution

java.lang.Object

g2601_2700.s2654_minimum_number_of_operations_to_make_all_array_elements_equal_to_1.Solution

public class Solution
extends Object

2654 - Minimum Number of Operations to Make All Array Elements Equal to 1.<p>Medium</p> <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><strong>Example 1:</strong></p> <p><strong>Input:</strong> nums = [2,6,3,4]</p> <p><strong>Output:</strong> 4</p> <p><strong>Explanation:</strong> We can do the following operations:</p> <ul> <li>Choose index i = 2 and replace nums[2] with gcd(3,4) = 1. Now we have nums = [2,6,1,4].</li> <li>Choose index i = 1 and replace nums[1] with gcd(6,1) = 1. Now we have nums = [2,1,1,4].</li> <li>Choose index i = 0 and replace nums[0] with gcd(2,1) = 1. Now we have nums = [1,1,1,4].</li> <li>Choose index i = 2 and replace nums[3] with gcd(1,4) = 1. Now we have nums = [1,1,1,1].</li> </ul> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> nums = [2,10,6,14]</p> <p><strong>Output:</strong> -1</p> <p><strong>Explanation:</strong> It can be shown that it is impossible to make all the elements equal to 1.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>2 <= nums.length <= 50</code></li> <li><code>1 <= nums[i] <= 10⁶</code></li> </ul> <p><strong>Follow-up:</strong></p> <p>The <code>O(n)</code> time complexity solution works, but could you find an <code>O(1)</code> constant time complexity solution?</p>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	minOperations(int[] nums)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

minOperations

public int minOperations(int[] nums)