imashutosh51

Removing Minimum Number of Magic Beans

Jun 14th, 2023 (edited)
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.19 KB | None | 0 0
  1. '''
  2. If we choose to make x bags empty,we should choose the x bags with the least amount
  3. of beans.so better to sort the array.
  4. so we need to find the a number which will be the count of beans in all the bags which are non-empty.
  5. But It is must that the count of beans for all the bags will be must be the count from one of the bag before emptying,because we can't add any beans so we will keep emptying the bags from smaller bags to bigger bags and mainintaing the answer variable.
  6. '''
  7. class Solution:
  8.     def minimumRemoval(self, arr: List[int]) -> int:
  9.         arr.sort()
  10.         print(arr)
  11.         ans=inf
  12.         total=sum(arr)
  13.         cur=0
  14.         for i in range(len(arr)):
  15.             #if current i is gonna be the count of all non-empty bags
  16.             beans_remaining_after_i= (len(arr)-i)*arr[i]
  17.             if i==3:
  18.                 print(total,beans_remaining_after_i,cur,ans)
  19.             ans=min(ans,cur + (total-cur-beans_remaining_after_i)) #first cur is which are the bags before ith index and already reduced to 0 and second part after + is all the beans remaining from ith position till the end of the array
  20.             cur+=arr[i]
  21.             print(i,ans)
  22.         return ans
  23.    
  24.  
Advertisement
Add Comment
Please, Sign In to add comment