Minimum Number of Operations to Make All Array Elements Equal to 1

Med

#2411Time: 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.

Patterns

Math Number Theory

Data structures

Array

Prompt

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] <= 10⁶

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

Define a helper function gcd(a, b) that computes the greatest common divisor of two integers.
Count the number of 1s 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.

Walkthrough

First, we handle two edge cases:

If the array already contains 1s, 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 1s.
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 1s 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:

Count the number of 1s in nums. If it's greater than zero, return n - countOnes.
Initialize minLength to a very large value (or n+1).
Iterate through all possible subarray lengths, len, from 2 to n.
For each len, iterate through all possible starting indices, i, from 0 to n - len.
For each subarray nums[i...i+len-1], calculate its GCD.
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.
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.
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.

1class Solution {2    private int gcd(int a, int b) {3        while (b != 0) {4            int temp = b;5            b = a % b;6            a = temp;7        }8        return a;9    }10 11    public int minOperations(int[] nums) {12        int n = nums.length;13        int ones = 0;14        for (int num : nums) {15            if (num == 1) {16                ones++;17            }18        }19 20        if (ones > 0) {21            return n - ones;22        }23 24        // Find shortest subarray with GCD of 125        for (int len = 2; len <= n; len++) {26            for (int i = 0; i <= n - len; i++) {27                int currentGcd = nums[i];28                for (int j = i + 1; j < i + len; j++) {29                    currentGcd = gcd(currentGcd, nums[j]);30                }31                if (currentGcd == 1) {32                    // Found the shortest length, calculate result and return33                    return (len - 1) + (n - 1);34                }35            }36        }37        38        // If no subarray has GCD of 1, it's impossible.39        return -1;40    }41}

Complexity

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.

Trade-offs

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.

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.

Algorithm

Define a helper function gcd(a, b).
Count the number of 1s 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).

Walkthrough

The overall logic remains the same: handle the case with existing 1s and the impossible case first. The improvement lies in how we find the shortest subarray with a GCD of 1 when no 1s are initially present.

The algorithm is as follows:

Count the number of 1s in nums. If countOnes > 0, return n - countOnes.
Initialize minLength to a very large value.
Iterate through the array with an outer loop for the start index i from 0 to n-1.
For each i, start a running GCD calculation. Initialize currentGcd = nums[i].
Use an inner loop for the end index j from i+1 to n-1.
In the inner loop, update the running GCD: currentGcd = gcd(currentGcd, nums[j]).
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.
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.
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.
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.

1class Solution {2    private int gcd(int a, int b) {3        while (b != 0) {4            int temp = b;5            b = a % b;6            a = temp;7        }8        return a;9    }10 11    public int minOperations(int[] nums) {12        int n = nums.length;13        int ones = 0;14        for (int num : nums) {15            if (num == 1) {16                ones++;17            }18        }19 20        if (ones > 0) {21            return n - ones;22        }23 24        int minLength = Integer.MAX_VALUE;25        for (int i = 0; i < n; i++) {26            int currentGcd = nums[i];27            for (int j = i + 1; j < n; j++) {28                currentGcd = gcd(currentGcd, nums[j]);29                if (currentGcd == 1) {30                    minLength = Math.min(minLength, j - i + 1);31                    break; // Found shortest subarray starting at i32                }33            }34        }35 36        if (minLength == Integer.MAX_VALUE) {37            return -1; // Impossible to make a 138        }39 40        return (minLength - 1) + (n - 1);41    }42}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int minOperations(int[] nums) {4    int n = nums.length;5    int cnt = 0;6    for (int x : nums) {7      if (x == 1) {8        ++cnt;9      }10    }11    if (cnt > 0) {12      return n - cnt;13    }14    int mi = n + 1;15    for (int i = 0; i < n; ++i) {16      int g = 0;17      for (int j = i; j < n; ++j) {18        g = gcd(g, nums[j]);19        if (g == 1) {20          mi = Math.min(mi, j - i + 1);21        }22      }23    }24    return mi > n ? -1 : n - 1 + mi - 1;25  }26private27  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }28}

1class Solution {2public:3  int minOperations(vector<int> &nums) {4    int n = nums.size();5    int cnt = 0;6    for (int x : nums) {7      if (x == 1) {8        ++cnt;9      }10    }11    if (cnt) {12      return n - cnt;13    }14    int mi = n + 1;15    for (int i = 0; i < n; ++i) {16      int g = 0;17      for (int j = i; j < n; ++j) {18        g = gcd(g, nums[j]);19        if (g == 1) {20          mi = min(mi, j - i + 1);21        }22      }23    }24    return mi > n ? -1 : n - 1 + mi - 1;25  }26};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem