Maximize absolute difference between X and Y by at most N decrements
Given five integers X, Y, A, B, and N, the task is to find the maximum possible absolute difference between X and Y by performing the following operations exactly N times:
- Decrement the value of X by 1 up to A.
- Decrement the value of Y by 1 up to B.
Note: The value of (X – A + Y – B) must be greater than or equal to N
Examples:
Input: X = 12, Y = 8, A = 8, B = 7, N = 2
Output: 4
Explanation:
Decrementing the value of X by 1. Therefore, X = X – 1 = 11
Decrementing the value of Y by 1. Therefore, Y = Y – 1 = 7
Therefore, the maximum absolute difference between X and Y = abs(X – Y) = abs(11 – 7) = 4Input: X = 10, Y = 10, A = 8, B = 5, N = 3
Output: 3
Explanation:
Decrementing the value of Y by 1 three times. Therefore, Y = Y – 3 = 7
Therefore, the maximum absolute difference between X and Y = abs(X – Y) = abs(10 – 7) = 3
Approach: The problem can be solved using the Greedy technique. Follow the steps below to solve the problem:
- Initialize a variable, say n1 to store the maximum count of operations performed on X.
- Update n1 = min(N, X – A).
- Initialize a variable, say n2 to store the maximum count of operations performed on Y.
- Update n2 = min(N, Y – B).
- Initialize a variable say, diff_X_Y_1 to store the absolute difference of X and Y by first decrementing the value of X by 1 exactly min(N, n1) times then decrement the value of Y by the remaining times of operations.
- Initialize a variable say, diff_X_Y_2 to store the absolute difference of X and Y by first decrementing the value of Y by 1 exactly min(N, n2) times then decrement the value of X by the remaining times of operations.
- Finally, print the value of max(diff_X_Y_1, diff_X_Y_2).
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 find the absolute difference // between X and Y with given operations int AbsDiff( int X, int Y, int A, int B, int N) { // Stores maximum absolute difference // between X and Y with given operations int maxDiff = 0; // Stores maximum number of operations // performed on X int n1 = X - A; // Update X X = X - min(N, n1); // Decrementing N at most N times N = N - min(N, n1); // Stores maximum number of operations // performed on Y int n2 = Y - B; // Update Y Y = Y - min(N, n2); // Update maxDiff maxDiff = abs (X - Y); return maxDiff; } // Function to find the max absolute difference // between X and Y with given operations int maxAbsDiff( int X, int Y, int A, int B, int N) { // Stores absolute difference between // X and Y by first decrementing X and then Y int diffX_Y_1; // Stores absolute difference between X // and Y first decrementing Y and then X int diffX_Y_2; // Update diffX_Y_1 diffX_Y_1 = AbsDiff(X, Y, A, B, N); // Swap X, Y and A, B swap(X, Y); swap(A, B); // Update diffX_Y_2 diffX_Y_2 = AbsDiff(X, Y, A, B, N); return max(diffX_Y_1, diffX_Y_2); } // Driver Code int main() { int X = 10; int Y = 10; int A = 8; int B = 5; int N = 3; cout << maxAbsDiff(X, Y, A, B, N); } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to find the absolute difference // between X and Y with given operations public static int AbsDiff( int X, int Y, int A, int B, int N) { // Stores maximum absolute difference // between X and Y with given operations int maxDiff = 0 ; // Stores maximum number of operations // performed on X int n1 = X - A; // Update X X = X - Math.min(N, n1); // Decrementing N at most N times N = N - Math.min(N, n1); // Stores maximum number of operations // performed on Y int n2 = Y - B; // Update Y Y = Y - Math.min(N, n2); // Update maxDiff maxDiff = Math.abs(X - Y); return maxDiff; } // Function to find the max absolute difference // between X and Y with given operations public static int maxAbsDiff( int X, int Y, int A, int B, int N) { // Stores absolute difference between // X and Y by first decrementing X and then Y int diffX_Y_1; // Stores absolute difference between X // and Y first decrementing Y and then X int diffX_Y_2; // Update diffX_Y_1 diffX_Y_1 = AbsDiff(X, Y, A, B, N); // Swap X, Y and A, B int temp1 = X; X = Y; Y = temp1; int temp2 = A; A = B; B = temp2; // Update diffX_Y_2 diffX_Y_2 = AbsDiff(X, Y, A, B, N); return Math.max(diffX_Y_1, diffX_Y_2); } // Driver code public static void main(String[] args) { int X = 10 ; int Y = 10 ; int A = 8 ; int B = 5 ; int N = 3 ; System.out.println(maxAbsDiff(X, Y, A, B, N)); } } // This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program to implement # the above approach # Function to find the absolute difference # between X and Y with given operations def AbsDiff(X, Y, A, B, N): # Stores maximum absolute difference # between X and Y with given operations maxDiff = 0 # Stores maximum number of operations # performed on X n1 = X - A # Update X X = X - min (N, n1) # Decrementing N at most N times N = N - min (N, n1) # Stores maximum number of operations # performed on Y n2 = Y - B # Update Y Y = Y - min (N, n2) # Update maxDiff maxDiff = abs (X - Y) return maxDiff # Function to find the max absolute difference # between X and Y with given operations def maxAbsDiff(X, Y, A, B, N): # Stores absolute difference between # X and Y by first decrementing X and then Y diffX_Y_1 = AbsDiff(X, Y, A, B, N) # Swap X, Y and A, B temp1 = X X = Y Y = temp1 temp2 = A A = B B = temp2 # Stores absolute difference between X # and Y first decrementing Y and then X diffX_Y_2 = AbsDiff(X, Y, A, B, N) return max (diffX_Y_1, diffX_Y_2) # Driver Code X = 10 Y = 10 A = 8 B = 5 N = 3 print (maxAbsDiff(X, Y, A, B, N)) # This code is contributed by sanjoy_62 |
C#
// C# program to implement // the above approach using System; class GFG{ // Function to find the absolute difference // between X and Y with given operations public static int AbsDiff( int X, int Y, int A, int B, int N) { // Stores maximum absolute difference // between X and Y with given operations int maxDiff = 0; // Stores maximum number of operations // performed on X int n1 = X - A; // Update X X = X - Math.Min(N, n1); // Decrementing N at most N times N = N - Math.Min(N, n1); // Stores maximum number of operations // performed on Y int n2 = Y - B; // Update Y Y = Y - Math.Min(N, n2); // Update maxDiff maxDiff = Math.Abs(X - Y); return maxDiff; } // Function to find the max absolute difference // between X and Y with given operations public static int maxAbsDiff( int X, int Y, int A, int B, int N) { // Stores absolute difference between // X and Y by first decrementing X and then Y int diffX_Y_1; // Stores absolute difference between X // and Y first decrementing Y and then X int diffX_Y_2; // Update diffX_Y_1 diffX_Y_1 = AbsDiff(X, Y, A, B, N); // Swap X, Y and A, B int temp1 = X; X = Y; Y = temp1; int temp2 = A; A = B; B = temp2; // Update diffX_Y_2 diffX_Y_2 = AbsDiff(X, Y, A, B, N); return Math.Max(diffX_Y_1, diffX_Y_2); } // Driver code public static void Main(String[] args) { int X = 10; int Y = 10; int A = 8; int B = 5; int N = 3; Console.WriteLine(maxAbsDiff(X, Y, A, B, N)); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // Javascript program to implement // the above approach // Function to find the absolute difference // between X and Y with given operations function AbsDiff(X, Y, A, B, N) { // Stores maximum absolute difference // between X and Y with given operations let maxDiff = 0; // Stores maximum number of operations // performed on X let n1 = X - A; // Update X X = X - Math.min(N, n1); // Decrementing N at most N times N = N - Math.min(N, n1); // Stores maximum number of operations // performed on Y let n2 = Y - B; // Update Y Y = Y - Math.min(N, n2); // Update maxDiff maxDiff = Math.abs(X - Y); return maxDiff; } // Function to find the max absolute difference // between X and Y with given operations function maxAbsDiff(X, Y, A, B, N) { // Stores absolute difference between // X and Y by first decrementing X and then Y let diffX_Y_1; // Stores absolute difference between X // and Y first decrementing Y and then X let diffX_Y_2; // Update diffX_Y_1 diffX_Y_1 = AbsDiff(X, Y, A, B, N); // Swap X, Y and A, B let temp1 = X; X = Y; Y = temp1; let temp2 = A; A = B; B = temp2; // Update diffX_Y_2 diffX_Y_2 = AbsDiff(X, Y, A, B, N); return Math.max(diffX_Y_1, diffX_Y_2); } // Driver Code let X = 10; let Y = 10; let A = 8; let B = 5; let N = 3; document.write(maxAbsDiff(X, Y, A, B, N)); </script> |
3
Time complexity: O(1)
Auxiliary Space:O(1)
Contact Us