Given an array arr[] of size N, the task is to find the minimum number of operations required to reduce all three elements of the array to zero. Following operations are allowed:
- Reduce 2 different array elements by one.
- Reduce a single array element by one.
Example:
Input: arr[] = {1, 2, 3}, N = 3
Output: 3
Explanation : Operation 1: reduce 3 and 2 to get {1, 1, 2}
Operation 2: reduce 1 and 2 to get {1, 0, 1}
Operation 3: reduce both 1s to get {0, 0, 0}Input: arr[] = {5, 1, 2, 9, 8}, N = 5
Output: 13
Approach:
This problem can be solved using greedy approach. The idea is to reduce the 2 largest elements at a time or (if not possible) 1 at a time. As we need the largest elements in each step, we can use a max heap.
The following steps can be taken to solve this approach:
- Initiate a count variable as 0.
- Insert all the elements in a max heap.
- Reduce the two largest elements.
- Insert the reduced values again into the heap.
- Repeat above mentioned steps until all array elements become zero and increase the count at each iteration.
- Stop when all array elements are zero.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// C++ program to reduce array to zero in minimum stepsint reduceArray(int arr[], int N) { int count = 0; priority_queue<int>pq; for (int i = 0; i < N; i++) { pq.push(arr[i] * -1); } while (pq.size() > 1) { int temp1 = pq.top(); pq.pop(); int temp2 = pq.top(); pq.pop(); count++; temp1++; temp2++; if (temp1 != 0) pq.push(temp1); if (temp2 != 0) pq.push(temp2); } if (pq.size() > 0){ count -= pq.top(); pq.pop(); } return count-1; } // Driver Codeint main() { int arr[] = { 1, 2, 3 }; int N = 3; int count = reduceArray(arr, N); cout << count; return 0;}// This code is contributed by satwik4409. |
Java
// Java program to reduce array to zero in minimum stepsimport java.util.*;class GFG { public static int reduceArray(int arr[], int N) { int count = 0; PriorityQueue<Integer> pq = new PriorityQueue<>(); for (int i = 0; i < N; i++) { pq.add(arr[i] * -1); } while (pq.size() > 1) { int temp1 = pq.poll(); int temp2 = pq.poll(); count++; temp1++; temp2++; if (temp1 != 0) pq.add(temp1); if (temp2 != 0) pq.add(temp2); } if (pq.size() > 0) count -= pq.poll(); return count; } // Driver Code public static void main(String[] args) { int arr[] = { 1, 2, 3 }; int N = 3; int count = reduceArray(arr, N); System.out.println(count); }} |
Python3
# Python program to reduce array to zero in minimum stepsfrom queue import PriorityQueuedef reduceArray(arr, N): count = 0 pq = PriorityQueue() for i in range(N): pq.put(arr[i] * -1) while (pq.qsize() > 1): temp1 = pq.get() temp2 = pq.get() count += 1 temp1 += 1 temp2 += 1 if (temp1 != 0): pq.put(temp1) if (temp2 != 0): pq.put(temp2) if (pq.qsize() > 0): count -= pq.get() return count# Driver Codearr = [1, 2, 3]N = 3count = reduceArray(arr, N)print(count)# This code is contributed by hrithikgarg03188. |
C#
// C# implementation of above approachusing System;using System.Collections.Generic;class GFG { public static int reduceArray(int[] arr, int N) { int count = 0; List<int> pq = new List<int>(); for (int i = 0; i < N; i++) { pq.Add(arr[i] * -1); } while (pq.Count > 1) { int temp1 = pq[0]; pq.RemoveAt(0); int temp2 = pq[0]; pq.RemoveAt(0); count++; temp1++; temp2++; if (temp1 != 0) pq.Add(temp1); if (temp2 != 0) pq.Add(temp2); } if (pq.Count > 0) count -= pq[0]; pq.RemoveAt(0); return count-1; } // Driver Code public static void Main() { int[] arr = { 1, 2, 3 }; int N = 3; int count = reduceArray(arr, N); Console.Write(count); }}// This code is contributed by sanjoy_62. |
Javascript
<script>// Javascript Priority Queue implementationfunction PriorityQueue () { let collection = []; this.printCollection = function() { (console.log(collection)); }; this.enqueue = function(element){ if (this.isEmpty()){ collection.push(element); } else { let added = false; for (let i=0; i<collection.length; i++){ if (element[1] < collection[i][1]){ //checking priorities collection.splice(i,0,element); added = true; break; } } if (!added){ collection.push(element); } } }; this.dequeue = function() { let value = collection.shift(); return value[0]; }; this.top = function() { return collection[0]; }; this.size = function() { return collection.length; }; this.isEmpty = function() { return (collection.length === 0); };}// Javascript program to reduce array to zero in minimum stepsfunction reduceArray(arr, N) { let count = 0; let pq = new PriorityQueue(); for (let i = 0; i < N; i++) { pq.enqueue(arr[i] * -1); } while (pq.size() > 1) { let temp1 = pq.top(); pq.dequeue(); let temp2 = pq.top(); pq.dequeue(); count++; temp1++; temp2++; if (temp1 != 0) pq.enqueue(temp1); if (temp2 != 0) pq.enqueue(temp2); } if (pq.size() > 0){ count -= pq.top(); pq.dequeue(); } return count-1; } // Driver Code let arr = [ 1, 2, 3 ]; let N = 3; let count = reduceArray(arr, N); console.log(count); // This code is contributed by akashish__</script> |
Output
3
Time Complexity: O(N * logN)
Auxiliary Space: O(N)
Another Approach:
- Initialize a variable ‘operations’ to 0, which will keep track of the number of operations required to reduce the array to all zeroes.
- Use a while loop to repeatedly perform the following steps until all elements of the array become zero:
- Find the maximum element(s) of the array. To do this, initialize ‘max_val’ to negative infinity, ‘max_idx’ to -1, and ‘max_cnt’ to 0. Then, iterate over the array and for each element, check if it is greater than ‘max_val’. If it is, update ‘max_val’ to the value of that element, ‘max_idx’ to the index of that element, and ‘max_cnt’ to 1. If the element is equal to ‘max_val’, increment ‘max_cnt’ by 1. At the end of the loop, we will have the maximum value(s) of the array, their index(es), and the number of times the maximum value(s) occur in the array.
- If ‘max_val’ is equal to zero, break out of the while loop, as all elements of the array have become zero.
- If ‘max_cnt’ is greater than 1, reduce any two of the maximum elements. If ‘max_cnt’ is equal to 2, iterate over the array again and find the two elements with value ‘max_val’. Reduce one of them by 1 and reduce the other one by 1 as well. Increment ‘operations’ by 1. If ‘max_cnt’ is greater than 2, simply reduce ‘max_val’ by 2 and increment ‘operations’ by 1.
- If ‘max_cnt’ is equal to 1, reduce the maximum element with the second maximum element. To do this, initialize ‘second_max_val’ to negative infinity and ‘second_max_idx’ to -1. Then, iterate over the array again and for each element, check if it is greater than ‘second_max_val’ and not equal to ‘max_val’. If it is, update ‘second_max_val’ to the value of that element and ‘second_max_idx’ to the index of that element. At the end of the loop, we will have the second maximum value of the array and its index. Reduce ‘max_val’ by 1 and reduce ‘second_max_val’ by 1. Increment ‘operations’ by 1.
- Once the while loop has completed, return the value of ‘operations’.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;int reduceArray(int arr[], int N){ int operations = 0; while (true) { // Find the maximum element(s) int max_val = INT_MIN, max_idx = -1, max_cnt = 0; for (int i = 0; i < N; i++) { if (arr[i] > max_val) { max_val = arr[i]; max_idx = i; max_cnt = 1; } else if (arr[i] == max_val) { max_cnt++; } } if (max_val == 0) { // All elements become zero break; } if (max_cnt > 1) { // Reduce any two of the maximum elements if (max_cnt == 2) { for (int i = 0; i < N; i++) { if (arr[i] == max_val && i != max_idx) { arr[i]--; arr[max_idx]--; operations++; break; } } } else { arr[max_idx] -= 2; operations++; } } else { // Reduce the maximum element with the second // maximum element int second_max_val = INT_MIN, second_max_idx = -1; for (int i = 0; i < N; i++) { if (arr[i] > second_max_val && i != max_idx) { second_max_val = arr[i]; second_max_idx = i; } } arr[max_idx]--; arr[second_max_idx]--; operations++; } } return operations;} // Driver Codeint main(){ int arr[] = { 1, 2, 3 }; int N = 3; int count = reduceArray(arr, N); cout << count; return 0;} |
Java
import java.util.Arrays;public class Main { // Function to reduce the array static int reduceArray(int[] arr, int N) { int operations = 0; while (true) { // Find the maximum element(s) int max_val = Integer.MIN_VALUE, max_idx = -1, max_cnt = 0; for (int i = 0; i < N; i++) { if (arr[i] > max_val) { max_val = arr[i]; max_idx = i; max_cnt = 1; } else if (arr[i] == max_val) { max_cnt++; } } if (max_val == 0) { // All elements become zero break; } if (max_cnt > 1) { // Reduce any two of the maximum elements if (max_cnt == 2) { for (int i = 0; i < N; i++) { if (arr[i] == max_val && i != max_idx) { arr[i]--; arr[max_idx]--; operations++; break; } } } else { arr[max_idx] -= 2; operations++; } } else { // Reduce the maximum element with the second maximum element int second_max_val = Integer.MIN_VALUE, second_max_idx = -1; for (int i = 0; i < N; i++) { if (arr[i] > second_max_val && i != max_idx) { second_max_val = arr[i]; second_max_idx = i; } } arr[max_idx]--; arr[second_max_idx]--; operations++; } } return operations; } // Driver Code public static void main(String[] args) { int[] arr = { 1, 2, 3 }; int N = 3; int count = reduceArray(arr, N); System.out.println(count); }} |
Python3
def reduceArray(arr, N): operations = 0 while True: # Find the maximum element(s) max_val = float('-inf') max_idx = -1 max_cnt = 0 for i in range(N): if arr[i] > max_val: max_val = arr[i] max_idx = i max_cnt = 1 elif arr[i] == max_val: max_cnt += 1 if max_val == 0: # All elements become zero break if max_cnt > 1: # Reduce any two of the maximum elements if max_cnt == 2: for i in range(N): if arr[i] == max_val and i != max_idx: arr[i] -= 1 arr[max_idx] -= 1 operations += 1 break else: arr[max_idx] -= 2 operations += 1 else: # Reduce the maximum element with the second maximum element second_max_val = float('-inf') second_max_idx = -1 for i in range(N): if arr[i] > second_max_val and i != max_idx: second_max_val = arr[i] second_max_idx = i arr[max_idx] -= 1 arr[second_max_idx] -= 1 operations += 1 return operations# Driver Codearr = [1, 2, 3]N = 3count = reduceArray(arr, N)print(count) |
C#
using System;class Program { static int ReduceArray(int[] arr, int N) { int operations = 0; while (true) { int max_val = int.MinValue, max_idx = -1, max_cnt = 0; for (int i = 0; i < N; i++) { if (arr[i] > max_val) { max_val = arr[i]; max_idx = i; max_cnt = 1; } else if (arr[i] == max_val) { max_cnt++; } } if (max_val == 0) { break; } if (max_cnt > 1) { if (max_cnt == 2) { for (int i = 0; i < N; i++) { if (arr[i] == max_val && i != max_idx) { arr[i]--; arr[max_idx]--; operations++; break; } } } else { arr[max_idx] -= 2; operations++; } } else { int second_max_val = int.MinValue, second_max_idx = -1; for (int i = 0; i < N; i++) { if (arr[i] > second_max_val && i != max_idx) { second_max_val = arr[i]; second_max_idx = i; } } arr[max_idx]--; arr[second_max_idx]--; operations++; } } return operations; } static void Main(string[] args) { int[] arr = { 1, 2, 3 }; int N = arr.Length; int count = ReduceArray(arr, N); Console.WriteLine(count); }} |
Javascript
function reduceArray(arr, N){ let operations = 0; while (true) { // Find the maximum element(s) let max_val = -Infinity, max_idx = -1, max_cnt = 0; for (let i = 0; i < N; i++) { if (arr[i] > max_val) { max_val = arr[i]; max_idx = i; max_cnt = 1; } else if (arr[i] === max_val) { max_cnt++; } } if (max_val === 0) { // All elements become zero break; } if (max_cnt > 1) { // Reduce any two of the maximum elements if (max_cnt === 2) { for (let i = 0; i < N; i++) { if (arr[i] === max_val && i !== max_idx) { arr[i]--; arr[max_idx]--; operations++; break; } } } else { arr[max_idx] -= 2; operations++; } } else { // Reduce the maximum element with the second // maximum element let second_max_val = -Infinity, second_max_idx = -1; for (let i = 0; i < N; i++) { if (arr[i] > second_max_val && i !== max_idx) { second_max_val = arr[i]; second_max_idx = i; } } arr[max_idx]--; arr[second_max_idx]--; operations++; } } return operations;}// Driver Codelet arr = [1, 2, 3];let N = 3;let count = reduceArray(arr, N);console.log(count); |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
