Day 27 : Magician and Chocolates

Easy

0/40

Average time to solve is 15m

Contributed by

34 upvotes

Asked in company

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

Sample Output 1:

8
33

Explanation For Sample Output 1:

For the first test case,
In the first step, we can choose the second bag. So the answer will be 8 and the array will be [3, 4, 2, 4].
So, the final answer will be 8.

For the second test case,
In the first step, we can choose the last bag. So the answer will be 22 and the array will be [10, 4, 7, 11].
In the second step, we can choose the last bag. So the answer will be 33 and the array will be [10, 4, 7, 5].
So, the final answer will be 33.

Sample Input 2:

2
5 3
3 6 10 12 8
4 1
2 10 4 3

Sample Output 2:

30
10

Hint 1

Hint 2

Try to get the maximum number of chocolates possible at each step.

Approaches (2)

Approach 1

Approach 2

Greedy

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’.

Time Complexity

O(K * N), where ‘K’ and ‘N’ are the given amount of time and number of bags respectively.

Since we are iterating over ‘K’ and for each value of ‘K’, we are iterating over the array to find the maximum element, the overall time complexity will be O(K * N).

Space Complexity

O(1).

Constant Space is used.

(100% EXP penalty)

Day 27 : Magician and Chocolates

Console