Equator

Equator

Codeforces easy

Given array \(A\) of \(N\) integers \(A_1, A_2, \dots, A_N\). Find the first index \(i\) such that the sum \(A_1 + A_2 ... + A_i\) is at least half the sum of the whole array.

Note

Array \(A\) is 1-indexed (i.e, the indexing starts from \(1\)).

Tip

When comparing two integers, if one of them involves division, you can avoid division by multiplying the other side instead.

For example, instead of writing:

if (running_sum >= total_sum / 2)

you can safely write:

if (running_sum * 2 >= total_sum)

This avoids rounding issues and works correctly with integers.

Solution

Loop over the array and get the sum of the whole array let’s call it total_sum.

int n;
cin >> n;

int a[n];
int total_sum = 0;

for (int i = 0; i < n; i++) {
    cin >> a[i];
    total_sum += a[i];
}

Then, start another loop from the first element, keeping a running_sum. As you add each element, check if running_sum has reached half total_sum. The first index where this happens is the answer.

int running_sum = 0;
int ans;

for (int i = 0; i < n; i++) {
    running_sum += a[i];

    if (running_sum * 2 >= total_sum) {
        ans = i + 1;
        break;
    }
}

cout << ans;