- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP
- Physics
- Chemistry
- Biology
- Mathematics
- English
- Economics
- Psychology
- Environmental Science
- Social Studies
- Fashion Studies
- Legal Studies

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

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

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
# the required answer
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)

- Related Questions & Answers
- How to Find Area of Scalene Triangle using C
- Write C Program to Reversing an Array Elements in C Programming
- How to print hello world using C Language
- Recursive program to linearly search an element in a given array using C
- How to redirect HTTP to HTTPS Using htaccess
- Write a ‘C’ Program to compute the sum of all elements stored in an array using pointers
- How to convert temperature from degree centigrade to Fahrenheit using C
- How to Implement Stack Operations Using Array using C
- How to get a list of parameter names inside Python function?
- How to calculate gross salary of a person using C Program
- Write C program to find Exponent Power Series
- How can we create recursive functions in Python?
- How To Reduce the Array to 0 by decreasing elements by 1 or replacing at most K elements by 0
- How to Calculate Area of Circle using C Programming
- How To Send mail from your Gmail account using Python
- What is SQL ?

ads