Award budget cuts - using greedy approach

AwardBudgetCuts_usingGreedy.cs

/
using System;

class Solution
{
    public static double FindGrantsCap(double[] grantsArray, double newBudget)
    {
      if(grantsArray == null || newBudget <= 0)
        return 0; 
      
      var length = grantsArray.Length; 
      double prefixSum = 0; 
      
      Array.Sort(grantsArray); 
      
      for(int index = 0; index < length; index++)
      {
        var current     = grantsArray[index]; 
        
        var available   = newBudget - prefixSum; 
        var numbersLeft = length - index;        
        
        if(current * numbersLeft > available)
        {
          return available/ numbersLeft;
        }
        
        prefixSum += current; 
      }
      
      return grantsArray[length - 1];
    }

    static void Main(string[] args)
    {
        var newCap = FindGrantsCap(new double[]{2, 100, 50, 120, 1000}, 190); 
        Console.WriteLine(newCap); 
    }
}

/*
Keywords:
N 
given grantsArray, 
newBudget
constraint: impact as few grant recipients as possible by applying maximum cap 
Ask: calculate cap value 
  
  [2, 100, 50, 120, 1000], 190 - new budget, cap value 47
  
  linear scan the array -> sorted array 
  sorted the array O(nlogn)
  [2, 50, 100, 120, 1000 ], 190 -> cap value  
  
  
  ___|   compared to newBudget
  
  _________|   2 + 50 * 4 = 202 > 190
  
             | 
  ______________
  
  ___________|______
  
  ___________|______________________________________
  
  */
  

easy understanding, good..

great code...

can you please provide an explanation?

can you please provide an explanation?
Problem statement see my blog:
http://juliachencoding.blogspot.com/search?q=award+budget+cut

The awards committee had planned to give n research grants this year, out of a its total yearly budget.
However, the budget was reduced to b dollars. The committee members has decided to affect the minimal number of highest grants, by applying a maximum cap c on all grants: every grant that was planned to be higher than c will now be c dollars.
Help the committee to choose the right value of c that would make the total sum of grants equal to the new budget.
Given an array of grants g and a new budget b, explain and code an efficient method to find the cap c.
Analyze the time and space complexity of your solution.

My explanation
Let me give it a try. Use example [2, 100, 50, 120, 1000], budget is 190.

So let us work on brute force solution, what is minimum value in the array to be cut?
So, the array is sorted first, sorted = new int[]{2, 50, 100, 120, 1000].
Let us go over all possible ones, index from 0 to 4.
If index = 0, cap value < 2, then maximum sum of the array is less than 2 * 5 = 10, budget is 190. We have 190 - 10 unused budget. So it is not working.
Move on to next one, index = 1, so the budget will be [2, c, c, c, c], 2 + 4 * c = 190, c = 47. The minimum number of cut is 4.
If c >= 50, then total sum minimum is 2 + 4 * 50 = 202 > 190. So it shows that second number in sorted has to be cut as the first one.

Thank you for asking. I wish that it works. I will write a blog if I come out better idea later.

Also, pramp.com questions can be looked up here:
https://github.com/jianminchen/Pramp
Budget cuts
https://github.com/jianminchen/Pramp/tree/master/Budget_Cuts