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