Given 4 integers X, Y, A, B. In one move either decrease X by A and Y by B or decrease X by B and Y by A. Calculate maximum possible moves. Given 4 integers X, Y, A, B. In one move we can make X = X – A and Y = Y – B or X = X – B and Y = Y – A. Calculate maximum total possible moves.
Example:
Input: X = 10, Y = 12, A = 2, B = 5
Output: 3
Explanation: 1st move: X = 8, Y = 7 after subtracting X by A and Y by B
2nd move: X = 6, Y = 2 after subtracting X by A and Y by B
3rd move: X = 1, Y = 0 after subtracting X by B and Y by A
So a total of 3 moves can be performed.Input: X = 1, Y = 1, A = 2, B = 2
Output: 0
Naive Approach: At every value of X and Y we can subtract max of A and B from max of X and Y and subtract min of A and B from min of X and Y until X and Y stays greater than zero.
Efficient Approach: Given problem can be solved using binary search on answer technique.
- The key idea here is that if for any number of moves N if it is possible to perform this many moves then we can also perform N – 1 moves.
- So we can do a binary search over the answer. Fix the range L = 1 and R = 10000000 (Change this if there are large integer values) and for each value mid = (L + R)/2 check if we can perform this much of moves. If possible then shift L = mid + 1, else R = mid – 1. Return the maximum possible value.
- To check for any number mid, we have to decrease X and Y at least mid * min(A, B) and for the remaining element, we can calculate total values for remaining for |A – B|. If these values are greater than mid then increase our right range otherwise decrease the left range.
Implementation:
C++
// C++ Program to implement the above approach#include <bits/stdc++.h>using namespace std;// Helper function to check if// we can perform Mid number of moves#define MAXN 10000000 // MAXN = 1e7bool can(int Mid, int X, int Y, int A, int B){ // Remove atleast Mid * B from both X and Y int p1 = X - Mid * B; int p2 = Y - Mid * B; // If any value is negative return false. if (p1 < 0 || p2 < 0) { return false; } // Calculate remaining values int k = A - B; if (k == 0) { return true; } int val = p1 / k + p2 / k; // If val >= Mid then it is possible // to perform this much moves if (val >= Mid) { return true; } // else return false return false;}int maxPossibleMoves(int X, int Y, int A, int B){ // Initialize a variable to store the answer int ans = 0; // Fix the left and right range int L = 1, R = MAXN; // Binary Search over the answer while (L <= R) { // Check for the middle // value as the answer int Mid = (L + R) / 2; if (can(Mid, X, Y, A, B)) { // It is possible to perform // this much moves L = Mid + 1; // Maximise the answer ans = max(ans, Mid); } else { R = Mid - 1; } } // Return answer return ans;}// Driver Codeint main(){ int X = 10, Y = 12, A = 2, B = 5; // Generalise that A >= B if (A < B) { swap(A, B); } cout << maxPossibleMoves(X, Y, A, B);} |
Java
// Java program to implement the above approachimport java.io.*;class GFG{ // Helper function to check if// we can perform Mid number of movesstatic int MAXN = 10000000;static boolean can(int Mid, int X, int Y, int A, int B){ // Remove atleast Mid * B from both X and Y int p1 = X - Mid * B; int p2 = Y - Mid * B; // If any value is negative return false. if (p1 < 0 || p2 < 0) { return false; } // Calculate remaining values int k = A - B; if (k == 0) { return true; } int val = p1 / k + p2 / k; // If val >= Mid then it is possible // to perform this much moves if (val >= Mid) { return true; } // Else return false return false;}static int maxPossibleMoves(int X, int Y, int A, int B){ // Initialize a variable to store the answer int ans = 0; // Fix the left and right range int L = 1, R = MAXN; // Binary Search over the answer while (L <= R) { // Check for the middle // value as the answer int Mid = (L + R) / 2; if (can(Mid, X, Y, A, B)) { // It is possible to perform // this much moves L = Mid + 1; // Maximise the answer ans = Math.max(ans, Mid); } else { R = Mid - 1; } } // Return answer return ans;}// Driver Codepublic static void main(String[] args){ int X = 10, Y = 12, A = 2, B = 5; // Generalise that A >= B if (A < B) { int temp = A; A = B; B = temp; } System.out.println(maxPossibleMoves(X, Y, A, B));}}// This code is contributed by Potta Lokesh |
Python3
# Python Program to implement the above approach# Helper function to check if# we can perform Mid number of movesMAXN = 10000000def can(Mid, X, Y, A, B): # Remove atleast Mid * B from both X and Y p1 = X - Mid * B p2 = Y - Mid * B # If any value is negative return false. if (p1 < 0 or p2 < 0): return False # Calculate remaining values k = A - B if (k == 0): return True val = p1 // k + p2 // k # If val >= Mid then it is possible # to perform this much moves if (val >= Mid): return True # else return false return False def maxPossibleMoves(X, Y, A, B): # Initialize a variable to store the answer ans = 0 # Fix the left and right range L = 1 R = MAXN # Binary Search over the answer while (L <= R): # Check for the middle # value as the answer Mid = (L + R) // 2 if (can(Mid, X, Y, A, B)): # It is possible to perform # this much moves L = Mid + 1 # Maximise the answer ans = max(ans, Mid) else: R = Mid - 1 # Return answer return ans # Driver CodeX = 10Y = 12A = 2B = 5# Generalise that A >= Bif (A < B): tmp = A A = B B = tmp print(maxPossibleMoves(X, Y, A, B))# This code is contributed by shivanisinghss2110 |
C#
// C# program to implement the above approachusing System;class GFG{ // Helper function to check if// we can perform Mid number of movesstatic int MAXN = 10000000;static Boolean can(int Mid, int X, int Y, int A, int B){ // Remove atleast Mid * B from both X and Y int p1 = X - Mid * B; int p2 = Y - Mid * B; // If any value is negative return false. if (p1 < 0 || p2 < 0) { return false; } // Calculate remaining values int k = A - B; if (k == 0) { return true; } int val = p1 / k + p2 / k; // If val >= Mid then it is possible // to perform this much moves if (val >= Mid) { return true; } // Else return false return false;}static int maxPossibleMoves(int X, int Y, int A, int B){ // Initialize a variable to store the answer int ans = 0; // Fix the left and right range int L = 1, R = MAXN; // Binary Search over the answer while (L <= R) { // Check for the middle // value as the answer int Mid = (L + R) / 2; if (can(Mid, X, Y, A, B)) { // It is possible to perform // this much moves L = Mid + 1; // Maximise the answer ans = Math.Max(ans, Mid); } else { R = Mid - 1; } } // Return answer return ans;}// Driver Codepublic static void Main(String[] args){ int X = 10, Y = 12, A = 2, B = 5; // Generalise that A >= B if (A < B) { int temp = A; A = B; B = temp; } Console.Write(maxPossibleMoves(X, Y, A, B));}}// This code is contributed by shivanisinghss2110 |
Javascript
<script>// Javascript Program to implement the above approach// Helper function to check if// we can perform Mid number of moveslet MAXN = 10000000; // MAXN = 1e7function can(Mid, X, Y, A, B){ // Remove atleast Mid * B from both X and Y let p1 = X - Mid * B; let p2 = Y - Mid * B; // If any value is negative return false. if (p1 < 0 || p2 < 0) { return false; } // Calculate remaining values let k = A - B; if (k == 0) { return true; } let val = Math.floor(p1 / k) + Math.floor(p2 / k); // If val >= Mid then it is possible // to perform this much moves if (val >= Mid) { return true; } // else return false return false;}function maxPossibleMoves(X, Y, A, B){ // Initialize a variable to store the answer let ans = 0; // Fix the left and right range let L = 1, R = MAXN; // Binary Search over the answer while (L <= R) { // Check for the middle // value as the answer let Mid = Math.floor((L + R) / 2); if (can(Mid, X, Y, A, B)) { // It is possible to perform // this much moves L = Mid + 1; // Maximise the answer ans = Math.max(ans, Mid); } else { R = Mid - 1; } } // Return answer return ans;}// Driver Codelet X = 10, Y = 12, A = 2, B = 5; // Generalise that A >= Bif (A < B) { let temp = A; A = B; B = temp;}document.write(maxPossibleMoves(X, Y, A, B));// This code is contributed by _saurabh_jaiswal.</script> |
Output:
3
Time Complexity: O(log(MAXN)), where MAXN is maximum number of moves
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!
Share your thoughts in the comments
