Award Budget Cuts

Sergei Golitsyn provides solutions to popular algo problems.

Aloha guys today we have a Pramp.com problem Award Budget Cuts:

Description

Given an array grantsArray of the original grants and the reduced budget newBudget, write a function findGrantsCap that finds in the most efficient manner a cap such that the least number of recipients is impacted and that the new budget constraint is met (i.e. sum of the N reallocated grants equals to newBudget).

Analyze the time and space complexities of your solution.

Example:

input:  
grantsArray = [2, 100, 50, 120, 1000], 
newBudget = 190
output: 47 
And given this cap the new grants array would be
[2, 47, 47, 47, 47]. 
Notice that the sum of the new grants is indeed 190

Solution

This problem was mind-blowing for me. First, let's concentrate on the example and figure out what is happening.
We have an array of old budgets and want to distribute new ones. In the best-case scenario, we want to distribute it evenly. For example, if arr = [10, 10, 10] and newBudg = 3, the correct result should be 3. We will put 1 to all grants.
Let's add more examples. arr = [10, 3, 4, 200] and newBudg = 8, result = 2. Do you see a pattern? arr = [10, 1, 2, 20] and newBudg = 7, result = 2. You can ask me why result 2 is correct in the last example. It happens because we can fill grand with budget 1, then we have the rest of the budget as 6. And we can evenly distribute it to 3 other grands.
Hmm, so we have a pattern of how to solve this problem.

• First of all, let's sort out the grants array.
• Then we can add variable cap = newBudg / grants.length.
• After it, we should iterate over the collection and check the cap and current element.
• If the current element is lower than the cap, we can subtract it from the budget and recalculate the cap again with a lower length.
• We want to do it till we find the first grand > cap. After it, it doesn't make sense. Our algorithm ready for implementation. Let's deep dive to the code implementation

Code

static double findGrantsCap(double[] arr, double newBudget) {
   // your code goes here
   Arrays.sort(arr); // O(N*LogN)
   int n = arr.length-1;
   double cap = newBudget/n+1;
   for(int i = 0; i < n; i++) { // O(N)
     if(arr[i] < cap) {
        newBudget -= arr[i];
        cap = (newBudget/(n-i));
     } else {
       return cap;
     }
   }
   return cap;
}