Given initial values of two positive integers X and Y, Find the final value of X and Y according to the below alterations:
1. If X=0 or Y=0, terminate the process. Else, go to step 2;
2. If X >= 2*Y, then change the value of X to X – 2*Y, and repeat step 1. Else, go to step 3;
3. If Y >= 2*X, then assign the value of Y to Y – 2*X, and repeat step 1. Else, end the process.
Constraints: 1<=X, Y<=10^18
Examples:
Input: X=12, Y=5
Output: X=0, Y=1
Explanation:
Initially X = 12, Y = 5
--> X = 2, Y = 5 (as X = X-2*Y)
--> X = 2, Y = 1 (as Y = Y-2*X)
--> X = 0, Y = 1 (as X = X-2*Y)
--> Stop (as X = 0)
Input: X=31, Y=12
Output: X=7, Y=12
Explanation:
Initially X = 31, Y = 12
--> X = 7, Y = 12 (as X = X-2*Y)
--> Stop (as (Y - 2*X) < 0)
Approach: Since the initial values of X and Y can be as high as 10^18. Simple brute force approach will not work.
If we observe carefully, the problem statement is nothing but a sort of Euclid Algorithm, where we will replace all subtractions with modulo.
Implementation:
C++
// CPP to implement above approach#include <iostream>using namespace std;// Function to get final value of X and Yvoid alter(long long int x, long long int y){ // Following the sequence // but by replacing minus with modulo while (true) { // Step 1 if (x == 0 || y == 0) break; // Step 2 if (x >= 2 * y) x = x % (2 * y); // Step 3 else if (y >= 2 * x) y = y % (2 * x); // Otherwise terminate else break; } cout << "X=" << x << ", " << "Y=" << y;}// Driver functionint main(){ // Get the initial X and Y values long long int x = 12, y = 5; // Find the result alter(x, y); return 0;} |
Java
// Java to implement above approachimport java.io.*;class GFG { // Function to get final value of X and Ystatic void alter(long x, long y){ // Following the sequence but by // replacing minus with modulo while (true) { // Step 1 if (x == 0 || y == 0) break; // Step 2 if (x >= 2 * y) x = x % (2 * y); // Step 3 else if (y >= 2 * x) y = y % (2 * x); // Otherwise terminate else break; } System.out.println("X = " + x + ", " + "Y = " + y);}// Driver Codepublic static void main (String[] args) { // Get the initial X and Y values long x = 12, y = 5; // Find the result alter(x, y);}}// This code is contributed by // shk |
Python3
# Python3 to implement above approachimport math as mt# Function to get final value of X and Ydef alter(x, y): # Following the sequence but by # replacing minus with modulo while (True): # Step 1 if (x == 0 or y == 0): break # Step 2 if (x >= 2 * y): x = x % (2 * y) # Step 3 elif (y >= 2 * x): y = y % (2 * x) # Otherwise terminate else: break print("X =", x, ", ", "Y =", y)# Driver Code# Get the initial X and Y valuesx, y = 12, 5# Find the resultalter(x, y)# This code is contributed by# Mohit kumar 29 |
C#
// C# implementation of the approach using System;class GFG{ // Function to get final value of X and Y static void alter(long x, long y) { // Following the sequence but by // replacing minus with modulo while (true) { // Step 1 if (x == 0 || y == 0) break; // Step 2 if (x >= 2 * y) x = x % (2 * y); // Step 3 else if (y >= 2 * x) y = y % (2 * x); // Otherwise terminate else break; } Console.WriteLine("X = " + x + ", " + "Y = " + y); } // Driver Code public static void Main () { // Get the initial X and Y values long x = 12, y = 5; // Find the result alter(x, y); }}// This code is contributed by aishwarya.27 |
Javascript
<script>// Javascript to implement above approach// Function to get final value of X and Yfunction alter(x, y){ // Following the sequence but by // replacing minus with modulo while (true) { // Step 1 if (x == 0 || y == 0) break; // Step 2 if (x >= 2 * y) x = x % (2 * y); // Step 3 else if (y >= 2 * x) y = y % (2 * x); // Otherwise terminate else break; } document.write("X = " + x + ", " + "Y = " + y);}// Driver Code// Get the initial X and Y valuesvar x = 12, y = 5;// Find the resultalter(x, y);// This code is contributed by Kirti</script> |
PHP
<?php// PHP implementation of the approach // Function to get final value of X and Y function alter($x, $y) { // Following the sequence but by // replacing minus with modulo while (true) { // Step 1 if ($x == 0 || $y == 0) break; // Step 2 if ($x >= 2 * $y) $x = $x % (2 * $y); // Step 3 else if ($y >= 2 * $x) $y = $y % (2 * $x); // Otherwise terminate else break; } echo "X = ", $x, ", ", "Y = ", $y; } // Driver Code // Get the initial X and Y values $x = 12 ;$y = 5 ;// Find the result alter($x, $y); // This code is contributed by Ryuga?> |
Output
X=0, Y=1
Time Complexity: O(min(x,y))
Auxiliary Space: O(1)
Using Recursion:
Approach:
- Recursive function to get the final X and Y by checking if X and Y are greater than 0 and if X or Y are greater than or equal to 2 times the other variable
- If X is greater than or equal to 2 times Y, X is updated to X minus 2 times Y and the function is called recursively with the updated X and Y values
- If Y is greater than or equal to 2 times X, Y is updated to Y minus 2 times X and the function is called recursively with the updated X and Y values
- If none of the above conditions are met, the function returns the current X and Y values as the final values.
- Finally, a while loop prints the steps taken to get the final X and Y values.
C++
#include <iostream>// Function to perform the alternate X and Y approachstd::pair<int, int> alternateXYApproach(int X, int Y) { if (X <= 0 || Y <= 0) { // If either X or Y is less than or equal to 0, return as is return std::make_pair(X, Y); } else if (X >= 2 * Y) { // If X is greater than or equal to 2 times Y, subtract 2*Y from X and keep Y as is return alternateXYApproach(X - 2 * Y, Y); } else if (Y >= 2 * X) { // If Y is greater than or equal to 2 times X, subtract 2*X from Y and keep X as is return alternateXYApproach(X, Y - 2 * X); } else { // If none of the above conditions are met, return X and Y as is return std::make_pair(X, Y); }}int main() { // Example 1 int X1 = 12; int Y1 = 5; std::pair<int, int> result1 = alternateXYApproach(X1, Y1); std::cout << "Input: X=" << X1 << ", Y=" << Y1 << std::endl; std::cout << "Output: X=" << result1.first << ", Y=" << result1.second << std::endl; std::cout << "Explanation:" << std::endl; while (result1.first > 0 && result1.second > 0) { if (result1.first >= 2 * result1.second) { result1.first -= 2 * result1.second; } else if (result1.second >= 2 * result1.first) { result1.second -= 2 * result1.first; } else { break; } if (result1.first >= 0) { std::cout << " --> X=" << result1.first << ", Y=" << result1.second << " (as X = X-2*Y)" << std::endl; } else { std::cout << " --> X=" << result1.first << ", Y=" << result1.second << " (as Y = Y-2*X)" << std::endl; } } std::cout << " --> Stop (as X = 0)" << std::endl; std::cout << std::endl; // Example 2 int X2 = 31; int Y2 = 12; std::pair<int, int> result2 = alternateXYApproach(X2, Y2); std::cout << "Input: X=" << X2 << ", Y=" << Y2 << std::endl; std::cout << "Output: X=" << result2.first << ", Y=" << result2.second << std::endl; std::cout << "Explanation:" << std::endl; while (result2.first > 0 && result2.second > 0) { if (result2.first >= 2 * result2.second) { result2.first -= 2 * result2.second; } else if (result2.second >= 2 * result2.first) { result2.second -= 2 * result2.first; } else { break; } if (result2.first >= 0) { std::cout << " --> X=" << result2.first << ", Y=" << result2.second << " (as X = X-2*Y)" << std::endl; } else { std::cout << " --> X=" << result2.first << ", Y=" << result2.second << " (as Y = Y-2*X)" << std::endl; } } std::cout << " --> Stop (as Y < 2*X)" << std::endl; return 0;} |
Java
public class AlternateXYApproach { public static int[] alternateXYApproach(int X, int Y) { // Base case: If either X or Y is less than or equal to 0, return X and Y. if (X <= 0 || Y <= 0) { int[] result = {X, Y}; return result; } // If X is at least twice the value of Y, subtract 2Y from X. else if (X >= 2 * Y) { return alternateXYApproach(X - 2 * Y, Y); } // If Y is at least twice the value of X, subtract 2X from Y. else if (Y >= 2 * X) { return alternateXYApproach(X, Y - 2 * X); } else { // If neither condition is met, return X and Y. int[] result = {X, Y}; return result; } } public static void main(String[] args) { // Example 1 int X1 = 12; int Y1 = 5; int[] result1 = alternateXYApproach(X1, Y1); System.out.println("Input: X=" + X1 + ", Y=" + Y1); System.out.println("Output: X=" + result1[0] + ", Y=" + result1[1]); System.out.println("Explanation:"); while (result1[0] > 0 && result1[1] > 0) { if (result1[0] >= 2 * result1[1]) { result1[0] -= 2 * result1[1]; } else if (result1[1] >= 2 * result1[0]) { result1[1] -= 2 * result1[0]; } else { break; } System.out.println(result1[0] >= 0 ? " --> X=" + result1[0] + ", Y=" + result1[1] + " (as X = X-2*Y)" : " --> X=" + result1[0] + ", Y=" + result1[1] + " (as Y = Y-2*X)"); } System.out.println(" --> Stop (as X = 0)\n"); // Example 2 int X2 = 31; int Y2 = 12; int[] result2 = alternateXYApproach(X2, Y2); System.out.println("Input: X=" + X2 + ", Y=" + Y2); System.out.println("Output: X=" + result2[0] + ", Y=" + result2[1]); System.out.println("Explanation:"); while (result2[0] > 0 && result2[1] > 0) { if (result2[0] >= 2 * result2[1]) { result2[0] -= 2 * result2[1]; } else if (result2[1] >= 2 * result2[0]) { result2[1] -= 2 * result2[0]; } else { break; } System.out.println(result2[0] >= 0 ? " --> X=" + result2[0] + ", Y=" + result2[1] + " (as X = X-2*Y)" : " --> X=" + result2[0] + ", Y=" + result2[1] + " (as Y = Y-2*X)"); } System.out.println(" --> Stop (as Y < 2*X)"); }} |
Python3
def alternate_x_y_approach_2(X, Y): if X <= 0 or Y <= 0: return X, Y elif X >= 2*Y: return alternate_x_y_approach_2(X-2*Y, Y) elif Y >= 2*X: return alternate_x_y_approach_2(X, Y-2*X) else: return X, Y# Example 1X = 12Y = 5result = alternate_x_y_approach_2(X, Y)print(f"Input: X={X}, Y={Y}")print(f"Output: X={result[0]}, Y={result[1]}")print("Explanation:")while result[0] > 0 and result[1] > 0: if result[0] >= 2*result[1]: result = (result[0]-2*result[1], result[1]) elif result[1] >= 2*result[0]: result = (result[0], result[1]-2*result[0]) else: break print(f" --> X={result[0]}, Y={result[1]} (as X = X-2*Y)" if result[0]>=0 else f" --> X={result[0]}, Y={result[1]} (as Y = Y-2*X)")print(" --> Stop (as X = 0)")print()# Example 2X = 31Y = 12result = alternate_x_y_approach_2(X, Y)print(f"Input: X={X}, Y={Y}")print(f"Output: X={result[0]}, Y={result[1]}")print("Explanation:")while result[0] > 0 and result[1] > 0: if result[0] >= 2*result[1]: result = (result[0]-2*result[1], result[1]) elif result[1] >= 2*result[0]: result = (result[0], result[1]-2*result[0]) else: break print(f" --> X={result[0]}, Y={result[1]} (as X = X-2*Y)" if result[0]>=0 else f" --> X={result[0]}, Y={result[1]} (as Y = Y-2*X)")print(" --> Stop (as Y < 2*X)") |
C#
using System;class Program{ // Function to perform the alternate X and Y approach static Tuple<int, int> AlternateXYApproach(int X, int Y) { if (X <= 0 || Y <= 0) { // If either X or Y is less than or equal to 0, return as is return Tuple.Create(X, Y); } else if (X >= 2 * Y) { // If X is greater than or equal to 2 times Y, subtract 2*Y from X and keep Y as is return AlternateXYApproach(X - 2 * Y, Y); } else if (Y >= 2 * X) { // If Y is greater than or equal to 2 times X, subtract 2*X from Y and keep X as is return AlternateXYApproach(X, Y - 2 * X); } else { // If none of the above conditions are met, return X and Y as is return Tuple.Create(X, Y); } } static void Main(string[] args) { // Example 1 int X1 = 12; int Y1 = 5; Tuple<int, int> result1 = AlternateXYApproach(X1, Y1); Console.WriteLine("Input: X=" + X1 + ", Y=" + Y1); Console.WriteLine("Output: X=" + result1.Item1 + ", Y=" + result1.Item2); Console.WriteLine("Explanation:"); while (result1.Item1 > 0 && result1.Item2 > 0) { if (result1.Item1 >= 2 * result1.Item2) { result1 = Tuple.Create(result1.Item1 - 2 * result1.Item2, result1.Item2); } else if (result1.Item2 >= 2 * result1.Item1) { result1 = Tuple.Create(result1.Item1, result1.Item2 - 2 * result1.Item1); } else { break; } if (result1.Item1 >= 0) { Console.WriteLine(" --> X=" + result1.Item1 + ", Y=" + result1.Item2 + " (as X = X-2*Y)"); } else { Console.WriteLine(" --> X=" + result1.Item1 + ", Y=" + result1.Item2 + " (as Y = Y-2*X)"); } } Console.WriteLine(" --> Stop (as X = 0)"); Console.WriteLine(); // Example 2 int X2 = 31; int Y2 = 12; Tuple<int, int> result2 = AlternateXYApproach(X2, Y2); Console.WriteLine("Input: X=" + X2 + ", Y=" + Y2); Console.WriteLine("Output: X=" + result2.Item1 + ", Y=" + result2.Item2); Console.WriteLine("Explanation:"); while (result2.Item1 > 0 && result2.Item2 > 0) { if (result2.Item1 >= 2 * result2.Item2) { result2 = Tuple.Create(result2.Item1 - 2 * result2.Item2, result2.Item2); } else if (result2.Item2 >= 2 * result2.Item1) { result2 = Tuple.Create(result2.Item1, result2.Item2 - 2 * result2.Item1); } else { break; } if (result2.Item1 >= 0) { Console.WriteLine(" --> X=" + result2.Item1 + ", Y=" + result2.Item2 + " (as X = X-2*Y)"); } else { Console.WriteLine(" --> X=" + result2.Item1 + ", Y=" + result2.Item2 + " (as Y = Y-2*X)"); } } Console.WriteLine(" --> Stop (as Y < 2*X)"); Console.ReadKey(); }} |
Javascript
// Function to perform the alternate X and Y approachfunction alternateXYApproach(X, Y) { if (X <= 0 || Y <= 0) { // If either X or Y is less than or equal to 0, return as is return [X, Y]; } else if (X >= 2 * Y) { // If X is greater than or equal to 2 times Y, subtract 2*Y from X and keep Y as is return alternateXYApproach(X - 2 * Y, Y); } else if (Y >= 2 * X) { // If Y is greater than or equal to 2 times X, subtract 2*X from Y and keep X as is return alternateXYApproach(X, Y - 2 * X); } else { // If none of the above conditions are met, return X and Y as is return [X, Y]; }}// Example 1let X1 = 12;let Y1 = 5;let result1 = alternateXYApproach(X1, Y1);console.log("Input: X=" + X1 + ", Y=" + Y1);console.log("Output: X=" + result1[0] + ", Y=" + result1[1]);console.log("Explanation:");while (result1[0] > 0 && result1[1] > 0) { if (result1[0] >= 2 * result1[1]) { result1[0] -= 2 * result1[1]; } else if (result1[1] >= 2 * result1[0]) { result1[1] -= 2 * result1[0]; } else { break; } if (result1[0] >= 0) { console.log(" --> X=" + result1[0] + ", Y=" + result1[1] + " (as X = X-2*Y)"); } else { console.log(" --> X=" + result1[0] + ", Y=" + result1[1] + " (as Y = Y-2*X)"); }}console.log(" --> Stop (as X = 0)");console.log("");// Example 2let X2 = 31;let Y2 = 12;let result2 = alternateXYApproach(X2, Y2);console.log("Input: X=" + X2 + ", Y=" + Y2);console.log("Output: X=" + result2[0] + ", Y=" + result2[1]);console.log("Explanation:");while (result2[0] > 0 && result2[1] > 0) { if (result2[0] >= 2 * result2[1]) { result2[0] -= 2 * result2[1]; } else if (result2[1] >= 2 * result2[0]) { result2[1] -= 2 * result2[0]; } else { break; } if (result2[0] >= 0) { console.log(" --> X=" + result2[0] + ", Y=" + result2[1] + " (as X = X-2*Y)"); } else { console.log(" --> X=" + result2[0] + ", Y=" + result2[1] + " (as Y = Y-2*X)"); }}console.log(" --> Stop (as Y < 2*X)");// This code is Contributed by Dwaipayan Bandyopadhyay |
Output
Input: X=12, Y=5
Output: X=0, Y=1
Explanation:
--> Stop (as X = 0)
Input: X=31, Y=12
Output: X=7, Y=12
Explanation:
--> Stop (as Y < 2*X)
Time Complexity: O(log X)
Space Complexity: O(log X)
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!
