LeetCode 2654. Minimum Number of Operations to Make All Array Elements Equal to 1 Solution in Java, C++, Python & More | Explanation + Code

Description

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.

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 <= 50
• 1 <= nums[i] <= 106

Solutions

Solution 1: 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 × (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.

PythonJavaC++GoTypeScriptRust

class Solution: def minOperations(self, nums: List[int]) -> int: n = len(nums) cnt = nums.count(1) if cnt: return n - cnt mi = n + 1 for i in range(n): g = 0 for j in range(i, n): g = gcd(g, nums[j]) if g == 1: mi = min(mi, j - i + 1) return -1 if mi > n else n - 1 + mi - 1(code-box)

class Solution { public int minOperations(int[] nums) { int n = nums.length; int cnt = 0; for (int x : nums) { if (x == 1) { ++cnt; } } if (cnt > 0) { return n - cnt; } int mi = n + 1; for (int i = 0; i < n; ++i) { int g = 0; for (int 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; } private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } }(code-box)

class Solution { public: int minOperations(vector<int>& nums) { int n = nums.size(); int cnt = 0; for (int x : nums) { if (x == 1) { ++cnt; } } if (cnt) { return n - cnt; } int mi = n + 1; for (int i = 0; i < n; ++i) { int g = 0; for (int j = i; j < n; ++j) { g = gcd(g, nums[j]); if (g == 1) { mi = min(mi, j - i + 1); } } } return mi > n ? -1 : n - 1 + mi - 1; } };(code-box)

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) }(code-box)

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); }(code-box)

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() }(code-box)