Minimize the sum problem (TCS Codevita)

July 21, 2021

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.


List of Top 100 Codes

2 comments on “Minimize the sum problem (TCS Codevita)”


  • mevinodrao

    #include
    long int i,j,k,a,b,sum=0,arr[10000000];
    unsigned int arraymax();
    int main()
    {
    printf(“enter the size of array and no of operations to be performed \n”);
    scanf(“%ld””%ld”,&a,&b);
    printf(“enter the array values\n”);
    for(i=1;i<=a;i++)
    {
    scanf("%ld",&arr[i]);
    }
    for(j=1;j<=b;j++)
    {
    arraymax();
    arr[1]=arr[1]/2;
    }
    for(i=1;i<=a;i++)
    {
    sum=sum+arr[i];
    }
    for(i=1;i<=a;i++)
    {
    printf("%ld\t",arr[i]);
    }
    printf("\n%ld",sum);
    return 0;
    }

    unsigned int arraymax()
    {
    for (i=2;i<=a;i++)
    {
    if (arr[1] < arr[i])
    {
    x=arr[1];
    arr[1] = arr[i];
    arr[i]=x;
    }
    }
    }


  • pradeep

    c++ solution for this problem

    #include
    #include

    using namespace std;

    int main()
    {
    int t;
    cin>>t;
    while(t–)
    {
    priority_queuepq;
    int n,k;
    cin>>n>>k;
    int arr[n];
    int sum=0;
    for(int i=0;i>arr[i];
    pq.push(arr[i]);

    }
    while(k–)
    {
    int x=pq.top();
    x=x/2;
    pq.pop();
    pq.push(x);
    }
    while(!pq.empty())
    {
    int y=pq.top();
    sum+=y;
    pq.pop();
    }
    cout<<sum<<endl;
    }

    return 0;
    }