# Solving Leetcode Interviews in Seconds with AI: Minimum Number of Operations to Make All Array Elements Equal to 1


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "2654" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> 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  

	# Explanation
	Here's the approach, complexity, and Python code for the problem:

*   **Core Idea:** The fundamental idea is to find the shortest contiguous subarray within `nums` whose greatest common divisor (GCD) is 1. Once such a subarray is found, we can transform the entire array to 1s using `n - 1` operations for that subarray + operations needed to generate the subarray.
*   **GCD Computation:**  An efficient GCD function is used (Euclidean Algorithm).
*   **Impossibility Check:** Before proceeding, verify if the GCD of the entire array is 1. If not, it's impossible to make all elements 1.

*   **Time Complexity:** O(n^2 * log(max(nums))) where n is the length of `nums`. The `log(max(nums))` factor comes from the GCD calculation.
*   **Space Complexity:** O(1)

	
	# Code
	```python
	def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def solve():
    n = int(input())
    nums = list(map(int, input().split()))

    g = nums[0]
    for i in range(1, n):
        g = gcd(g, nums[i])

    if g != 1:
        print(-1)
        return

    min_len = float('inf')
    for i in range(n):
        current_gcd = nums[i]
        for j in range(i, n):
            current_gcd = gcd(current_gcd, nums[j])
            if current_gcd == 1:
                min_len = min(min_len, j - i + 1)
                break

    if min_len == 1:
        print(n - nums.count(1))
    else:
        print(min_len + n - 2) # n-1 to get everything to 1 *BEFORE* calculating the min_len subarray (n-1 + min_len -1), minus 1 since we used min_len already.


#Input reading and function invocation, handling multiple test cases:
t = int(input()) # number of test cases

for _ in range(t):
    solve()
	```