Problem Description:
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:
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
