Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- '''
- If we choose to make x bags empty,we should choose the x bags with the least amount
- of beans.so better to sort the array.
- so we need to find the a number which will be the count of beans in all the bags which are non-empty.
- 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.
- '''
- class Solution:
- def minimumRemoval(self, arr: List[int]) -> int:
- arr.sort()
- print(arr)
- ans=inf
- total=sum(arr)
- cur=0
- for i in range(len(arr)):
- #if current i is gonna be the count of all non-empty bags
- beans_remaining_after_i= (len(arr)-i)*arr[i]
- if i==3:
- print(total,beans_remaining_after_i,cur,ans)
- 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
- cur+=arr[i]
- print(i,ans)
- return ans
Advertisement
Add Comment
Please, Sign In to add comment