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

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 i such that 0 <= i < n - 1 and replace either of nums[i] or nums[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

1
2
3
4
5
6
7


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

1
2
3


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^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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


#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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


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.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – GCD Window Search#

Intuition#

Approach#

Code#

Complexity#