Key Observation: After any modification, the quantity $\text{sum}(a)=a_1+a_2+\cdots+a_N$ stays the same.

Solution: Rather than figuring out the minimum number of operations to make the array equal, let's figure out the maximum number of elements $r$ that could remain in the array after all modifications. Then the minimum number of modifications will equal $N-r$.

For a certain $r$ to be achievable, $\frac{\text{sum}(a)}{r}$ must be an integer and it must be possible to partition the array into $r$ ranges such that each range sums to exactly $\frac{\text{sum}(a)}{r}$. For example, in the first test case of the sample input, we can partition the array into $r=3$ ranges each with sum $\frac{\text{sum}(a)}{r}=3$:

[1 2] [3] [1 1 1]

For a single $r$, checking whether this is possible can be done in $O(N)$ time by iterating over the elements of $a$ from left to right. For each element, we can either choose to extend the current range or start a new one; see the code for details.

Time Complexity: $O(N\cdot (\#\text{ divisors of }\text{sum}(a)))$

This allows us to solve the problem under the time constraints because the sum of the array is at most $10^6$, and the maximum number of divisors for any number $\leq 10^6$ is $240$.

Jesse’s code:

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	int sum_a = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		sum_a += a[i];
	}
	for (int r = n; r >= 1; r--) {
		if (sum_a % r == 0) {
			int targetSum = sum_a / r; // the desired sum for each range
			int curSum = 0;			   // the sum of the current range
			bool ok = true;
			for (int i = 0; i < n; i++) {
				curSum += a[i];
				if (curSum > targetSum) {
					/*
					 * Can't split the array into
					 * r equal elements.
					 */
					ok = false;
					break;
				}
				if (curSum == targetSum) {
					/*
					 * Start a new range
					 */
					curSum = 0;
				}
			}
			if (ok) {
				cout << n - r << endl;
				return;
			}
		}
	}
}

int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		solve();
	}
}