https://www.pramp.com/challenge/r1Kw0vwG6OhK9AEGAyWV

Award-Budget-Cuts.py

# Time: O(N log(N))
# Space: O(1)

'''
[2, 100, 50, 120, 1000] newBudget = 190 
1000, 120, 100, 50, 2, 0
120, 120, 100, 50, 2, 0
100, 100, 100, 50, 2, 0
50, 50, 50, 50, 2, 0
2, 2, 2, 2, 2, 0

'''
def find_grants_cap(grantsArray, newBudget):
  pass # your code goes here
  # sort the array in a descending order
  grantsArray.sort(reverse = True)
  
  # pad the array with a zero at the end to 
  # cover the case where 0 <= cap <= grands 
  grantsArray.append(0)
 
  # calculate the total amount we need to 
  # cut back to meet the reduced budget 
  surplus = sum(grantsArray) - newBudget 
  
  # if there is noting to cut, simply return 
  # the highest grant as the cap. Recall that 
  # the grants array is sorted in a descending order,
  # so the highest grant is positioned at index 0
  if surplus <= 0:
    return grantsArray[0]
  
  # start substracting from surplus the 
  # differences ("deltas") between consecutive 
  # grants until surplus is less or equal to zero.
  # Basically, we are testing out, in order, each 
  # of the grants as potential lower bound for the cap.
  # Once we find the first value that brings us below zero we break
  for i in range(len(grantsArray)-1):
    surplus -= (i+1) * (grantsArray[i] - grantsArray[i+1])
    if surplus <= 0:
      break 
  
  # since grantsArray[i+1] is a lower bound 
  # to our cap, i.e. grantsArray[i+1] <= cap,
  # we need to add to grantsA
  return grantsArray[i+1] + (-surplus/float(i+1))