Equal Sum

Easy

0/40

Average time to solve is 15m

Contributed by

35 upvotes

Asked in companies

Problem statement

After a long lockdown, Alex and Rome want to meet. There are ‘N’ checkpoints in between their homes numbered from 0 to N - 1, where checkpoint 0 is closest to Alex and checkpoint N - 1 is closest to Rome. Each checkpoint has a token with a number written on it. If someone crosses some checkpoint, he will collect the token. Alex and Rome will meet at some checkpoint ‘i’, 0 <= i <= N - 1. They aim to have the same total sum of numbers on the tokens they have collected individually when they meet at the checkpoint ‘i’. They don’t want any fights, so no one will take the token at checkpoint ‘i’.

You are given an array ‘token’ consisting of ‘N’ integers, signifying the number on each token. Find out the checkpoint number ‘i’ such that Alex and Rome will have the same sum of numbers on their tokens. Since Alex is lazy, find out the index closest to Alex such that the above conditions hold. Also, notify if no such checkpoints exist.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains ‘T’, the number of test cases.

The first line of each test case contains an integer ‘N’, the number of checkpoints.

The second line of each test case contains an array ‘token’ of ‘N’ space-separated integers, signifying the number on each token.

Output Format:

For each test case, print an integer denoting the checkpoint number i, 0 <= i <= N - 1. In case no such checkpoint exists, print ‘-1’.

Note:

You are not required to print the expected output. It has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
1 <= N <= 10^5
-10^4 <= token[i] <= 10^4

Where token[i] is the token number at checkpoint i, 0 <= i <= N - 1.

Time Limit: 1 sec

Sample Input 1:

Sample Output 1:

2
2

Explanation for Sample Input 1:

In the first test case, the token numbers are [1, 4, 9, 3, 2]. If they meet at index 2, Alex will have token 0 and token 1, with the sum = 1 + 4 = 5. Rome will have token 3 and token 5, with the sum = 3 + 2 = 5. Hence, the sums are equal and the answer is 2.

In the second test case, the token numbers are [1, -2, 5, -1]. If they meet at index 2, Alex will have a sum of 1 + (-2) = -1, and Rome will have a sum of -1. Hence, the answer is 2.

Sample Input 2:

Sample Output 2:

-1
2

Hint 1

Hint 2

For each index, can we calculate the sums of Alex and Rome?

Approaches (2)

Approach 1

Approach 2

Brute Force

Here, we will traverse through the array. And for each index, find out the sum for Alex and Rome.

The steps are as follow:

We will traverse the array from i = 0 to i = N - 1.
- For each index i, using separate loops, calculate the sum of tokens from index 0 to index i - 1, for Alex. Calculate the sum of tokens from index i + 1 to index N - 1, for Rome.
  - If both the sums are equal we will return the index as the answer.
If no suitable index is found, return ‘-1’.

Time Complexity

O(N^2), where ‘N’ is the number of checkpoints.

We are traversing the array. And for each index, we are calculating the sum for Alex and Rome. Thus, for each index, we are traversing the array again. Hence the overall complexity is O(N^2).

Space Complexity

O(1)

We do not require any extra space. So, the overall complexity is O(1).

(100% EXP penalty)

Equal Sum

Console