Maximum times X and Y can be reduced to near 0 using numbers A or B | C ++ Program to implement the above approach ; Helper function to check if we can perform Mid number of moves # define MAXN 10000000 MAXN = 1e7 ; Remove atleast Mid * B from both X and Y ; If any value is negative return false . ; Calculate remaining values ; If val >= Mid then it is possible to perform this much moves ; else return false ; Initialize a variable to store the answer ; Fix the left and right range ; Binary Search over the answer ; Check for the middle value as the answer ; It is possible to perform this much moves ; Maximise the answer ; Return answer ; Driver Code ; Generalise that A >= B
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool can ( int Mid , int X , int Y , int A , int B ) { int p1 = X - Mid * B ; int p2 = Y - Mid * B ; if ( p1 < 0 p2 < 0 ) { return false ; } int k = A - B ; if ( k == 0 ) { return true ; } int val = p1 / k + p2 / k ; if ( val >= Mid ) { return true ; } return false ; } int maxPossibleMoves ( int X , int Y , int A , int B ) { int ans = 0 ; int L = 1 , R = MAXN ; while ( L <= R ) { int Mid = ( L + R ) / 2 ; if ( can ( Mid , X , Y , A , B ) ) { L = Mid + 1 ; ans = max ( ans , Mid ) ; } else { R = Mid - 1 ; } } return ans ; } int main ( ) { int X = 10 , Y = 12 , A = 2 , B = 5 ; if ( A < B ) { swap ( A , B ) ; } cout << maxPossibleMoves ( X , Y , A , B ) ; }