Problem Brief

🐾 Cross the Threshold

INTERNOA

There are n particles present in a space and an array, initialEnergy[n]. The finalEnergy[i] of the i^th particle is max(initialEnergy[i] - barrier, 0).

The goal is to find the maximum possible integer value of the barrier such that the sum of final energies of the particles is greater than or equal to a given threshold th.

Function Description

Complete the function getMaxBarrier in the editor.

getMaxBarrier has the following parameter(s):

1. int initialEnergy[n]: the initial energies of the particles
2. int th: the threshold

Returns

int: the maximum integer value of the barrier such that the sum of energies of all the particles is greater than or equal to th

1Example 1

Input

initialEnergy = [4, 8, 7, 2, 1], th = 9

Output

Explanation

Test barrier values of 0 through 4. * These columns in the image above are calculated for each value in initialEnergy. Each finalEnergy[i] is max(this value, 0), so negative values are not part of the sums. The maximum value of barrier for which the sum of final energies of all particles is greater than or equal to th is 3.

2Example 2

Input

initialEnergy = [5, 2, 13, 10], th = 8

Output

Explanation

With the initial energies provided and the threshold of 8, we start testing different barrier values: barrier initialEnergy sum of to test - barrier energies final 6 -1 -4 7 4 11 7 -2 -5 6 3 9 8 -3 -6 5 2 7

3Example 3

Input

initialEnergy = [3, 9, 7], th = 6

Output

Explanation

Constraints

Limits and guarantees your solution can rely on.

2 ≤ n ≤ 10⁵

1 ≤ initialEnergy[i] ≤ 10⁹

1 ≤ th ≤ 10¹⁴

It is guaranteed that a non-negative value of barrier will exist in each case, i.e., ∑initialEnergy[i] for all i from 0 to n-1 is greater than or equal to threshold th.