(Analysis by Jesse Choe, Benjamin Qi)

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;
				if (curSum == targetSum) {
					 * Start a new range
					curSum = 0;
			if (ok) {
				cout << n - r << endl;

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