Check if A and B can be reduced to 0 by decrementing with x and y with absolute difference at most K
Given three integers A, B, and K. The task is to check whether A and B can be reduced to zero by decrementing x and y from A and B respectively such that abs(x ā y) ā¤ K.
Example:
Input: A = 2, B = 7, K = 3
Output: YES
Explanation: Decrement values in the following way:
- Decrement 1 from A and 4 from B such that abs(1 ā 4) ā¤ 3, therefore, current value of A = 1 and B = 3.
- Decrement 1 from A and 3 from B such that abs(1 ā 3) ā¤ 3, current value of A = 0 and B = 0.
So, it is possible to reduce both the numbers to 0.
Input: A = 9, B = 8, K = 0
Output: NO
Approach: The task can be solved with a simple observation. The idea is to find the minimum and maximum out of A and B. If the minimum number multiplied by (1+K) is less than the maximum, then it is not possible to convert A and B to zero, else they can be converted to zero.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if it is possible // to reduce A and B to zero bool isPossibleToReduce( int A, int B, int k) { // Finding minimum and maximum // of A and B int mn = min(A, B); int mx = max(A, B); // If minimum multiply by (1+k) // is less than maximum then // return false if (mn * (1 + k) < mx) { return false ; } // Else return true; return true ; } // Driver Code int main() { int A = 2, B = 7; int K = 3; if (isPossibleToReduce(A, B, K)) cout << "YES" ; else cout << "NO" ; return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { /// Function to check if it is possible // to reduce A and B to zero static boolean isPossibleToReduce( int A, int B, int k) { // Finding minimum and maximum // of A and B int mn = Math.min(A, B); int mx = Math.max(A, B); // If minimum multiply by (1+k) // is less than maximum then // return false if (mn * ( 1 + k) < mx) { return false ; } // Else return true; return true ; } // Driver Code public static void main(String[] args) { int A = 2 , B = 7 ; int K = 3 ; if (isPossibleToReduce(A, B, K)) System.out.println( "YES" ); else System.out.println( "NO" ); } } // This code is contributed by dwivediyash |
Python3
# python program for the above approach # Function to check if it is possible # to reduce A and B to zero def isPossibleToReduce(A, B, k): # Finding minimum and maximum # of A and B mn = min (A, B) mx = max (A, B) # If minimum multiply by (1+k) # is less than maximum then # return false if (mn * ( 1 + k) < mx): return False # Else return true; return True # Driver Code if __name__ = = "__main__" : A = 2 B = 7 K = 3 if (isPossibleToReduce(A, B, K)): print ( "YES" ) else : print ( "NO" ) # This code is contributed by rakeshsahni |
C#
// C# program for the above approach using System; public class GFG { /// Function to check if it is possible // to reduce A and B to zero static bool isPossibleToReduce( int A, int B, int k) { // Finding minimum and maximum // of A and B int mn = Math.Min(A, B); int mx = Math.Max(A, B); // If minimum multiply by (1+k) // is less than maximum then // return false if (mn * (1 + k) < mx) { return false ; } // Else return true; return true ; } // Driver Code public static void Main( string [] args) { int A = 2, B = 7; int K = 3; if (isPossibleToReduce(A, B, K)) Console.WriteLine( "YES" ); else Console.WriteLine( "NO" ); } } // This code is contributed by AnkThon |
Javascript
<script> // Javascript program for the above approach // Function to check if it is possible // to reduce A and B to zero function isPossibleToReduce(A, B, k) { // Finding minimum and maximum // of A and B let mn = Math.min(A, B); let mx = Math.max(A, B); // If minimum multiply by (1+k) // is less than maximum then // return false if (mn * (1 + k) < mx) { return false ; } // Else return true; return true ; } // Driver Code let A = 2, B = 7; let K = 3; if (isPossibleToReduce(A, B, K)) document.write( "YES" ); else document.write( "NO" ); // This code is contributed by gfgking. </script> |
Output
YES
Time Complexity: O(1)
Auxiliary Space: O(1)