Minimum operations for reducing Array to 0 by subtracting smaller element from a pair repeatedly

0 0 5 minutes read

Given an array arr[] of size N, the task is to find the minimum number of operations required to make all array elements zero. In one operation, select a pair of elements and subtract the smaller element from both elements in the array.

Example:

Input: arr[] = {1, 2, 3, 4}
Output: 3
Explanation: Pick the elements in the following sequence:
Operation 1: Pick elements at indices {3, 2}: arr[]={1, 2, 0, 1}
Operation 2: Pick elements at indices {1, 3}: arr[]={1, 1, 0, 0}
Operation 3: Pick elements at indices {2, 1}: arr[]={0, 0, 0, 0}

Input: arr[] = {2, 2, 2, 2}
Output: 2

Approach: This problem can be solved using a priority queue. To solve the below problem, follow the below steps:

Traverse the array and push all the elements which are greater than 0, in the priority queue.
Create a variable op, to store the number of operations, and initialise it with 0.
Now, iterate over the priority queue pq till its size is greater than one in each iteration:
- Increment the value of variable op.
- Then select the top two elements, let’s say p and q to apply the given operation.
- After applying the operation, one element will definitely become 0. Push the other one back into the priority queue if it is greater than zero.
Repeat the above operation until the priority queue becomes empty.
Print op, as the answer to this question.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum number
// of operations required to make all
// array elements zero
int setElementstoZero(int arr[], int N)
{
 
    // Create a priority queue
    priority_queue<int> pq;
 
    // Variable to store the number
    // of operations
    int op = 0;
 
    for (int i = 0; i < N; i++) {
        if (arr[i] > 0) {
            pq.push(arr[i]);
        }
    }
 
    // Iterate over the priority queue
    // till size is greater than 1
    while (pq.size() > 1) {
        // Increment op by 1
        op += 1;
 
        auto p = pq.top();
        pq.pop();
        auto q = pq.top();
        pq.pop();
 
        // If the element is still greater
        // than zero again push it again in pq
        if (p - q > 0) {
            pq.push(p);
        }
    }
 
    // Return op as the answer
    return op;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << setElementstoZero(arr, N);
 
    return 0;
}

Java

// Java code for the above approach
import java.util.*;
class CustomComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer number1, Integer number2)
    {
        int value = number1.compareTo(number2);
       
        // elements are sorted in reverse order
        if (value > 0) {
            return -1;
        }
        else if (value < 0) {
            return 1;
        }
        else {
            return 0;
        }
    }
}
class GFG 
{
   
    // Function to find the minimum number
    // of operations required to make all
    // array elements zero
    static int setElementstoZero(int arr[], int N)
    {
       
        // Create a priority queue
        PriorityQueue<Integer> pq
            = new PriorityQueue<Integer>(
                new CustomComparator());
       
        // Variable to store the number
        // of operations
        int op = 0;
        for (int i = 0; i < N; i++) {
            if (arr[i] > 0) {
                pq.add(arr[i]);
            }
        }
        // Iterate over the priority queue
        // till size is greater than 1
        while (pq.size() > 1) 
        {
           
            // Increment op by 1
            op = op + 1;
            Integer p = pq.poll();
            Integer q = pq.poll();
           
            // If the element is still greater
            // than zero again push it again in pq
            if (p - q > 0) {
                pq.add(p);
            }
        }
       
        // Return op as the answer
        return op;
    }
   
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 3, 4 };
        int N = arr.length;
        System.out.println(setElementstoZero(arr, N));
    }
}
 
// This code is contributed by Potta Lokesh

Python3

# Python program for the above approach
 
# Function to find the minimum number
# of operations required to make all
# array elements zero
def setElementstoZero(arr, N):
 
    # Create a priority queue
    pq = []
 
    # Variable to store the number
    # of operations
    op = 0
 
    for i in range(N):
        if (arr[i] > 0):
            pq.append(arr[i])
 
    pq.sort()
 
    # Iterate over the priority queue
    # till size is greater than 1
    while (len(pq) > 1):
        # Increment op by 1
        op += 1
 
        p = pq[len(pq) - 1]
        pq.pop()
        q = pq[len(pq)-1]
        pq.pop()
 
        # If the element is still greater
        # than zero again push it again in pq
        if (p - q > 0):
            pq.append(p)
        pq.sort()
 
    # Return op as the answer
    return op
 
 
# Driver Code
arr = [1, 2, 3, 4]
N = len(arr)
print(setElementstoZero(arr, N))
 
# This code is contributed by Saurabh Jaiswal

C#

// C# code for the above approach
using System;
using System.Collections.Generic;
 
public class GFG {
 
  // Function to find the minimum number
  // of operations required to make all
  // array elements zero
  static int setElementstoZero(int[] arr, int N)
  {
 
    // Create a priority queue
    List<int> pq = new List<int>();
 
    // Variable to store the number
    // of operations
    int op = 0;
    for (int i = 0; i < N; i++) {
      if (arr[i] > 0) {
        pq.Add(arr[i]);
      }
    }
     
    // Iterate over the priority queue
    // till size is greater than 1
    while (pq.Count > 1) {
      pq.Sort();
      pq.Reverse();
       
      // Increment op by 1
      op = op + 1;
      int p = pq[0];
 
      int q = pq[1];
      pq.RemoveRange(0, 2);
 
      // If the element is still greater
      // than zero again push it again in pq
      if (p - q > 0) {
        pq.Add(p);
      }
    }
 
    // Return op as the answer
    return op;
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int[] arr = { 1, 2, 3, 4 };
    int N = arr.Length;
    Console.WriteLine(setElementstoZero(arr, N));
  }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to find the minimum number
// of operations required to make all
// array elements zero
function setElementstoZero(arr, N)
{
 
    // Create a priority queue
    var pq = [];
 
    // Variable to store the number
    // of operations
    var op = 0;
 
    for(var i = 0; i < N; i++) {
        if (arr[i] > 0) {
            pq.push(arr[i]);
        }
    }
 
    pq.sort((a,b) => a-b);
 
    // Iterate over the priority queue
    // till size is greater than 1
    while (pq.length > 1) {
        // Increment op by 1
        op += 1;
         
        var p = pq[pq.length-1];
        pq.pop();
        var q = pq[pq.length-1];
        pq.pop();
 
        // If the element is still greater
        // than zero again push it again in pq
        if (p - q > 0) {
            pq.push(p);
        }
        pq.sort((a,b) => a-b);
    }
 
    // Return op as the answer
    return op;
}
 
// Driver Code
var arr = [ 1, 2, 3, 4 ];
var N = arr.length;
document.write(setElementstoZero(arr, N));
 
// This code is contributed by rutvik_56.
</script>

Output

Time Complexity: O(NlogN)
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!