Given an array A of boxes such that each box contains some balls in it
and ith box has A[i] number of balls. we have to pick M balls from any box such that the maximum balls of all boxes should be minimum
for example A = [1,9,3,7,5,6,4,8,2] and M = 6
than we will pick 3 balls from 2nd box, 2 balls from 8th box, and 1 ball from 4th box
and the final array will look like A = [1,6,3,6,5,6,4,6,2]
Which algorithm should I use?
1 < A[i] < 1e9
1 < M < 1e18
First of all , there is no standard algorithm to use for you problem so I will explain the way this should be solved.
The problem requires you to find modify the array so that you will obtain the minimum possible oft of the "max boxes". The key here is to find the maximum of your array and to extract a ball from it every time and, at the same time, lower the M by 1. This action should be repeated while M !=0. Using your example,the steps would look like this:
A = [1,9,3,7,5,6,4,8,2]
A = [1,8,3,7,5,6,4,8,2]
A = [1,7,3,7,5,6,4,8,2]
A = [1,7,3,7,5,6,4,7,2]
A = [1,6,3,7,5,6,4,7,2]
A = [1,6,3,6,5,6,4,7,2]
A = [1,6,3,6,5,6,4,6,2]
If you still have some questions, feel free to ask! I can also provide you with a full working algorithm but you should try to create it yourself first!