Minimize the sum problem (TCS Codevita)

Minimize the sum 

Minimize the sum Problem is one of the question that was asked in previous year TCS Codevita competition. It is simple minimize sum problem where we have to find minimum sum by performing  atmost k operations in an array. This is an article on Minimize the sum problem where we have to minimize the sum by performing at most k operations in an array.

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 the updated array.
  • The task is to minimize the sum after utmost 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.

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.


import java.util.*;

class Solution
{
public static void main (String[]args)
{
Scanner sc = new Scanner (System.in);
int n = sc.nextInt ();
int k = sc.nextInt ();

PriorityQueue < Integer > maxHeap =new PriorityQueue <> ((one, two)->two - one);

for (int i = 0; i < n; i++)
maxHeap.add (sc.nextInt ());

while (k > 0 && maxHeap.size () > 0)
{
int max = maxHeap.poll ();
maxHeap.add (max / 2);
k = k - 1;
}
int sum = 0;

while (maxHeap.size () > 0)
sum = sum + maxHeap.poll ();
System.out.println (sum);
}
}