LeetCode Daily Problem P2654: Minimum Number of Operations to Make All Array Elements 1

---

Timeline

timeline

2025-11-12

init

gcd mathematics

---

Problem:

P2654 Make all array elements become 1 minimum number of operations

https://leetcode.cn/problems/minimum-number-of-operations-to-make-all-array-elements-equal-to-1/description/?envType=daily-question&envId=2025-11-12

As long as there is a 1, it can spread to other non-1 numbers to become 1, so our goal is to find a 1 or a subarray that can become 1.

1. Case 1: There is already a 1 in the array
2. Case 2: No 1, we need to find the shortest subarray such that the gcd of all its numbers is 1, let its length be len. As long as we can create a 1 in that segment through operations, and then spread to the entire array requires n - 1 operations. Then the answer = len - 1 + (n - 1).

#include <vector>
#include <numeric>
#include <algorithm>
#include <climits>
using std::vector;

class Solution {
    public:
	int minOperations(vector<int> &nums)
	{
		int n = nums.size();
		int cnt1 = 0;
		for (int x : nums) {
			if (x == 1) {
				cnt1++;
			}
		}

		// Case 1: There is already a 1 in the array
		if (cnt1 > 0) {
			return n - cnt1;
		}

		// Case 2: No 1, find the shortest subarray with gcd 1
		// We need to find the length len of the shortest subarray with gcd = 1.
		// As long as we can create a 1 in that segment through operations, and then propagate it to the entire array, it takes n - 1 operations.
		// Answer = len - 1 + (n - 1).
		int ans = INT_MAX;
		int g;
		for (int i = 0; i < n; i++) {
			g = nums[i];
			for (int j = i + 1; j < n; j++) {
				g = std::gcd(g, nums[j]);
				if (g == 1) {
				        // j-i+1 is the length of the subarray with gcd 1
					ans = std::min(ans, j - i + 1);
					break;
				}
			}
		}

		if (ans == INT_MAX) {
			return -1; // It is impossible to create a 1
		}
		return (ans - 1) + (n - 1); // Create a 1, then spread it to all 1s
	}
};