Last Updated: 2 Dec, 2020
Day 27 : Magician and Chocolates
Easy
Asked in company
In a magic event, you are given ‘N’ bags, each bag containing ‘A[i]’ chocolates. In one unit of time, you can choose any bag ‘i’ and eat all the chocolates ‘A[i]’ in that bag and then the magician fills the ith bag with floor(‘A[i]’ / 2) chocolates. Your task is to find the maximum number of chocolate you can eat in ‘K’ units of time.
Since the answer could be large, return answer modulo 10^9 + 7.
For Example:
For the array [ 4, 7, 9, 10] and ‘k’=2
In the first step, we can choose the last bag. So the answer will be 10 and the array will be [4, 7, 9, 5].
In the second step, we can choose the second last bag. So the answer will be 19 and the array will be [4, 7, 4, 5].
So the final output will be 19.
Input Format:
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.
The first line of each test case contains two space-separated integers ‘N’ and ‘K’, representing the number of bags and the amount of time.
The second line of each test case contains ‘N’ space-separated integers representing the number of chocolates in each bag.
Output Format:
For each test case, print an integer representing the maximum number of chocolates you can eat in the given amount of time.
Output for each test case will be printed in a separate line.
Note
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 100
1 <= N <= 10^5
1 <= ARR[i] <= 10^5
It is guaranteed that the sum of ‘N’ over all test cases doesn’t exceed 10^5.
Time Limit: 1 sec.
Approaches
Since we have a limited amount of time and we have to maximize the number of chocolates we will try to take the maximum number of chocolates possible at each unit of time.
Algorithm:
- We will declare a variable of value 1000000007 to take the modulus of the answer as stated in the question.
- Then we will implement a while loop to iterate over ‘K’.
- Now we will iterate over the array and will find the maximum element in the array, add it to the ‘ANS’, and reduce the element to its half.
- Finally, we will return ‘ANS’.
We will use a priority queue to find the largest element in the array at each step. It will significantly reduce the time complexity from ‘N’ to ‘log(N)’. At each step, we will take the largest element from the priority queue, add it to the answer and push the half of maximum element back to the priority queue.
Algorithm:
- We will declare a variable of value 1000000007 to take the modulus of the answer as stated in the question.
- Then we will declare a priority queue of integers and push every element of the array to it.
- Then we will implement a while loop to iterate over ‘K’.
- At each step, we will take out the top element ‘cur’ of the priority queue, then delete it from the priority queue. After that, we will add ‘cur’ to the answer and push ‘cur’ / 2 to the priority queue.
- Finally, we will return the answer.