# How To Reduce the Array to 0 by decreasing elements by 1 or replacing at most K elements by 0

#### Cyber Security : Go from Zero to Hero

Most Popular

60 Lectures 5.5 hours

#### Master C and Embedded C Programming- Learn as you go

Best Seller

66 Lectures 5.5 hours

#### C Programming from scratch- Master C Programming

Best Seller

60 Lectures 8 hours

Given an array arr[ ] of N integers and a positive integer K, the task is to find the minimum number of operations required to reduce all array elements to 0 such that in each operation reduce any array element by 1 and independently at most K array element can be reduced to 0. Examples:

Input: arr[ ] = {4, 1, 5}, K = 1
Output: 5
Explanation: Following are the operations performed to convert all array elements to 0:
Here K = 1, So replace arr[2] by 0, converts arr[v] to {4, 1, 0} –> Number of operations = 0.
Decrease arr[1] by 1, converts arr[] to {4, 0, 0} –>  Number of operations = 1.
Decrease arr[0] by 1 four times, converts arr[b] to {0, 0, 0} –>  Number of operations = 4.
Therefore, total number of operations = 0 + 1 + 4 = 5, which is minimum possible.

Input: arr[ ] = {4, 2, 10, 9, 18}, K = 2
Output: 15 
Approach: The given problem can be solved by using the Greedy Approach which is based on the idea is that first sort the given array arr[ ] in non-decreasing order and then update the K largest element to 0 and perform the given operation on the remaining array elements. Follow the steps below to solve the given problem: If the value of N is at most K, then replace all array elements with 0. Therefore the number of operations required in this case will be 0. Sort the array arr[ ] in non-decreasing order. Replace last K elements by 0. Print the sum of the first (N – K) elements as the resultant count of operations. Below is the implementation of the above approach:

# Python3 program for the above approach

# Function to find the minimum number
# operations needed to convert all the
# array elements to 0

def minOperations(arr, K, N) :

# If K is greater then 0 then

# replace all array elements to 0

if (K >= N) :

return 0;

# Sort array in non-decreasing order

arr.sort();

# Stores the count of operations

# required

countOperations = 0;

# Iterate loop until N - K times

for i in range(N - K) :

# Take sum of elements

countOperations += arr[i];

# Return countOperations as

return countOperations;

# Driver Code

if __name__ == "__main__" :

arr = [ 4, 1, 5 ];

N = len(arr);

K = 1;

print(minOperations(arr, K, N));
Output:

5
Time Complexity: O(N*log N) Auxiliary Space: O(1)