**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++ )

#### Recommended Codevita Problems

Count Pairs | TCS CodeVita 9 Solution ( Zone 1 ) 2020

Lift | TCS CodeVita 9 Solution ( Zone 1 ) 2020

Number Distancing | TCS CodeVita 9 Solution ( Zone 1 ) 2020

Critical Planets | TCS CodeVita 9 Solution ( Zone 1 ) 2020

Prime Time Again | TCS CodeVita 9 Solution ( Zone 1 ) 2020

Minimum Gifts | TCS CodeVita 9 Solution ( Zone 1 ) 2020

Railway Station | TCS CodeVita 9 Solution ( Zone 1 ) 2020

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

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

ReplyDeletenotify me please

DeleteDear Aditya

DeleteYou will be notified , Do follow the site itself and follow site by Email.

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

ReplyDeletein java

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

ReplyDelete