Loading...
Loading...
Loading...
A college robotics team logs the change in battery charge after each test run. A change can be negative, zero or positive. The team wants to know how many different sets of four changes, taken from four different runs, add up exactly to a target T. Two sets are the same if they have the same four values, in any order.
Example 1
Input
6 0 1 0 -1 0 -2 2
Output
3
The sets are (−2, −1, 1, 2), (−2, 0, 0, 2) and (−1, 0, 0, 1).
Example 2
Input
5 8 2 2 2 2 2
Output
1
Many choices of runs give 2 + 2 + 2 + 2, but it is one set.
Try the problem first. Open one hint at a time.
Sort the values. Fix the first value with one loop and the second with a loop inside it.
For the last two values, use one index just after the second value and one at the end, moving them toward each other by comparing the total with T.
To count each set once, skip a first or second value equal to the one used just before it at the same level, and after a match skip repeated values at the left index.
Four values of 10^9 add up to 4 × 10^9, so keep the total in a long.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor