First Balance Index with a Small Memory Budget
National Olympiad — Regional round (2025 season)
Submission name: balance.cpp
Problem summary
Find the smallest interior index whose preceding and following values have equal sums, or 0 if none exists.
Input
n followed by n signed values.
Output
The smallest 1-based balance index, or 0.
Constraints
2<n<1000000; −1000≤a[i]≤1000; original memory limit 5 MB.
Worked example
Input and output for the worked example discussed below.
Input
6 1 5 9 1 2 3
Output
3
Solution analysis
- Store the input while computing its total. Individual values fit signed short, so a million entries use about 2 MB without separate prefix and suffix arrays.
- Scan interior positions with leftSum. The right sum equals total−leftSum−a[i]. Return the first equality; otherwise add the current value before continuing.
- Position 3 of [1,5,9,1,2,3] has both side sums equal to 6. For five zeros the answer is 2 because endpoints are excluded and the earliest interior match wins.
Why it works
Before testing each index, leftSum is its exact preceding sum. Subtracting it and the current value leaves precisely the following sum. The equality test therefore matches the definition, and scan order finds the earliest index.
Watch out. Exclude endpoints, retain signed values, and avoid large extra prefix/suffix arrays.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<short>values(n);
int total=0;
for(short&value:values){
cin>>value;
total+=value;
}
int leftSum=values[0];
for(int index=1;index+1<n;index++){
// Remove the left prefix and current value to obtain the right suffix.
if(leftSum==total-leftSum-values[index]){
cout<<index+1<<'\n';
return 0;
}
leftSum+=values[index];
}
cout<<0<<'\n';
}