Loading...
Loading...
Loading...
Two friends share a long restaurant bill. The items are listed in order, and some lines are discounts (negative amounts). They want to cut the list into a first part and a second part, each with at least one item, so that both parts add up to the same amount.
Print the smallest number of items in the first part that works, or NO SPLIT.
NO SPLIT.Example 1
Input
5 120 80 50 100 50
Output
2
120 + 80 = 200 and 50 + 100 + 50 = 200.
Example 2
Input
3 10 20 15
Output
NO SPLIT
The first parts sum to 10 or 30; the rest to 35 or 15.
Try the problem first. Open one hint at a time.
First find the total of all amounts.
Walk from the left keeping the sum of the first part. The second part is then total - left, with no second loop.
Stop at n - 1 items, so the second part is never empty. Use long for the sums.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor