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

---

Timeline

Timeline

2025-11-12

init

GCD math

---

Problem:

P2654 make all array elements become 1 the 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 and turn them into 1, so our goal is to find a 1 or a subarray that can become 1.

1. Case 1: The array already has a 1.
2. Case 2: There is no 1. We need to find the shortest subarray such that the gcd of all its numbers is 1, and denote its length as len. As long as we can create a 1 in that segment through operations, then spreading it to the whole array requires n - 1 operations. So 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: The array already has a 1.
		if (cnt1 > 0) {
			return n - cnt1;
		}

		// Case 2: There is 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, then spreading it to the whole array requires 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 make all elements 1.
	}
};