Given two numbers X and Y. The task is to check whether X and Y can be reduced to zero at the same time by performing the following operation any number of times:
- Choose any natural number (say z) and reduce X and Y as one of the following at each operation:
- X = X – z and Y = Y – 2*z
- X = X – 2*z and Y = Y – z
Example:
Input: X = 6, Y = 9
Output: YES
Explanation:
We can perform operation in following way:
if z = 1, then
X = X – 2*z = 6 – 2*(1)
Y = Y – z = 9 – 1
=> X = 4 & Y = 8
Now again if z = 4, then
X = X – z = 4 – 4
Y = Y – 2*z = 8 – 2*(4)
=> X = 0 & Y = 0
Therefore, X & Y become zero in 2 steps assuming z as 1 and 4 respectively.Input: X = 1, Y = 1
Output: NO
Explanation:
We don’t have any possible value for z such that X & Y can become zero simultaneously.
Approach:
Below are the observation for the given problem statement:
- Since X and Y are updated to (X – z and Y – 2*z) or (X – 2*z and Y – z), therefore after n number of operations (X + Y) is updated to (X + Y – 3*n*z). Hence X and Y can be reduced to zero at simultaneously if (X+Y)%3 equals 0.
- At each step one of the X or Y is reduced by 2*z. To reduced X and Y simultaneously zero it must satisfy this condition: max(X, Y)? 2*min(X, Y).
For Example:
Let X = 6 and Y = 15
Since (X+Y)%3 = (21%3) = 0
As our first condition is satisfied,
But by taking z = 6
X = X – z = 6 – 6 = 0
Y = Y – 2*z = 15 – 12 = 3
Since Y is not less than or equals to 2*X, therefore X and Y cannot be reduced to zero at same time.
If the above two conditions satisfy the values of X and Y, then X and Y can be reduced to 0 simultaneously.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Function to check if it is possible to// make x and y can become 0 at same timevoid canBeReduced(int x, int y){ int maxi = max(x, y); int mini = min(x, y); // Check the given conditions if (((x + y) % 3) == 0 && maxi <= 2*mini) cout << "YES" << endl; else cout << "NO" << endl;}// Driver Codeint main(){ int x = 6, y = 9; // Function Call canBeReduced(x, y); return 0;} |
Java
// Java program of the above approachimport java.util.*;class GFG{ // Function to check if it is possible to// make x and y can become 0 at same timestatic void canBeReduced(int x, int y){ int maxi = Math.max(x, y); int mini = Math.min(x, y); // Check the given conditions if (((x + y) % 3) == 0 && maxi <= 2*mini) System.out.print("YES" +"\n"); else System.out.print("NO" +"\n");} // Driver Codepublic static void main(String[] args){ int x = 6, y = 9; // Function Call canBeReduced(x, y);}}// This code is contributed by Rajput-Ji |
C#
// C# program of the above approachusing System; class GFG { // Function to check if it is possible to // make x and y can become 0 at same time static void canBeReduced(int x, int y) { int maxi = Math.Max(x, y); int mini = Math.Min(x, y); // Check the given conditions if (((x + y) % 3) == 0 && maxi <= 2*mini) Console.WriteLine("YES"); else Console.WriteLine("NO"); } // Driver Code static void Main() { int x = 6, y = 9; // Function Call canBeReduced(x, y); }}// This code is contributed by shubhamsingh10 |
Python3
# Python 3 program of the above approach# Function to check if it is possible to# make x and y can become 0 at same timedef canBeReduced(x,y): maxi = max(x, y) mini = min(x, y) # Check the given conditions if (((x + y) % 3) == 0 and maxi <= 2*mini): print("YES") else: print("NO")# Driver Codeif __name__ == '__main__': x = 6 y = 9 # Function Call canBeReduced(x, y) # This code is contributed by Surendra_Gangwar |
Javascript
<script>// javascript program of the above approach// Function to check if it is possible to// make x and y can become 0 at same timefunction canBeReduced(x , y){ var maxi = Math.max(x, y); var mini = Math.min(x, y); // Check the given conditions if (((x + y) % 3) == 0 && maxi <= 2*mini) document.write("YES" +"\n"); else document.write("NO" +"\n");} // Driver Codevar x = 6, y = 9; // Function CallcanBeReduced(x, y);// This code contributed by shikhasingrajput </script> |
YES
Time Complexity: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!