n weights are placed at equally spaced positions 1..n along a rigid beam (weight[i] at position i, 1-indexed; a weight may be negative, representing an upward lifting force). A position p (1 <= p <= n) is called a BALANCE POINT if the total torque of weights strictly to the left of p equals the total torque of weights strictly to the right of p, where the torque of a weight at position i relative to p is weight[i] * |i - p|. Formally, p is a balance point if:
sum over i < p of weight[i] * (p - i) == sum over i > p of weight[i] * (i - p)
(the weight at position p itself contributes to neither side; an empty side sums to 0). Find the SMALLEST position p that is a balance point. If no position balances, print -1.
Line 1: an integer n.
Line 2: n space-separated integers, weight[1..n].
A single integer: the smallest balance point p, or -1 if none exists.
Example 1
Input
5 1 1 1 1 1
Expected
3
Explanation
At p=1 left=0, right=1*1+1*2+1*3+1*4=10 (no match). At p=2 left=1, right=1+2+3=6 (no match). At p=3 left=1*2+1*1=3, right=1*1+1*2=3 - these match, and no smaller p worked, so the answer is 3.
Example 2
Input
3 5 -3 5
Expected
2
Explanation
At p=1 left=0, right=-3*1+5*2=7 (no match). At p=2 left=5*1=5, right=5*1=5 - these match, so the answer is 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →