Maximum number of pair reductions possible on a given triplet
Given a triplet of integers (A, B, C), the task is to count the maximum number of decrements by 1 that can be performed on positive pairs of the given triplet.
Examples:
Input: A = 4, B = 3, C = 2
Output: 4
Explanation:
Operation 1: Reduce the pair (4, 3). Therefore, the triplet reduces to {3, 2, 2}.
Operation 2: Reduce the pair (3, 2). Therefore, the triplet reduces to {2, 1, 2}.
Operation 3: Reduce the pair (2, 2). Therefore, the triplet reduces to {1, 1, 1}.
Operation 3: Reduce the pair (1, 1). Therefore, the triplet reduces to {0, 0, 1}.
No further operations are possible.Input: A = 7, B = 9, C = 6
Output: 11
Approach: The idea is to use Greedy Approach to solve the problem. Follow the steps below to solve the problem:
- Store the triplet in an array.
- Initialize a variable, say count, to store the maximum possible reductions that can be performed on the triplet.
- Iterate a loop until the first two array elements are reduced to 0 and perform the following operations:
- Sort the array in increasing order.
- Pick the two maximum array elements and reduce them by 1.
- Increment count by 1.
- Print the value of count as the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count the maximum // number of pair reductions // possible on a given triplet void maxOps( int a, int b, int c) { // Convert them into an array int arr[] = { a, b, c }; // Stores count of operations int count = 0; while (1) { // Sort the array sort(arr, arr + 3); // If the first two array // elements reduce to 0 if (!arr[0] && !arr[1]) break ; // Apply the operations arr[1] -= 1; arr[2] -= 1; // Increment count count += 1; } // Print the maximum count cout << count; } // Driver Code int main() { // Given triplet int a = 4, b = 3, c = 2; maxOps(a, b, c); return 0; } // This code is contributed by subhammahato348. |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to count the maximum // number of pair reductions // possible on a given triplet static void maxOps( int a, int b, int c) { // Convert them into an array int arr[] = { a, b, c }; // Stores count of operations int count = 0 ; while ( 1 != 0 ) { // Sort the array Arrays.sort(arr); // If the first two array // elements reduce to 0 if (arr[ 0 ] == 0 && arr[ 1 ] == 0 ) break ; // Apply the operations arr[ 1 ] -= 1 ; arr[ 2 ] -= 1 ; // Increment count count += 1 ; } // Print the maximum count System.out.print(count); } // Driver Code public static void main(String[] args) { // Given triplet int a = 4 , b = 3 , c = 2 ; maxOps(a, b, c); } } // This code is contributed by code_hunt. |
Python3
# Python3 program for the above approach # Function to count the maximum # number of pair reductions # possible on a given triplet def maxOps(a, b, c): # Convert them into an array arr = [a, b, c] # Stores count of operations count = 0 while True : # Sort the array arr.sort() # If the first two array # elements reduce to 0 if not arr[ 0 ] and not arr[ 1 ]: break # Apply the operations arr[ 1 ] - = 1 arr[ 2 ] - = 1 # Increment count count + = 1 # Print the maximum count print (count) # Given triplet a, b, c = 4 , 3 , 2 maxOps(a, b, c) |
C#
// C# program for the above approach using System; class GFG { // Function to count the maximum // number of pair reductions // possible on a given triplet static void maxOps( int a, int b, int c) { // Convert them into an array int [] arr = { a, b, c }; // Stores count of operations int count = 0; while (1 != 0) { // Sort the array Array.Sort(arr); // If the first two array // elements reduce to 0 if (arr[0] == 0 && arr[1] == 0) break ; // Apply the operations arr[1] -= 1; arr[2] -= 1; // Increment count count += 1; } // Print the maximum count Console.WriteLine(count); } // Driver Code public static void Main(String[] args) { // Given triplet int a = 4, b = 3, c = 2; maxOps(a, b, c); } } // This code is contributed by susmitakundugoaldanga. |
Javascript
<script> // JavaScript program for the above approach // Function to count the maximum // number of pair reductions // possible on a given triplet function maxOps(a, b, c) { // Convert them into an array let arr = [ a, b, c ]; // Stores count of operations let count = 0; while (1) { // Sort the array arr.sort(); // If the first two array // elements reduce to 0 if (!arr[0] && !arr[1]) break ; // Apply the operations arr[1] -= 1; arr[2] -= 1; // Increment count count += 1; } // Print the maximum count document.write(count); } // Driver Code // Given triplet let a = 4, b = 3, c = 2; maxOps(a, b, c); // This code is contributed by Surbhi Tyagi. </script> |
4
Time Complexity: O(log n), where n is the maximum value among a, b, and c, as the number of pair reductions required to reduce the two largest numbers to 0 is proportional to log n.
Auxiliary Space: O(1)
METHOD: Max_ pair_ reductions
APPROACH:
This algorithm sorts the input triplet in descending order and then repeatedly subtracts the smaller of the first two values from both of them until one of them becomes zero. The number of reductions performed in each step is added to a counter. Once one of the values becomes zero, the algorithm adds the remaining value to the counter and returns it as the maximum number of pair reductions possible
ALGORITHM:
1.Create a list containing the values of A, B, and C.
2.Sort the list in decreasing order.
3.Initialize a count variable to 0.
4.While the first two elements of the list are positive, perform the following operations:
a. Find the minimum of the first two elements.
b. Subtract the minimum from both elements.
c. Increment the count variable by the minimum.
d. Sort the list in decreasing order.
5.Return the count variable plus the value of the remaining element of the list.
C++
#include <algorithm> #include <iostream> using namespace std; int max_pair_reductions( int A, int B, int C) { int triplet[] = { A, B, C }; sort(triplet, triplet + 3, greater< int >()); int count = 0; while (triplet[0] > 0 && triplet[1] > 0) { int min_val = min(triplet[0], triplet[1]); triplet[0] -= min_val; triplet[1] -= min_val; count += min_val; sort(triplet, triplet + 3, greater< int >()); } return count + triplet[2]; } int main() { int A = 4; int B = 3; int C = 2; cout << max_pair_reductions(A, B, C) << endl; // Output: 4 return 0; } |
Java
import java.util.Arrays; public class MaxPairReductions { // Function to calculate the maximum pair reductions static int maxPairReductions( int A, int B, int C) { int [] triplet = { A, B, C }; // Create an array to hold the values A, B, and C Arrays.sort(triplet); // Sort the array in ascending order int count = 0 ; // Initialize a counter for reductions // Continue reducing pairs until both A and B are greater than 0 while (triplet[ 2 ] > 0 && triplet[ 1 ] > 0 ) { int minVal = Math.min(triplet[ 2 ], triplet[ 1 ]); // Find the minimum value between triplet[2] and triplet[1] triplet[ 2 ] -= minVal; // Reduce triplet[2] by minVal triplet[ 1 ] -= minVal; // Reduce triplet[1] by minVal count += minVal; // Increment the reduction count Arrays.sort(triplet); // Sort the array again to maintain ascending order } return count + triplet[ 0 ]; // Return the total count plus the remaining value in triplet[0] } public static void main(String[] args) { int A = 4 ; int B = 3 ; int C = 2 ; System.out.println(maxPairReductions(A, B, C)); // Output: 4 } } |
Python3
def max_pair_reductions(A, B, C): triplet = [A, B, C] triplet.sort(reverse = True ) count = 0 while triplet[ 0 ] > 0 and triplet[ 1 ] > 0 : min_val = min (triplet[ 0 ], triplet[ 1 ]) triplet[ 0 ] - = min_val triplet[ 1 ] - = min_val count + = min_val triplet.sort(reverse = True ) return count + triplet[ 2 ] A = 4 B = 3 C = 2 print (max_pair_reductions(A, B, C)) # 4 |
C#
using System; using System.Linq; class Program { // Function to find the maximum number of reductions in a triplet static int MaxPairReductions( int A, int B, int C) { // Create an array to store the triplet values int [] triplet = { A, B, C }; // Sort the triplet in descending order Array.Sort(triplet, (x, y) => y.CompareTo(x)); // Initialize a variable to count the number of reductions int count = 0; // Continue reducing pairs while the two largest elements are positive while (triplet[0] > 0 && triplet[1] > 0) { // Find the minimum value between the two largest elements int minVal = Math.Min(triplet[0], triplet[1]); // Subtract the minimum value from both elements triplet[0] -= minVal; triplet[1] -= minVal; // Increase the reduction count count += minVal; // Re-sort the triplet to maintain the descending order Array.Sort(triplet, (x, y) => y.CompareTo(x)); } // Add the remaining value to the count return count + triplet[2]; } static void Main() { // Input values int A = 4; int B = 3; int C = 2; // Call the function and print the result Console.WriteLine(MaxPairReductions(A, B, C)); // Output: 4 } } |
Javascript
function max_pair_reductions(A, B, C) { let triplet = [ A, B, C ]; triplet.sort(); triplet.reverse(); let count = 0; while (triplet[0] > 0 && triplet[1] > 0) { let min_val = Math.min(triplet[0], triplet[1]); triplet[0] -= min_val; triplet[1] -= min_val; count += min_val; triplet.sort(); triplet.reverse(); } return count + triplet[2]; } let A = 4; let B = 3; let C = 2; document.write(max_pair_reductions(A, B, C)); // Output: 4 |
4
The time complexity of this algorithm is O(log n), where n is the maximum value of A, B, and C. The space complexity is O(1), as the algorithm only uses a fixed amount of memory for the input triplet, counter, and some temporary variables.