Given an array arr[] consisting of N distinct elements, the task is to find the maximum number of pairs required to be decreased by 1 in each step, such that N – 1 array elements are reduced to 0 and the remaining array element is a non-negative integer.
Examples:
Input: arr[] = {1, 2, 3}
Output: 3
Explanation:
Decrease arr[1] and arr[2] by 1 modifies arr[] = {1, 1, 2}
Decrease arr[1] and arr[2] by 1 modifies arr[] = {1, 0, 1}
Decrease arr[0] and arr[2] by 1 modifies arr[] = {0, 0, 0}
Therefore, the maximum number of decrements required is 3.
Input: arr[] = {1, 2, 3, 4, 5}
Output: 7
Approach: The problem can be solved Greedily. Follow the steps below to solve the problem:
- Initialize a variable, say cntOp, to store maximum count of steps required to make (N – 1) elements of the array equal to 0.
- Create a priority queue, say PQ, to store the array elements.
- Traverse the array and insert the array elements into PQ.
- Now repeatedly extract the top 2 elements from the priority queue, decrease the value of both the elements by 1, again insert both the elements in priority queue and increment the cntOp by 1. This process continues while (N – 1) element of the PQ becomes equal to 0.
- Finally, print the value of cntOp
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to count maximum number of steps// to make (N - 1) array elements to 0int cntMaxOperationToMakeN_1_0(int arr[], int N){ // Stores maximum count of steps to make // (N - 1) elements equal to 0 int cntOp = 0; // Stores array elements priority_queue<int> PQ; // Traverse the array for (int i = 0; i < N; i++) { // Insert arr[i] into PQ PQ.push(arr[i]); } // Extract top 2 elements from the array // while (N - 1) array elements become 0 while (PQ.size() > 1) { // Stores top element // of PQ int X = PQ.top(); // Pop the top element // of PQ. PQ.pop(); // Stores top element // of PQ int Y = PQ.top(); // Pop the top element // of PQ. PQ.pop(); // Update X X--; // Update Y Y--; // If X is not equal to 0 if (X != 0) { // Insert X into PQ PQ.push(X); } // if Y is not equal // to 0 if (Y != 0) { // Insert Y // into PQ PQ.push(Y); } // Update cntOp cntOp += 1; } return cntOp;}// Driver Codeint main(){ int arr[] = { 1, 2, 3, 4, 5 }; int N = sizeof(arr) / sizeof(arr[0]); cout << cntMaxOperationToMakeN_1_0(arr, N); return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{ // Function to count maximum number of steps// to make (N - 1) array elements to 0static int cntMaxOperationToMakeN_1_0(int[] arr, int N){ // Stores maximum count of steps to make // (N - 1) elements equal to 0 int cntOp = 0; // Stores array elements PriorityQueue<Integer> PQ = new PriorityQueue<Integer>((a, b) -> b - a); // Traverse the array for(int i = 0; i < N; i++) { // Insert arr[i] into PQ PQ.add(arr[i]); } // Extract top 2 elements from the array // while (N - 1) array elements become 0 while (PQ.size() > 1) { // Stores top element // of PQ int X = PQ.peek(); // Pop the top element // of PQ. PQ.remove(); // Stores top element // of PQ int Y = PQ.peek(); // Pop the top element // of PQ. PQ.remove(); // Update X X--; // Update Y Y--; // If X is not equal to 0 if (X != 0) { // Insert X into PQ PQ.add(X); } // if Y is not equal // to 0 if (Y != 0) { // Insert Y // into PQ PQ.add(Y); } // Update cntOp cntOp += 1; } return cntOp;}// Driver codepublic static void main(String[] args){ int[] arr = { 1, 2, 3, 4, 5 }; int N = arr.length; System.out.print(cntMaxOperationToMakeN_1_0(arr, N));}}// This code is contributed by susmitakundugoaldanga |
Python3
# Python3 program to implement# the above approach# Function to count maximum number of steps# to make (N - 1) array elements to 0def cntMaxOperationToMakeN_1_0(arr, N): # Stores maximum count of steps to make # (N - 1) elements equal to 0 cntOp = 0 # Stores array elements PQ = [] # Traverse the array for i in range(N): # Insert arr[i] into PQ PQ.append(arr[i]) PQ = sorted(PQ) # Extract top 2 elements from the array # while (N - 1) array elements become 0 while (len(PQ) > 1): # Stores top element # of PQ X = PQ[-1] # Pop the top element # of PQ. del PQ[-1] # Stores top element # of PQ Y = PQ[-1] # Pop the top element # of PQ. del PQ[-1] # Update X X -= 1 # Update Y Y -= 1 # If X is not equal to 0 if (X != 0): # Insert X into PQ PQ.append(X) # if Y is not equal # to 0 if (Y != 0): # Insert Y # into PQ PQ.append(Y) # Update cntOp cntOp += 1 PQ = sorted(PQ) return cntOp# Driver Codeif __name__ == '__main__': arr = [1, 2, 3, 4, 5] N = len(arr) print (cntMaxOperationToMakeN_1_0(arr, N)) # This code is contributed by mohit kumar 29. |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG { // Function to count maximum number of steps // to make (N - 1) array elements to 0 static int cntMaxOperationToMakeN_1_0(int[] arr, int N) { // Stores maximum count of steps to make // (N - 1) elements equal to 0 int cntOp = 0; // Stores array elements List<int> PQ = new List<int>(); // Traverse the array for (int i = 0; i < N; i++) { // Insert arr[i] into PQ PQ.Add(arr[i]); } PQ.Sort(); PQ.Reverse(); // Extract top 2 elements from the array // while (N - 1) array elements become 0 while (PQ.Count > 1) { // Stores top element // of PQ int X = PQ[0]; // Pop the top element // of PQ. PQ.RemoveAt(0); // Stores top element // of PQ int Y = PQ[0]; // Pop the top element // of PQ. PQ.RemoveAt(0); // Update X X--; // Update Y Y--; // If X is not equal to 0 if (X != 0) { // Insert X into PQ PQ.Add(X); PQ.Sort(); PQ.Reverse(); } // if Y is not equal // to 0 if (Y != 0) { // Insert Y // into PQ PQ.Add(Y); PQ.Sort(); PQ.Reverse(); } // Update cntOp cntOp += 1; } return cntOp; } // Driver code static void Main() { int[] arr = { 1, 2, 3, 4, 5 }; int N = arr.Length; Console.WriteLine(cntMaxOperationToMakeN_1_0(arr, N)); }}// This code is contributed by divyesh072019 |
Javascript
<script> // Javascript program to implement the above approach // Function to count maximum number of steps // to make (N - 1) array elements to 0 function cntMaxOperationToMakeN_1_0(arr, N) { // Stores maximum count of steps to make // (N - 1) elements equal to 0 let cntOp = 0; // Stores array elements let PQ = []; // Traverse the array for (let i = 0; i < N; i++) { // Insert arr[i] into PQ PQ.push(arr[i]); } PQ.sort(function(a, b){return a - b}); PQ.reverse(); // Extract top 2 elements from the array // while (N - 1) array elements become 0 while (PQ.length > 1) { // Stores top element // of PQ let X = PQ[0]; // Pop the top element // of PQ. PQ.shift(); // Stores top element // of PQ let Y = PQ[0]; // Pop the top element // of PQ. PQ.shift(); // Update X X--; // Update Y Y--; // If X is not equal to 0 if (X != 0) { // Insert X into PQ PQ.push(X); PQ.sort(function(a, b){return a - b}); PQ.reverse(); } // if Y is not equal // to 0 if (Y != 0) { // Insert Y // into PQ PQ.push(Y); PQ.sort(function(a, b){return a - b}); PQ.reverse(); } // Update cntOp cntOp += 1; } return cntOp; } let arr = [ 1, 2, 3, 4, 5 ]; let N = arr.length; document.write(cntMaxOperationToMakeN_1_0(arr, N)); // This code is contributed by mukesh07.</script> |
Output
7
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)
Approach: Using the Two Pointers approach
Algorithm steps:
- Sort the array arr in descending order using std::sort and the greater<int> comparator.
Initialize two pointers, left and right, where left starts at index 0 and right starts at index N – 2 (since we need to make (N – 1) elements equal to 0). - Initialize a variable cntOp to keep track of the count of steps.
- Iterate until the left and right pointers meet or cross each other.
- In each iteration:
- Subtract 1 from both elements pointed to by the left and right pointers.
- If either element becomes non-positive:
- Move the left pointer to the right (increment it) if the left element becomes non-positive.
- Move the right pointer to the left (decrement it) if the right element becomes non-positive.
- Increment the count of steps cntOp by 1.
- After the iteration is complete, return the value of cntOp, which represents the maximum number of steps required to make (N – 1) elements equal to 0.
Below is the implementation of the above approach:
C++
//C++ code for the above approach#include <iostream>#include <algorithm>using namespace std;// Function to count maximum number of steps// to make (N - 1) array elements equal to 0int cntMaxOperationToMakeN_1_0(int arr[], int N){ // Sort the array in descending order sort(arr, arr + N, greater<int>()); // Initialize two pointers int left = 0; int right = N - 2; // (N - 1) elements to make 0 // Count the number of steps int cntOp = 0; // Perform steps until left and right pointers meet while (left <= right) { // Subtract 1 from both elements arr[left]--; arr[right]--; // If either element becomes non-positive, // move the pointer accordingly if (arr[left] <= 0) left++; if (arr[right] <= 0) right--; // Increment the count of steps cntOp++; } return cntOp;}// Driver Codeint main(){ int arr[] = {1, 2, 3,4,5}; int N = sizeof(arr) / sizeof(arr[0]); cout << cntMaxOperationToMakeN_1_0(arr, N); return 0;} |
Java
import java.util.Arrays;import java.util.Collections;public class Main { // Function to count maximum number of steps // to make (N - 1) array elements equal to 0 static int cntMaxOperationToMakeN_1_0(int arr[], int N) { // Sort the array in descending order Arrays.sort(arr); reverseArray(arr); // Initialize two pointers int left = 0; int right = N - 2; // (N - 1) elements to make 0 // Count the number of steps int cntOp = 0; // Perform steps until left and right pointers meet while (left <= right) { // Subtract 1 from both elements arr[left]--; arr[right]--; // If either element becomes non-positive, // move the pointer accordingly if (arr[left] <= 0) left++; if (arr[right] <= 0) right--; // Increment the count of steps cntOp++; } return cntOp; } // Function to reverse the array static void reverseArray(int arr[]) { int left = 0; int right = arr.length - 1; while (left < right) { int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; right--; } } // Driver Code public static void main(String[] args) { int arr[] = {1, 2, 3, 4, 5}; int N = arr.length; System.out.println(cntMaxOperationToMakeN_1_0(arr, N)); }} |
Python3
def cntMaxOperationToMakeN_1_0(arr, N): # Sort the array in descending order arr.sort(reverse=True) # Initialize two pointers left = 0 right = N - 2 # (N - 1) elements to make 0 # Count the number of steps cntOp = 0 # Perform steps until left and right pointers meet while left <= right: # Subtract 1 from both elements arr[left] -= 1 arr[right] -= 1 # If either element becomes non-positive, # move the pointer accordingly if arr[left] <= 0: left += 1 if arr[right] <= 0: right -= 1 # Increment the count of steps cntOp += 1 return cntOp# Driver Codearr = [1, 2, 3, 4, 5]N = len(arr)print(cntMaxOperationToMakeN_1_0(arr, N)) |
C#
using System;using System.Linq;namespace MaxOperationsToMakeZero{ class Program { static int CountMaxOperationToMakeN_1_0(int[] arr, int N) { // Sort the array in descending order Array.Sort(arr, (x, y) => y.CompareTo(x)); // Initialize two pointers int left = 0; int right = N - 2; // (N - 1) elements to make 0 // Count the number of steps int cntOp = 0; // Perform steps until left and right pointers meet while (left <= right) { // Subtract 1 from both elements arr[left]--; arr[right]--; // If either element becomes non-positive, // move the pointer accordingly if (arr[left] <= 0) left++; if (arr[right] <= 0) right--; // Increment the count of steps cntOp++; } return cntOp; } static void Main(string[] args) { int[] arr = { 1, 2, 3, 4, 5 }; int N = arr.Length; Console.WriteLine(CountMaxOperationToMakeN_1_0(arr, N)); } }} |
Javascript
// Function to count maximum number of steps// to make (N - 1) array elements equal to 0function cntMaxOperationToMakeN_1_0(arr, N) { // Sort the array in descending order arr.sort((a, b) => b - a); // Initialize two pointers let left = 0; let right = N - 2; // (N - 1) elements to make 0 // Count the number of steps let cntOp = 0; // Perform steps until left and right pointers meet while (left <= right) { // Subtract 1 from both elements arr[left]--; arr[right]--; // If either element becomes non-positive, // move the pointer accordingly if (arr[left] <= 0) left++; if (arr[right] <= 0) right--; // Increment the count of steps cntOp++; } return cntOp;}// Driver Codeconst arr = [1, 2, 3, 4, 5];const N = arr.length;console.log(cntMaxOperationToMakeN_1_0(arr, N)); |
Output
7
Time Complexity: O(N log N) , because of the sorting operation.
Auxiliary Space: O(1) because the algorithm only uses a constant amount of additional space for the pointers and variables.
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!
