Maximize absolute difference between X and Y by at most N decrements

0 0 7 minutes read

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) = 4

Input: 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>

Output:

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