Minimize The Sum from a Given Array of Integers

Introduction

In this article, we’ll write a program to minimize the sum after performing K operations from an array. This coding problem is one of the TCS Codevita's previous year's questions. 

Now let us understand the problem statement clearly.

Problem Statement

Perform at most K operations on an array of integers so that the final array's sum of elements is the minimum. The following is how an operation is defined.

• 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 final task is to minimize the sum after utmost K operations.

Constraints

1 <= N, K <= 10^5

Input

The first line will contain two numbers, N and K, which denote the array's size and the maximum number of operations it can perform, respectively.

Output

Print an integer denoting the minimum sum of the final array.

Now let us understand the statement with the help of an example.

Example 

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.

Solution

Java Solution

import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {
        // Your code  here!
        Scanner sc= new Scanner(System.in);
        // System.out.println("XXXXXXXX")
        int n,k,i,s=0; 
        n=sc.nextInt();
        k=sc.nextInt();
        int a[]= new int [n];
        
        for(i=0;i<n;i++) a[i]=sc.nextInt();
        while(k-- > 0)
        {
            int mx=0,p=0;
            for(i=0;i<n;i++){
            if(a[i]>mx) {
                mx=a[i];
                p=i;
            }
            }
            a[p]=a[p]/2;
        }
        for(i=0;i<n;i++) s+=a[i];
        System.out.println(s);
    }
}

Output

4 3
20 7 5 4
17

C++ Solution

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long int n,k,temp_ele,sum=0;
    cin>>n;
    cin>>k;
    vector<int> v;
    for(int i=0;i<n;i++)
    {
         cin>>temp_ele;
         sum=sum + temp_ele;
         v.push_back(temp_ele);
    }
    make_heap(v.begin(),v.end());
    long int maxi = 0,res = 0;
    for(int i=0;i<k;i++)
    {
        maxi=v.front();
        sum-=maxi;
        pop_heap(v.begin(), v.end());
        v.pop_back();
        res = maxi / 2;
        sum+=res;
        v.push_back(res);
        push_heap(v.begin(),v.end());
    }
    cout<<sum;
}

You can also try this code with Online C++ Compiler

Run Code

Output

4 3
20 42 15 4
39

You can also try this code with Online C++ Compiler

Run Code