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 Window Search
Intuition
If the GCD of the whole array is not 1, it's impossible. Otherwise, find the shortest subarray with GCD 1; we can propagate 1 to all elements in n-1 moves, but need extra moves to create the first 1.
Approach
- If gcd of all nums > 1, return -1.
- For every subarray, compute its GCD; if it's 1, update the minimum length.
- The answer is (min length - 1) + (n - 1).
Code
C++
#include <vector>
#include <numeric>
using namespace std;
class Solution {
public:
int minOperations(vector<int>& nums) {
int n = nums.size(), minlen = n + 1;
int allgcd = nums[0];
for (int x : nums) allgcd = gcd(allgcd, x);
if (allgcd != 1) return -1;
for (int i = 0; i < n; ++i) {
int g = nums[i];
for (int j = i; j < n; ++j) {
g = gcd(g, nums[j]);
if (g == 1) {
minlen = min(minlen, j - i + 1);
break;
}
}
}
return minlen - 1 + n - 1;
}
};
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)
allgcd := nums[0]
for _, x := range nums { allgcd = gcd(allgcd, x) }
if allgcd != 1 { return -1 }
minlen := n + 1
for i := 0; i < n; i++ {
g := nums[i]
for j := i; j < n; j++ {
g = gcd(g, nums[j])
if g == 1 {
if j-i+1 < minlen { minlen = j - i + 1 }
break
}
}
}
return minlen - 1 + n - 1
}
Java
class Solution {
public int minOperations(int[] nums) {
int n = nums.length, minlen = n + 1;
int allgcd = nums[0];
for (int x : nums) allgcd = gcd(allgcd, x);
if (allgcd != 1) return -1;
for (int i = 0; i < n; ++i) {
int g = nums[i];
for (int j = i; j < n; ++j) {
g = gcd(g, nums[j]);
if (g == 1) {
minlen = Math.min(minlen, j - i + 1);
break;
}
}
}
return minlen - 1 + n - 1;
}
private int gcd(int a, int b) {
while (b != 0) {
int t = b; b = a % b; a = t;
}
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 allgcd = nums[0]
for (x in nums) allgcd = gcd(allgcd, x)
if (allgcd != 1) return -1
var minlen = n + 1
for (i in 0 until n) {
var g = nums[i]
for (j in i until n) {
g = gcd(g, nums[j])
if (g == 1) {
minlen = minOf(minlen, j - i + 1)
break
}
}
}
return minlen - 1 + n - 1
}
}
Python
from math import gcd
class Solution:
def minOperations(self, nums: list[int]) -> int:
from math import gcd
n = len(nums)
allgcd = nums[0]
for x in nums:
allgcd = gcd(allgcd, x)
if allgcd != 1:
return -1
minlen = n + 1
for i in range(n):
g = nums[i]
for j in range(i, n):
g = gcd(g, nums[j])
if g == 1:
minlen = min(minlen, j - i + 1)
break
return minlen - 1 + n - 1
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 allgcd = nums[0];
for &x in &nums { allgcd = gcd(allgcd, x); }
if allgcd != 1 { return -1; }
let mut minlen = n + 1;
for i in 0..n {
let mut g = nums[i as usize];
for j in i..n {
g = gcd(g, nums[j as usize]);
if g == 1 {
minlen = minlen.min(j - i + 1);
break;
}
}
}
minlen - 1 + n - 1
}
}
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 allgcd = nums[0];
for (const x of nums) allgcd = gcd(allgcd, x);
if (allgcd !== 1) return -1;
let minlen = n + 1;
for (let i = 0; i < n; ++i) {
let g = nums[i];
for (let j = i; j < n; ++j) {
g = gcd(g, nums[j]);
if (g === 1) {
minlen = Math.min(minlen, j - i + 1);
break;
}
}
}
return minlen - 1 + n - 1;
}
}
Complexity
- ⏰ Time complexity:
O(n^2)— n = length of nums, for all subarrays. - 🧺 Space complexity:
O(1)— only a few variables.