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 operationsint 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 operationsint 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 Codeint 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 codepublic 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 operationsdef 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 operationsdef 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 CodeX = 10Y = 10A = 8B = 5N = 3print(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 codepublic 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 operationsfunction 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 operationsfunction 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> |
Output:
3
Time complexity: O(1)
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!
