Find the Balanced Prefix Boundary
National Olympiad — Regional round (2014 season)
Submission name: barray.cpp
Problem summary
Find the 1-based index i whose prefix sum through i equals the sum strictly after i. Print −1 if no such boundary exists.
Input
N followed by N positive integers.
Output
The balancing index, or −1.
Constraints
2 ≤ N ≤ 100000; each value is at most 10^11.
Worked example
Input and output for the worked example discussed below.
Input
6 1 5 6 7 9 10
Output
4
Solution analysis
- Let total be the sum of the entire array and prefix the sum through the candidate index. The right-hand sum is total−prefix, so balance is equivalent to 2×prefix=total.
- Read and retain the values while computing total, then scan left to right adding each value to prefix. At the first equality print its 1-based position. Positive values make prefix strictly increasing, so at most one equality exists.
- The example has total 38. Prefix sums are 1,6,12,19,28,38. At index 4, prefix=19 and the remaining 9+10=19, so the answer is 4. The balancing element belongs to the left side.
Why it works
The computed prefix includes exactly positions 1…i, and subtracting it from total leaves exactly positions i+1…N. Therefore the equality test holds exactly at valid boundaries. The scan tests every possible i, so returning −1 only after the scan is complete is correct.
Watch out. The boundary element is included on the left and excluded on the right. Use long long for values and sums; int cannot hold the stated values.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n;
cin>>n;
vector<long long>values(n);
long long total=0;
for(long long&value:values){
cin>>value;
total+=value;
}
long long prefix=0;
for(int i=0;i<n;i++){
prefix+=values[i];
// The current element is part of the left-hand prefix.
if(prefix==total-prefix){
cout<<i+1<<'\n';
return 0;
}
}
cout<<-1<<'\n';
}