FastPrep
Problem · Array

🐾 Cross the Threshold

Learn this problem
● MediumSnowflake logoSnowflakeINTERNOA
See Snowflake hiring insights

Problem statement

There are n particles with initial energies given by initialEnergy. For an integer barrier, the final energy of particle i is max(initialEnergy[i] - barrier, 0).

Find the maximum non-negative integer value of barrier such that the sum of all final energies is at least the threshold th.

Complete getMaxBarrier with the following parameters:

  • int initialEnergy[n]: the initial energies of the particles
  • long th: the required energy threshold

Returns: int, the maximum barrier whose remaining total energy is at least th.

Function

getMaxBarrier(initialEnergy: int[], th: long) → int

Examples

Example 1

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

With barrier = 3, the final energies are [1, 5, 4, 0, 0] and sum to 10. With barrier = 4, they sum to 7, which is below th = 9. Therefore, the maximum feasible barrier is 3.

Example 2

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

At barrier = 7, the remaining energies are [0, 0, 6, 3] and sum to 9. At barrier = 8, the sum is 7. Thus, 7 is the largest feasible barrier.

Example 3

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

At barrier = 5, the remaining energies are [0, 4, 2] and sum to 6. Increasing the barrier to 6 lowers the sum to 4, so the answer is 5.

Constraints

  • 2 ≤ n ≤ 10^5
  • 1 ≤ initialEnergy[i] ≤ 10^9
  • 1 ≤ th ≤ 10^14
  • It is guaranteed that sum(initialEnergy) ≥ th, so a non-negative barrier always exists.

More Snowflake problems

drafts saved locally
public int getMaxBarrier(int[] initialEnergy, long th) {
    // write your code here
}
initialEnergy[4, 8, 7, 2, 1]
th9
expected3
checking account