A reserve fund stores its distinct positive deposit amounts in a binary search tree. Starting from an empty tree, the amounts are inserted one at a time in the order given (standard BST insertion: go left when the new amount is smaller than the current node, otherwise go right). Process the stored amounts in ascending order, keeping a running total. Report the smallest amount x at which the running total (of every stored amount <= x) first reaches or exceeds a threshold T.
Line 1: an integer n, the number of deposits.
Line 2: n space-separated distinct positive integers, the deposits in insertion order.
Line 3: an integer T.
A single integer: the smallest deposit x at which the ascending running total first becomes >= T. If the total of all deposits is still < T, print NONE.
Example 1
Input
5 30 10 40 20 50 55
Expected
30
Explanation
Ascending deposits are 10, 20, 30, 40, 50. Running totals: 10, 30, 60. The total first reaches 55 at deposit 30 (total 60), so the answer is 30.
Example 2
Input
4 5 2 8 6 100
Expected
NONE
Explanation
The deposits total 2 + 5 + 6 + 8 = 21, which never reaches 100, so the answer is NONE.
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 →