binary search award budget cuts

On pramp, this question is called "Award Budget Cuts". The wording of the question is a little complex, but basically says that there are N companies receiving grants each year, e.g:

G = [10, 50, 100, 120, 200]

However there have been budget cuts, and thus the new budget requires some grants to be capped.

B = 190

Write a function that finds a cap such that the least number of recipients is impacted and such that the new budget constraint is met (i.e sum of the N reallocated grants equals to B).

Solution

This problem can easily be solved with a binary search but is more interesting than a regular binary search, since the solution space involves a trial and error process of capping values, rather than searching for a value in a sorted list.

Capping grant values

We want to cap the grants, and sum the capped grants, to figure whether we are still over or under the total funding amount.

Since we are familiar with lambdas and generators, we can easily do this in a one-liner:

1G = [10, 50, 100, 120, 200] # total: 480
2comp_total = lambda c: sum(min(c, g) for g in G)
3print(comp_total(50)) # 210

In the code above, we cap the grants to a maximum value of 50. As a result the total of the grants allocated is now 210. We now have a mechanism for testing out various caps, to decide whether the cap is too low or too high. Since 210 > 190, a cap of 50 is still too high.

In the animation above, you can see the grants getting capped by binary search, and gravitating towards the optimal cap amount of 47.

Computing the cap

The cap is the value we are searching for, or optimising. Its maximum value (the right pointer in our binary search) is the entire budget. Its minimum value (the left pointer in our binary search) is 0.

The search, as any binary search, consists of guessing the value by taking the average of the min and max. The key difference is we then attempt to validate this guess by computing whether it leads us to being over, or under the given budget.

 1def find_grants_cap(G, b):
 2  comp_total = lambda c: sum(min(c, g) for g in G)
 3  l, r = 0, b
 4  while l < r:
 5    m = (l + r) / 2
 6    total = comp_total(m)
 7    if abs(total - b) < 0.0001:
 8      return m
 9    else:
10      l, r = ((m, r),(l, m))[total > b]

Below, we can view these values being optimised simultaneously.

This algorithm is very interesting and fun to watch, as it details very clearly how binary search can be used for numerical optimisation as opposed to simply searching for a value in a sorted array.

Time and Space Complexity

$$time = O(n \times log(n))$$ $$space = O(1)$$