Type Here to Get Search Results !

# Minimize The Sum | TCS CodeVita 9 Solution ( Zone 1 ) 2020 | By CodingHumans |

6

Minimize The Sum

Problem Description

Given an array of integers, perform atmost K operations so that the sum of elements of final array is minimum. An operation is defined as follows -

Consider any 1 element from the array, arr[i].

Replace arr[i] by floor(arr[i]/2).

Perform next operations on updated array.

The task is to minimize the sum after atmost K operations.

Constraints

1 <= N, K <= 10^5.

Input

First line contains two integers N and K representing size of array and maximum numbers of operations that can be performed on the array respectively.

Second line contains N space separated integers denoting the elements of the array, arr.

Output

Print a single integer denoting the minimum sum of the final array.

Time Limit

1

Examples
Example 1

Input

4 3

20 7 5 4

Output

17

Explanation

Operation 1 -> Select 20. Replace it by 10.

New array = [10, 7, 5, 4]

Operation 2 -> Select 10. Replace it by 5.

New array = [5, 7, 5, 4].

Operation 3 -> Select 7. Replace it by 3.

New array = [5,3,5,4].

Sum = 17.

Recommended: Please try your approach on your integrated development environment (IDE) first, before moving on to the solution.

Few words from CodingHumans : Don't Just copy paste the solution, try to analyze the problem and solve it without looking by taking the the solution as a hint or a reference . Your understanding of the solution matters.

HAPPY CODING 😁

Solution
( C++ )

If you have any doubts regarding this problem or  need the solution in other programming languages then leave a comment down below .

1. python solution please i think so list comprehension and sorted function of python and use floor on the last element only..

1. 2. You will be notified , Do follow the site itself and follow site by Email.

2. hii this is really a good platform to know all the ansers.But can you post the answers in python

3. 4. Thanks a lot...team codinghumans!! I really want to say you are doing something really awesome, keep up the good work👍♥️.