FastPrep
Problem · Array

🐾 Cross the Threshold

● MediumSnowflakeINTERNOA
See Snowflake hiring insights

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. 1. int initialEnergy[n]: the initial energies of the particles
  2. 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

Examples
01 · Example 1
initialEnergy = [4, 8, 7, 2, 1]
th = 9
return = 3
Example 1 illustration
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.
02 · Example 2
initialEnergy = [5, 2, 13, 10]
th = 8
return = 7
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
03 · Example 3
initialEnergy = [3, 9, 7]
th = 6
return = 5
Example 3 illustration
Constraints

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.

More Snowflake problems
drafts saved locally
public int getMaxBarrier(int[] initialEnergy, int th) {
    // write your code here (solution hint: binary search + prefixsum)
}
initialEnergy[4, 8, 7, 2, 1]
th9
expected3
sign in to submit