Minimum Number of Operations to Make All Array Elements Equal to 1
MediumUpdated: Aug 2, 2025
Practice on:
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
isuch that0 <= i < n - 1and replace either ofnums[i]ornums[i+1]with their gcd value.
Return _theminimum number of operations to make all elements of _nums
equal to1. If it is impossible, return -1.
The gcd of two integers is the greatest common divisor of the two integers.
Examples
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 <= 501 <= nums[i] <= 10^6
Solution
Method 1 – GCD Propagation and Window Search
Intuition
To make all elements 1, we need to either use existing 1s to spread across the array, or create a 1 by finding a subarray whose GCD is 1. If there are already 1s, we can convert all other elements to 1 in minimal moves. Otherwise, we must find the shortest subarray with GCD 1 to generate a 1, then propagate it to the rest.
Approach
- Count the number of
1s innums. - If there are any
1s, answer isn - cnt1(spread the1s to all positions). - If no
1s, check if GCD of all elements is1. If not, return-1(impossible). - Otherwise, for each subarray, find the shortest length with GCD
1. - The answer is
minLen + n - 2(create one1inminLen - 1moves, then spread it inn - 1moves).
Complexity
- ⏰ Time complexity:
O(n^2 * log m)– For each subarray, we compute GCD, where is the max value innums. - 🧺 Space complexity:
O(1)– Only a few variables are used.
Code
C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int minOperations(vector<int>& nums) {
int n = nums.size();
int cnt1 = 0;
for (int x : nums) cnt1 += (x == 1);
if (cnt1) return n - cnt1;
int g = nums[0];
for (int x : nums) g = gcd(g, x);
if (g != 1) return -1;
int minLen = n;
for (int i = 0; i < n; ++i) {
int curGcd = nums[i];
for (int j = i + 1; j < n; ++j) {
curGcd = gcd(curGcd, nums[j]);
if (curGcd == 1) {
minLen = min(minLen, j - i + 1);
break;
}
}
}
return minLen + n - 2;
}
};
Go
func gcd(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
func minOperations(nums []int) int {
n := len(nums)
cnt1 := 0
for _, x := range nums {
if x == 1 { cnt1++ }
}
if cnt1 > 0 { return n - cnt1 }
g := nums[0]
for _, x := range nums { g = gcd(g, x) }
if g != 1 { return -1 }
minLen := n
for i := 0; i < n; i++ {
curGcd := nums[i]
for j := i + 1; j < n; j++ {
curGcd = gcd(curGcd, nums[j])
if curGcd == 1 {
if j-i+1 < minLen { minLen = j - i + 1 }
break
}
}
}
return minLen + n - 2
}
Java
class Solution {
public int minOperations(int[] nums) {
int n = nums.length;
int cnt1 = 0;
for (int x : nums) if (x == 1) cnt1++;
if (cnt1 > 0) return n - cnt1;
int g = nums[0];
for (int x : nums) g = gcd(g, x);
if (g != 1) return -1;
int minLen = n;
for (int i = 0; i < n; i++) {
int curGcd = nums[i];
for (int j = i + 1; j < n; j++) {
curGcd = gcd(curGcd, nums[j]);
if (curGcd == 1) {
minLen = Math.min(minLen, j - i + 1);
break;
}
}
}
return minLen + n - 2;
}
private int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
}
Kotlin
class Solution {
fun minOperations(nums: IntArray): Int {
fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
val n = nums.size
var cnt1 = 0
for (x in nums) if (x == 1) cnt1++
if (cnt1 > 0) return n - cnt1
var g = nums[0]
for (x in nums) g = gcd(g, x)
if (g != 1) return -1
var minLen = n
for (i in 0 until n) {
var curGcd = nums[i]
for (j in i + 1 until n) {
curGcd = gcd(curGcd, nums[j])
if (curGcd == 1) {
minLen = minOf(minLen, j - i + 1)
break
}
}
}
return minLen + n - 2
}
}
Python
from math import gcd
class Solution:
def minOperations(self, nums: list[int]) -> int:
n = len(nums)
cnt1 = sum(x == 1 for x in nums)
if cnt1:
return n - cnt1
g = nums[0]
for x in nums:
g = gcd(g, x)
if g != 1:
return -1
minLen = n
for i in range(n):
curGcd = nums[i]
for j in range(i + 1, n):
curGcd = gcd(curGcd, nums[j])
if curGcd == 1:
minLen = min(minLen, j - i + 1)
break
return minLen + n - 2
Rust
impl Solution {
pub fn min_operations(nums: Vec<i32>) -> i32 {
fn gcd(mut a: i32, mut b: i32) -> i32 {
while b != 0 {
let t = b; b = a % b; a = t;
}
a
}
let n = nums.len() as i32;
let mut cnt1 = 0;
for &x in &nums { if x == 1 { cnt1 += 1; } }
if cnt1 > 0 { return n - cnt1; }
let mut g = nums[0];
for &x in &nums { g = gcd(g, x); }
if g != 1 { return -1; }
let mut min_len = n;
for i in 0..n {
let mut cur_gcd = nums[i as usize];
for j in (i + 1)..n {
cur_gcd = gcd(cur_gcd, nums[j as usize]);
if cur_gcd == 1 {
min_len = min_len.min(j - i + 1);
break;
}
}
}
min_len + n - 2
}
}
TypeScript
function gcd(a: number, b: number): number {
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}
class Solution {
minOperations(nums: number[]): number {
const n = nums.length;
let cnt1 = 0;
for (const x of nums) if (x === 1) cnt1++;
if (cnt1 > 0) return n - cnt1;
let g = nums[0];
for (const x of nums) g = gcd(g, x);
if (g !== 1) return -1;
let minLen = n;
for (let i = 0; i < n; ++i) {
let curGcd = nums[i];
for (let j = i + 1; j < n; ++j) {
curGcd = gcd(curGcd, nums[j]);
if (curGcd === 1) {
minLen = Math.min(minLen, j - i + 1);
break;
}
}
}
return minLen + n - 2;
}
}