Question

Given n elements find out a way to get minimum sum. If it is given that we have two integers n(size of array) and k(no of operations) We have to do k operations where in each operation we choose an element, remove the element from the array, divide it by 2, and insert the floor of the divided number back into the array.

Find the complete question here.


Solution by Sahithi Siripuram


Algorithm

To get the minimum sum from the entire process every time we do an operation we choose the maximum element available in the array

If we insert the elements into a priority queue we can obtain the maximum element from the priority queue by using the top function.

Solution

#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false); \
  cin.tie(NULL); cout.tie(NULL);
#define ull unsigned long long


int main()
{
  FIO;
  ull n,k,x,y,s=0; cin>>n>>k; 
  //taking the input of number of elements in an array(n)
  //and number of operations(k)
  priority_queue<int> p;
  for(ull i=0;i<n;i++)  
    //pushing the elements into the priority queue
  {
    cin>>x;
    p.push(x);
  }
  while(k--)  //run the loop till all the operations are executed 
  {
    //find the maximum element (i.e the top element in the priority queue)
    //divide it by 2 and do the floor of the element
    x=floor(p.top()/2);      
    p.pop();   //remove the element from the priority queue
    p.push(x);  //push the new element into the priority queue again
  }
  //calculate the sum of all the elements in the priority queue
  while(!p.empty())  
  {
    s+=p.top();
    p.pop();
  }
  cout<<s; // print the sum
  return 0;
}