Minimum Number of Operations to Make All Array Elements Equal to 1 solution and explanation
Google
9 more videos on this problem
Minimum Number of Operations to Make All Array Elements Equal to 1 | Easy Intuition | Leetcode 2654codestorywithMIK · 23:40 · 8K views
Minimum Number of Operations to Make All Array Elements Equal to 1 - Leetcode 2654 - PythonNeetCodeIO · 24:08 · 5K views
2654. Minimum Number of Operations to Make All Array Elements Equal to 1 | LeetCode Weekly 342Deep Tech · 13:54 · 1K views
Leetcode Weekly contest 342 - Minimum Number of Operations to Make All Array Elements Equal to 1Prakhar Agrawal · 8:33 · 1K views
Minimum Number of Operations to Make All Array Elements Equal to 1 | Harder Follow-ups | Weekly 342codingMohan · 31:13 · 1K views
Minimum Number of Operations to Make All Array Elements Equal to 1 | LeetCode 2654Sanyam IIT Guwahati · 15:38 · 1K views
2654. Minimum Number of Operations to Make All Array Elements Equal to 1 (Leetcode Hard)Programming Live with Larry · 39:57 · 630 views
6392. Minimum Number of Operations to Make All Array Elements Equal to 1 LEETCODE WEEKLY CONTEST 342Joyjit Codes · 7:47 · 592 views
Leetcode 2654. Minimum Number of Operations to Make All Array Elements Equal to 1 | Leetcode contestOffCampus Phodenge | Aman Chowdhury · 18:34 · 414 views
Minimum Number of Operations to Make All Array Elements Equal to 1 - Leetcode 2654 - PythonAlgorithms Casts · 19:24 · 271 views
The 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 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 <= 501 <= nums[i] <= 106
Approach overview
Problem Overview: You are given an integer array where one operation replaces nums[i] with gcd(nums[i], nums[i+1]). The goal is to determine the minimum number of operations required to make every element equal to 1. If it’s impossible, return -1. The key observation is that once a single 1 exists in the array, you can propagate it across the array using adjacent GCD operations.
Approach 1: Brute Force by Iterating Over All Pairs (O(n² log A) time, O(1) space)
Start by checking how many elements are already equal to 1. If at least one exists, the remaining elements can be converted using adjacent operations in n - countOfOnes steps. If there are no 1s, search for the smallest subarray whose GCD becomes 1. Use two nested loops: fix a start index, expand the end index, and update the running GCD using gcd(currentGcd, nums[j]). The first time the GCD becomes 1, you know how many operations are required to create a 1 in that segment. Track the minimum length across all pairs.
This approach relies heavily on properties of the number theory concept of GCD. Each GCD computation takes O(log A), giving an overall complexity of O(n² log A). The algorithm uses only a few variables, so space complexity remains constant.
Approach 2: Optimized Scan from Left (O(n² log A) time, O(1) space)
This version improves the brute force idea by scanning the array from left to right and stopping early whenever the running GCD becomes 1. For each starting index i, compute the cumulative GCD while expanding the right pointer. As soon as the GCD becomes 1, the segment can generate a single 1 in length - 1 operations. Once that 1 exists, converting the rest of the array takes another n - 1 operations.
The algorithm keeps track of the shortest segment that produces GCD 1. If none exists, it means the overall array GCD is greater than 1, so producing a 1 is impossible. This optimized scan avoids unnecessary expansions once a valid segment is found and works well for typical constraints.
The logic combines array traversal with repeated GCD reduction from math. The main insight: create a single 1 as cheaply as possible, then spread it across the array.
Recommended for interviews: The optimized left‑scan approach. Interviewers expect you to recognize the GCD property and minimize the subarray length that yields 1. Starting with brute force shows you understand the mechanics, but identifying the shortest GCD‑1 segment demonstrates stronger algorithmic reasoning.
Approach 1: Brute Force by Iterating Over All Pairs
This approach involves iterating over every possible subarray and calculating the GCD of the subarray. The idea is to find the shortest subarray that has a GCD of 1, indicating that the elements in this subarray can eventually be reduced to ones using successive GCD operations.
import math
def min_operations(nums):
n = len(nums)
min_ops = float('inf')
for i in range(n):
current_gcd = nums[i]
for j in range(i, n):
current_gcd = math.gcd(current_gcd, nums[j])
if current_gcd == 1:
min_ops = min(min_ops, j - i)
break
return -1 if min_ops == float('inf') else (min_ops + n - 1)
nums = [2, 6, 3, 4]
print(min_operations(nums)) # Output: 4import java.util.Arrays;
class Solution {
public int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public int minOperations(int[] nums) {
int n = nums.length;
int minOps = Integer.MAX_VALUE;
for (int i = 0; i < n; ++i) {
int currentGCD = nums[i];
for (int j = i; j < n; ++j) {
currentGCD = gcd(currentGCD, nums[j]);
if (currentGCD == 1) {
minOps = Math.min(minOps, j - i);
break;
}
}
}
return minOps == Integer.MAX_VALUE ? -1 : (minOps + n - 1);
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {2,6,3,4};
System.out.println(sol.minOperations(nums));
}
}#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int minOperations(vector<int>& nums) {
int n = nums.size();
int minOps = INT_MAX;
for (int i = 0; i < n; ++i) {
int currentGCD = nums[i];
for (int j = i; j < n; ++j) {
currentGCD = gcd(currentGCD, nums[j]);
if (currentGCD == 1) {
minOps = min(minOps, j - i);
break;
}
}
}
return minOps == INT_MAX ? -1 : (minOps + n - 1);
}
int main() {
vector<int> nums = {2, 6, 3, 4};
cout << minOperations(nums) << endl;
return 0;
}function gcd(a, b) {
while (b !== 0) {
const temp = b;
b = a % b;
a = temp;
}
return a;
}
function minOperations(nums) {
const n = nums.length;
let minOps = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < n; i++) {
let currentGCD = nums[i];
for (let j = i; j < n; j++) {
currentGCD = gcd(currentGCD, nums[j]);
if (currentGCD === 1) {
minOps = Math.min(minOps, j - i);
break;
}
}
}
return minOps === Number.MAX_SAFE_INTEGER ? -1 : (minOps + n - 1);
}
console.log(minOperations([2, 6, 3, 4])); // Output: 4#include <stdio.h>
#include <limits.h>
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int minOperations(int* nums, int numsSize) {
int minOperations = INT_MAX;
for (int i = 0; i < numsSize; ++i) {
int currentGCD = nums[i];
for (int j = i; j < numsSize; ++j) {
currentGCD = gcd(currentGCD, nums[j]);
if (currentGCD == 1) {
minOperations = (j - i) < minOperations ? (j - i) : minOperations;
break;
}
}
}
return minOperations == INT_MAX ? -1 : (minOperations + numsSize - 1);
}
int main() {
int nums[] = {2, 6, 3, 4};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int result = minOperations(nums, numsSize);
printf("%d\n", result);
return 0;
}using System;
class Solution {
public 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 minOps = Int32.MaxValue;
for (int i = 0; i < n; ++i) {
int currentGCD = nums[i];
for (int j = i; j < n; ++j) {
currentGCD = Gcd(currentGCD, nums[j]);
if (currentGCD == 1) {
minOps = Math.Min(minOps, j - i);
break;
}
}
}
return minOps == Int32.MaxValue ? -1 : (minOps + n - 1);
}
static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.MinOperations(new int[] {2, 6, 3, 4})); // Output: 4
}
}This Python code goes through each subarray, calculates the GCD for it, and checks if the GCD is 1. It tracks the shortest subarray length whose GCD becomes 1, thus computing minimum operations required.
The time complexity is O(n^2), acknowledging the examination of every subarray. Space complexity remains O(1) due to simple variable use for GCD calculations.
Approach 2: Optimized Scan from Left
In this method, we take advantage of the properties of the GCD to search efficiently. We design an algorithm that tries to resolve the problem by linearly scanning for opportunities to achieve a GCD of 1, minimizing redundant calculations.
import math
def min_operations(nums):
totalGCD = nums[0]
for num in nums[1:]:
totalGCD = math.gcd(totalGCD, num)
if totalGCD > 1:
return -1
n = len(nums)
min_length = n
for i in range(n):
currentGCD = nums[i]
j = i
while j < n and currentGCD != 1:
currentGCD = math.gcd(currentGCD, nums[j])
j += 1
if currentGCD == 1:
min_length = min(min_length, j - i)
return min_length - 1 + n if min_length != n else -1
nums = [2, 6, 3, 4]
print(min_operations(nums))class Solution {
public 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 totalGCD = nums[0];
for (int i = 1; i < n; ++i) {
totalGCD = gcd(totalGCD, nums[i]);
}
if (totalGCD > 1) return -1;
int minLength = n;
for (int i = 0; i < n; i++) {
int currentGCD = nums[i];
for (int j = i; j < n && currentGCD != 1; j++) {
currentGCD = gcd(currentGCD, nums[j]);
if (currentGCD == 1) {
minLength = Math.min(minLength, j - i + 1);
}
}
}
return minLength == n ? -1 : minLength - 1 + n;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.minOperations(new int[]{2, 6, 3, 4}));
}
}#include <iostream>
#include <vector>
using namespace std;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int minOperations(vector<int>& nums) {
int n = nums.size();
int totalGCD = nums[0];
for (int i = 1; i < n; ++i) {
totalGCD = gcd(totalGCD, nums[i]);
}
if (totalGCD > 1) return -1;
int minLength = n;
for (int i = 0; i < n; ++i) {
int currentGCD = nums[i];
for (int j = i; j < n && currentGCD != 1; ++j) {
currentGCD = gcd(currentGCD, nums[j]);
if (currentGCD == 1) {
minLength = min(minLength, j - i + 1);
}
}
}
return (minLength == n ? -1 : minLength - 1 + n);
}
int main() {
vector<int> nums = {2, 6, 3, 4};
cout << minOperations(nums) << endl;
return 0;
}function gcd(a, b) {
while (b !== 0) {
const temp = b;
b = a % b;
a = temp;
}
return a;
}
function minOperations(nums) {
let totalGCD = nums[0];
const n = nums.length;
for (let i = 1; i < n; i++) {
totalGCD = gcd(totalGCD, nums[i]);
}
if (totalGCD > 1) return -1;
let minLength = n;
for (let i = 0; i < n; i++) {
let currentGCD = nums[i];
for (let j = i; j < n && currentGCD !== 1; j++) {
currentGCD = gcd(currentGCD, nums[j]);
if (currentGCD === 1) {
minLength = Math.min(minLength, j - i + 1);
}
}
}
return minLength === n ? -1 : minLength - 1 + n;
}
console.log(minOperations([2, 6, 3, 4]));#include <stdio.h>
int gcd(int a, int b) {
while (b) {
int t = b;
b = a % b;
a = t;
}
return a;
}
int minOperations(int* nums, int numsSize) {
int totalGCD = nums[0];
for (int i = 1; i < numsSize; ++i) {
totalGCD = gcd(totalGCD, nums[i]);
}
if (totalGCD > 1) {
return -1;
}
int minLength = numsSize;
for (int i = 0; i < numsSize; ++i) {
int currentGCD = nums[i];
for (int j = i; j < numsSize && currentGCD != 1; ++j) {
currentGCD = gcd(currentGCD, nums[j]);
if (currentGCD == 1) {
minLength = (j - i + 1) < minLength ? (j - i + 1) : minLength;
}
}
}
return minLength == numsSize ? -1 : minLength - 1 + numsSize;
}
int main() {
int nums[] = {2, 6, 3, 4};
printf("%d\n", minOperations(nums, 4));
}using System;
public class Solution {
public 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 totalGCD = nums[0];
int n = nums.Length;
for (int i = 1; i < n; i++) {
totalGCD = Gcd(totalGCD, nums[i]);
}
if (totalGCD > 1) return -1;
int minLength = n;
for (int i = 0; i < n; i++) {
int currentGCD = nums[i];
for (int j = i; j < n && currentGCD != 1; j++) {
currentGCD = Gcd(currentGCD, nums[j]);
if (currentGCD == 1) {
minLength = Math.Min(minLength, j - i + 1);
}
}
}
return minLength == n ? -1 : minLength - 1 + n;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.MinOperations(new int[] {2, 6, 3, 4}));
}
}This Python solution implements an enhanced sweep through the array. An early check for total GCD stops unproductive arrays, whereas targeted GCD tests improve overall efficiency for viable arrays.
The performance is O(n^2) in worst-case scenarios where every subarray must be evaluated. Space complexity remains O(1).
Approach 3: Math
We first count the number of 1s in the array nums as cnt. If cnt \gt 0, then we only need n - cnt operations to turn the entire array into 1s.
Otherwise, we need to first turn one element in the array into 1, and then the minimum number of remaining operations is n - 1.
Consider how to turn one element in the array into 1 while minimizing the number of operations. In fact, we only need to find a minimum contiguous subarray interval nums[i,..j] such that the greatest common divisor of all elements in the subarray is 1, with the subarray length being mi = min(mi, j - i + 1). Finally, our total number of operations is n - 1 + mi - 1.
The time complexity is O(n times (n + log M)) and the space complexity is O(log M), where n and M are the length of the array nums and the maximum value in the array nums, respectively.
function minOperations(nums: number[]): number {
const n = nums.length;
let cnt = 0;
for (const x of nums) {
if (x === 1) {
++cnt;
}
}
if (cnt > 0) {
return n - cnt;
}
let mi = n + 1;
for (let i = 0; i < n; ++i) {
let g = 0;
for (let 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;
}
function gcd(a: number, b: number): number {
return b === 0 ? a : gcd(b, a % b);
}func minOperations(nums []int) int {
n := len(nums)
cnt := 0
for _, x := range nums {
if x == 1 {
cnt++
}
}
if cnt > 0 {
return n - cnt
}
mi := n + 1
for i := 0; i < n; i++ {
g := 0
for j := i; j < n; j++ {
g = gcd(g, nums[j])
if g == 1 {
mi = min(mi, j-i+1)
}
}
}
if mi > n {
return -1
}
return n - 1 + mi - 1
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}impl Solution {
pub fn min_operations(nums: Vec<i32>) -> i32 {
let n = nums.len() as i32;
let cnt = nums.iter().filter(|&&x| x == 1).count() as i32;
if cnt > 0 {
return n - cnt;
}
let mut mi = n + 1;
for i in 0..nums.len() {
let mut g = 0;
for j in i..nums.len() {
g = gcd(g, nums[j]);
if g == 1 {
mi = mi.min((j - i + 1) as i32);
break;
}
}
}
if mi > n {
-1
} else {
n - 1 + mi - 1
}
}
}
fn gcd(mut a: i32, mut b: i32) -> i32 {
while b != 0 {
let tmp = a % b;
a = b;
b = tmp;
}
a.abs()
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force by Iterating Over All Pairs | The time complexity is O(n^2), acknowledging the examination of every subarray. Space complexity remains O(1) due to simple variable use for GCD calculations. |
| Optimized Scan from Left | The performance is O(n^2) in worst-case scenarios where every subarray must be evaluated. Space complexity remains O(1). |
| Math | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force by Iterating Over All Pairs | O(n² log A) | O(1) | When first exploring the problem and validating how GCD propagation works across subarrays. |
| Optimized Scan from Left | O(n² log A) | O(1) | General case. Finds the shortest subarray with GCD = 1 and minimizes operations. |
Frequently asked questions
Is Minimum Number of Operations to Make All Array Elements Equal to 1 easy or hard?
The problem is rated Medium because it requires recognizing a number theory insight rather than just simulating operations. The difficulty lies in realizing that generating a single 1 through GCD operations enables converting the entire array efficiently.
Minimum Number of Operations to Make All Array Elements Equal to 1 Python/Java solution
Most implementations follow the same structure: count existing ones first, then scan all subarrays while maintaining a running GCD. Python uses math.gcd, while Java typically uses a custom gcd method. Both implementations run in O(n² log A) time with O(1) extra space.
How to solve Minimum Number of Operations to Make All Array Elements Equal to 1 in O(n)?
A strict O(n) solution generally isn't possible because multiple GCD computations across subarrays are required. The practical optimized solution scans subarrays and updates the running GCD, resulting in O(n² log A) complexity while using constant extra space.
What is the best approach for Minimum Number of Operations to Make All Array Elements Equal to 1?
The best approach scans the array to find the shortest subarray whose GCD becomes 1. Once a single 1 is produced, it can be propagated across the entire array using adjacent operations. This method runs in O(n² log A) time due to repeated GCD calculations and uses O(1) extra space.
Is Minimum Number of Operations to Make All Array Elements Equal to 1 asked at Google/Amazon/Meta?
Problems combining GCD operations with array transformations frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require recognizing number theory properties and minimizing operations are common in medium‑difficulty interview rounds.
What data structure is used in Minimum Number of Operations to Make All Array Elements Equal to 1?
The problem primarily uses arrays with mathematical GCD operations. No advanced data structures are required. The key concept comes from number theory, specifically repeated GCD reduction across contiguous array segments.
What is the time complexity of Minimum Number of Operations to Make All Array Elements Equal to 1?
The typical optimal solution runs in O(n² log A) time, where n is the array length and A is the maximum element value. The log A factor comes from the Euclidean algorithm used to compute GCD repeatedly while expanding subarrays.