There are n particles present in a space and an array, initialEnergy[n]. The
finalEnergy[i] of the ith 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
Example 1:
Input: initialEnergy = [4, 8, 7, 2, 1], th = 9
Output: 3
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.
Example 2:
Input: initialEnergy = [5, 2, 13, 10], th = 8
Output: 7
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
Example 3:
Input: initialEnergy = [3, 9, 7], th = 6
Output: 5
2 ≤ n ≤ 105
1 ≤ initialEnergy[i] ≤ 109
1 ≤ th ≤ 1014
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.
input:
output: