Minimum number of operations to make all array elements equal to 1

Array Math Number Theory

54.6% acceptance

Feb 25, 2026

781

You are given a 0-indexed array nums consisting 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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_operations(nums: Vec<i32>) -> i32 {
    let n = nums.len();

    fn gcd(a: i32, b: i32) -> i32 {
      if b == 0 { a } else { gcd(b, a % b) }
    }

    // Count existing 1s
    let ones = nums.iter().filter(|&&x| x == 1).count();
    if ones > 0 {
      return (n - ones) as i32;
    }

    // Find minimum subarray length that has gcd = 1
    let mut min_len = usize::MAX;
    for i in 0..n {
      let mut g = nums[i];
      for j in i..n {
        g = gcd(g, nums[j]);
        if g == 1 {
          min_len = min_len.min(j - i + 1);
          break;
        }
      }
    }

    if min_len == usize::MAX {
      return -1;
    }

    // min_len - 1 operations to create a 1, then n - 1 operations to spread
    (min_len - 1 + n - 1) as i32
  }
}