A sorting line moves pallets past a row of fixed scanning gates, one gate per position, in a fixed left-to-right order. Each gate records the weight of the pallet passing beneath it. For a chosen quadruple of gate positions w < x < y < z (listed in strictly increasing order along the line), the line is considered balanced at that quadruple if the recorded weight at position w, plus the weight at position x, plus the weight at position y, equals exactly the weight recorded at position z.
Given the sequence of recorded pallet weights along the line, count how many strictly increasing quadruples of positions (w, x, y, z) are balanced in this sense.
Line 1: an integer n, the number of recorded weights.
Line 2: n integers, the weights weight[0], weight[1], ..., weight[n-1], in order along the line.
Print a single integer: the number of quadruples of indices 0 <= w < x < y < z < n such that weight[w] + weight[x] + weight[y] == weight[z].
Example 1
Input
4 1 2 3 6
Expected
1
Explanation
There is only one possible quadruple of increasing positions with n=4: (0,1,2,3). Checking it: weight[0]+weight[1]+weight[2] = 1+2+3 = 6, which equals weight[3] = 6. So it is balanced, and the answer is 1.
Example 2
Input
5 1 1 1 2 4
Expected
3
Explanation
The weights are [1,1,1,2,4]. Checking all valid quadruples (w,x,y,z): with z=3 (weight 2), the only choice of w<x<y<3 is (0,1,2), giving sum 1+1+1=3, which is not 2, so no match. With z=4 (weight 4), the choices of three indices from {0,1,2,3} are (0,1,2) summing to 3 (no match), (0,1,3) summing to 1+1+2=4 (match), (0,2,3) summing to 1+1+2=4 (match), and (1,2,3) summing to 1+1+2=4 (match). That gives 3 balanced quadruples: (0,1,3,4), (0,2,3,4), and (1,2,3,4). The answer is 3.
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 →