Where the two sides weigh the same
Reported in interviews at (where)
You are given a list of whole numbers. A position balances the list when the numbers before it add up to the same total as the numbers after it; the number at the position itself counts on neither side, and an empty side adds up to 0.
For each list, find the first position that balances it. Positions are counted from 0.
Input
The first line holds T, the number of tests. Each test is two lines: n, then the n whole numbers of the list, separated by spaces.
Output
For each test, one line: the first position that balances its list, or -1 if none does.
- Input
3
7
1 7 3 6 5 6 0
3
1 2 3
1
-4- Output
3
-1
0
- Before position 3: 1 + 7 + 3 = 11. After it: 5 + 6 + 0 = 11.
- The sides at positions 0, 1 and 2 are 0 and 5, 1 and 3, 3 and 0.
- Both sides of the only position are empty.
Limits
1 <= T <= 2001 <= n <= 100000-10000 <= each number <= 10000the n of all the tests add up to at most 400000
Hints
Hint 1
The total of the whole list tells you the right side once you know the left side.
Hint 2
Walk once from the left, keeping the sum of what you have passed: the right side is total - left - a[i].
Where this was reported
- Aditya Birla Group, SDE interview, 2023 (Code360)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.
