Last Updated: 27 Nov, 2020
Equal Sum
Easy
Asked in companies
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.
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
Approaches
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.
- 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 no suitable index is found, return ‘-1’.
The key idea here is that tokens collected by Alex = total tokens - tokens collected by Rome - ith token. So, we can cumulatively find Alex’s sum and using the formula find Rome’s sum.
The steps are as follows:
- We will calculate ‘sum_token’ as the sum of all tokens.
- We will initialize a variable ‘token_alex’ as 0, signifying the sum of tokens from j = 0 to j = i - 1.
- We will traverse the array from i = 0 to i = N - 1.
- We will calculate Rome’s sum, token_rome as sum_token - token_alex - token[i].
- If both sums are equal, return the index as the answer.
- Add token[i] to token_alex.
- We will calculate Rome’s sum, token_rome as sum_token - token_alex - token[i].
- If no suitable index is found, return ‘-1’.
Similar problems