Minimize the sum problem | Code Vita 2020 | Code Vita 9

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.

Solution in C:

#include <stdio.h>

void insertionSort(int arr[], int n) {

    int i, key, j;

    for (i = 1; i < n; i++) {

        key = arr[i];

        j = i - 1;

        /* Move elements of arr[0..i-1] that are greater than key to one position ahead of their current position */

        while (j >= 0 && arr[j] < key) {

            arr[j + 1] = arr[j];

            j = j - 1;

        }

        arr[j + 1] = key;

    }

}

int minimizeSum(int N, int K, int arr[]) {

    int i;

    // Sort the array in descending order

    insertionSort(arr, N);

    for (i = 0; i < K; i++) {

        // Perform the operation on the maximum element

        arr[0] = arr[0] / 2;

        // Re-sort the array

        insertionSort(arr, N);

    }

    int sum = 0;

    for (i = 0; i < N; i++) {

        sum += arr[i];

    }

    return sum;

}

int main() {

    int N, K;

    scanf("%d %d", &N, &K);

    int arr[N];

    for (int i = 0; i < N; i++) {

        scanf("%d", &arr[i]);

    }

    int result = minimizeSum(N, K, arr);

    printf("%d\n", result);

    return 0;

}

You can also run it on an online IDE: 

https://ide.geeksforgeeks.org/online-c-compiler/3e917f44-b16f-4cca-9fd4-6ac81a2254f3

Your feedback are always welcome! If you have any doubt you can contact me or leave a comment!  Happy Coding !! Cheers!!!

Related Links:

https://codepiggy.blogspot.com/2024/01/restaurants-code-vita-8-round-2.html