# Minimum Number of Operations to Make All Array Elements Equal to 1
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-operations-to-make-all-array-elements-equal-to-1)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-operations-to-make-all-array-elements-equal-to-1
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array
---
## Problem
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`

# Approaches
## Brute Force Subarray Check
This approach systematically checks every possible contiguous subarray within the input array `nums` to find the shortest one whose elements have a greatest common divisor (GCD) of 1. The core idea is that to make all elements 1, we must first create a `1` if none exists. The minimum number of operations to create a `1` is `k-1`, where `k` is the length of the shortest subarray with a GCD of 1. Once a `1` is created, it takes an additional `n-1` operations to make all other elements `1`.
**Time:** O(n^3 * log(max_val)). The outer loop for `len` runs `n-1` times. The middle loop for `i` runs up to `n` times. The inner loop to calculate the GCD of a subarray of length `len` runs `len-1` times, and each `gcd` call takes `O(log(max_val))` time, where `max_val` is the maximum value in `nums`. This results in a total complexity dominated by the nested loops. · **Space:** O(1). We only use a few variables to store intermediate results.
**Pros:** Conceptually straightforward, directly implementing the definition of finding the shortest subarray.; Correctly solves the problem.
**Cons:** Inefficient due to the triple nested loop structure. It recomputes the GCD for overlapping subarrays multiple times.
### Explanation
First, we handle two edge cases:
1.  If the array already contains `1`s, we don't need to create a `1`. We can use an existing `1` to turn its neighbors into `1`, and so on. The number of operations required is simply the number of elements that are not `1`. This is `n - countOnes`, where `n` is the array length and `countOnes` is the number of `1`s.
2.  It's impossible to create a `1` if the GCD of all elements in the initial array is greater than 1. This is because any number generated by the `gcd` operation will be a multiple of the initial GCD. So, if `gcd(nums) > 1`, we return -1.

If neither of these cases applies (i.e., no `1`s exist, but it's possible to create one), we proceed to find the shortest subarray with a GCD of 1.

The algorithm is as follows:
1.  Count the number of `1`s in `nums`. If it's greater than zero, return `n - countOnes`.
2.  Initialize `minLength` to a very large value (or `n+1`).
3.  Iterate through all possible subarray lengths, `len`, from 2 to `n`.
4.  For each `len`, iterate through all possible starting indices, `i`, from 0 to `n - len`.
5.  For each subarray `nums[i...i+len-1]`, calculate its GCD.
6.  If the GCD is 1, we have found the shortest possible subarray because we are iterating `len` in increasing order. The length is `len`. We can set `minLength = len` and break out of all loops.
7.  If a `minLength` was found, the total number of operations is `(minLength - 1)` (to create the first `1`) plus `(n - 1)` (to propagate the `1` to the other `n-1` elements). Return `minLength - 1 + n - 1`.
8.  If the loops complete and no such subarray is found, it implies impossibility. This happens if the GCD of the entire array is greater than 1.

```java
class Solution {
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public int minOperations(int[] nums) {
        int n = nums.length;
        int ones = 0;
        for (int num : nums) {
            if (num == 1) {
                ones++;
            }
        }

        if (ones > 0) {
            return n - ones;
        }

        // Find shortest subarray with GCD of 1
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int currentGcd = nums[i];
                for (int j = i + 1; j < i + len; j++) {
                    currentGcd = gcd(currentGcd, nums[j]);
                }
                if (currentGcd == 1) {
                    // Found the shortest length, calculate result and return
                    return (len - 1) + (n - 1);
                }
            }
        }
        
        // If no subarray has GCD of 1, it's impossible.
        return -1;
    }
}
```
### Algorithm
*   Define a helper function `gcd(a, b)` that computes the greatest common divisor of two integers.
*   Count the number of `1`s in the input array `nums`. Let this be `ones`.
*   If `ones > 0`, return `nums.length - ones`.
*   Iterate through all possible subarray lengths `len` from 2 to `nums.length`.
*   For each `len`, iterate through all possible start indices `i` from 0 to `nums.length - len`.
*   Calculate the GCD of the subarray `nums[i...i+len-1]`.
    *   Initialize `currentGcd = nums[i]`.
    *   Iterate `j` from `i+1` to `i+len-1`.
    *   Update `currentGcd = gcd(currentGcd, nums[j])`.
*   If `currentGcd == 1`, we have found the shortest subarray. The length is `len`. The total operations are `(len - 1) + (nums.length - 1)`. Return this value.
*   If the loops complete without finding a subarray with GCD 1, it's impossible. Return -1.

## Optimized Subarray Search
This approach improves upon the brute-force method by avoiding redundant GCD calculations. Instead of re-calculating the GCD for every subarray from scratch, we can compute it incrementally. For a fixed starting point `i`, we can find the GCD of `nums[i...j]` by using the already computed GCD of `nums[i...j-1]`. This optimization reduces the time complexity significantly.
**Time:** O(n^2 * log(max_val)). The check for `1`s takes `O(n)`. The nested loops for finding the minimum length subarray run in `O(n^2)`. Inside the inner loop, we perform one `gcd` operation, which takes `O(log(max_val))`. The total time complexity is dominated by the nested loops. · **Space:** O(1). We only use a constant amount of extra space for variables.
**Pros:** Efficient for the given constraints (`n <= 50`).; Correctly handles all cases.; Improves upon the brute-force approach by eliminating redundant computations.
**Cons:** The core logic still relies on checking subarrays, which has a quadratic time complexity. For much larger `n`, this might be too slow.
### Explanation
The overall logic remains the same: handle the case with existing `1`s and the impossible case first. The improvement lies in how we find the shortest subarray with a GCD of 1 when no `1`s are initially present.

The algorithm is as follows:
1.  Count the number of `1`s in `nums`. If `countOnes > 0`, return `n - countOnes`.
2.  Initialize `minLength` to a very large value.
3.  Iterate through the array with an outer loop for the start index `i` from 0 to `n-1`.
4.  For each `i`, start a running GCD calculation. Initialize `currentGcd = nums[i]`.
5.  Use an inner loop for the end index `j` from `i+1` to `n-1`.
6.  In the inner loop, update the running GCD: `currentGcd = gcd(currentGcd, nums[j])`.
7.  If at any point `currentGcd` becomes 1, it means the subarray `nums[i...j]` has a GCD of 1. The length of this subarray is `j - i + 1`.
8.  We update our `minLength` with `min(minLength, j - i + 1)`. Since we are looking for the shortest subarray starting at `i`, we can `break` the inner loop once we find a `1` and move to the next starting index `i+1`.
9.  After checking all possible starting positions `i`, if `minLength` is still at its initial large value, it means no subarray has a GCD of 1. In this scenario, it's impossible to make all elements 1, so we return -1.
10. Otherwise, the minimum operations needed is `(minLength - 1)` (to create the first `1`) plus `(n - 1)` (to make the other elements `1`). Return `minLength - 1 + n - 1`.

```java
class Solution {
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public int minOperations(int[] nums) {
        int n = nums.length;
        int ones = 0;
        for (int num : nums) {
            if (num == 1) {
                ones++;
            }
        }

        if (ones > 0) {
            return n - ones;
        }

        int minLength = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int currentGcd = nums[i];
            for (int j = i + 1; j < n; j++) {
                currentGcd = gcd(currentGcd, nums[j]);
                if (currentGcd == 1) {
                    minLength = Math.min(minLength, j - i + 1);
                    break; // Found shortest subarray starting at i
                }
            }
        }

        if (minLength == Integer.MAX_VALUE) {
            return -1; // Impossible to make a 1
        }

        return (minLength - 1) + (n - 1);
    }
}
```
### Algorithm
*   Define a helper function `gcd(a, b)`.
*   Count the number of `1`s in `nums`. Let this be `ones`.
*   If `ones > 0`, return `nums.length - ones`.
*   Initialize `minLength = Integer.MAX_VALUE`.
*   Iterate `i` from 0 to `nums.length - 1`.
    *   Initialize `currentGcd = nums[i]`.
    *   Iterate `j` from `i + 1` to `nums.length - 1`.
        *   Update `currentGcd = gcd(currentGcd, nums[j])`.
        *   If `currentGcd == 1`:
            *   The length of this subarray is `j - i + 1`.
            *   Update `minLength = min(minLength, j - i + 1)`.
            *   Break the inner loop (as we've found the shortest subarray starting at `i`).
*   If `minLength` is still `Integer.MAX_VALUE`, it's impossible. Return -1.
*   Otherwise, return `(minLength - 1) + (nums.length - 1)`.

# Solutions
### Java

```java
class Solution {
public
  int minOperations(int[] nums) {
    int n = nums.length;
    int cnt = 0;
    for (int x : nums) {
      if (x == 1) {
        ++cnt;
      }
    }
    if (cnt > 0) {
      return n - cnt;
    }
    int mi = n + 1;
    for (int i = 0; i < n; ++i) {
      int g = 0;
      for (int j = i; j < n; ++j) {
        g = gcd(g, nums[j]);
        if (g == 1) {
          mi = Math.min(mi, j - i + 1);
        }
      }
    }
    return mi > n ? -1 : n - 1 + mi - 1;
  }
private
  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

```

### CPP

```cpp
class Solution {
public:
  int minOperations(vector<int> &nums) {
    int n = nums.size();
    int cnt = 0;
    for (int x : nums) {
      if (x == 1) {
        ++cnt;
      }
    }
    if (cnt) {
      return n - cnt;
    }
    int mi = n + 1;
    for (int i = 0; i < n; ++i) {
      int g = 0;
      for (int j = i; j < n; ++j) {
        g = gcd(g, nums[j]);
        if (g == 1) {
          mi = min(mi, j - i + 1);
        }
      }
    }
    return mi > n ? -1 : n - 1 + mi - 1;
  }
};

```

### Python

```python
class Solution:
    def minOperations(self, nums: List[int]) -> int: n = len(nums) cnt = nums . count(1) if cnt: return n - cnt mi = n + 1 for i in range(n): g = 0 for j in range(i, n): g = gcd(g, nums[j]) if g == 1: mi = min(mi, j - i + 1) return - 1 if mi > n else n - 1 + mi - 1

```