Convert X into Y by repeatedly multiplying X with 2 or appending 1 at the end
Given two positive integers X and Y, the task is to check if it is possible to convert the number X into Y, either by multiplying X by 2 or appending 1 at the end of X. If it is possible to convert X into Y, then print “Yes”. Otherwise, print “No”.
Examples:
Input: X = 100, Y = 40021
Output: Yes
Explanation:
Below are the operations performed to convert X into Y:
Operation 1: Multiply X(= 100) by 2, modifies the value X to 200.
Operation 2: Append 1 at the end of X(= 200), modifies the value X to 2001.
Operation 3: Multiply X(= 2001) by 2, modifies the value X to 4002.
Operation 4: Append 1 at the end of X(= 4002), modifies the value X to 40021.
Therefore, from the above operations, it can be seen that the value X can be converted into Y. Hence, print Yes.Input: X = 17 and Y = 35
Output: No
Approach: The given problem can be solved by performing the operations in the reverse way i.e., try to convert the value Y into X. Follow the steps below to solve the problem:
- Iterate until the value of Y is greater than X and perform the following steps:
- If the value of the last digit of Y is 1, then divide the value of Y by 10.
- Otherwise, if the value of Y is divisible by 2, then divide Y by 2.
- Otherwise, break out of the loop.
- After completing the above steps, if the value of Y is the same as the value of X, then print Yes. Otherwise, print No.
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 X can be // converted to Y by multiplying // X by 2 or appending 1 at the end void convertXintoY( int X, int Y) { // Iterate until Y is at least X while (Y > X) { // If Y is even if (Y % 2 == 0) Y /= 2; // If the last digit of Y is 1 else if (Y % 10 == 1) Y /= 10; // Otherwise else break ; } // Check if X is equal to Y if (X == Y) cout << "Yes" ; else cout << "No" ; } // Driver Code int main() { int X = 100, Y = 40021; convertXintoY(X, Y); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to check if X can be // converted to Y by multiplying // X by 2 or appending 1 at the end static void convertXintoY( int X, int Y) { // Iterate until Y is at least X while (Y > X) { // If Y is even if (Y % 2 == 0 ) Y /= 2 ; // If the last digit of Y is 1 else if (Y % 10 == 1 ) Y /= 10 ; // Otherwise else break ; } // Check if X is equal to Y if (X == Y) System.out.print( "Yes" ); else System.out.print( "No" ); } // Driver Code public static void main(String[] args) { int X = 100 , Y = 40021 ; convertXintoY(X, Y); } } // This code is contributed by sanjoy_62. |
Python3
# Python program for the above approach # Function to check if X can be # converted to Y by multiplying # X by 2 or appending 1 at the end def convertXintoY(X, Y): # Iterate until Y is at least X while (Y > X): # If Y is even if (Y % 2 = = 0 ): Y / / = 2 # If the last digit of Y is 1 elif (Y % 10 = = 1 ): Y / / = 10 # Otherwise else : break # Check if X is equal to Y if (X = = Y): print ( "Yes" ) else : print ( "No" ) # Driver Code if __name__ = = '__main__' : X,Y = 100 , 40021 convertXintoY(X, Y) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; class GFG{ // Function to check if X can be // converted to Y by multiplying // X by 2 or appending 1 at the end static void convertXintoY( int X, int Y) { // Iterate until Y is at least X while (Y > X) { // If Y is even if (Y % 2 == 0) Y /= 2; // If the last digit of Y is 1 else if (Y % 10 == 1) Y /= 10; // Otherwise else break ; } // Check if X is equal to Y if (X == Y) Console.Write( "Yes" ); else Console.Write( "No" ); } // Driver Code public static void Main(String[] args) { int X = 100, Y = 40021; convertXintoY(X, Y); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // JavaScript program for the above approach // Function to check if X can be // converted to Y by multiplying // X by 2 or appending 1 at the end function convertXintoY(X, Y) { // Iterate until Y is at least X while (Y > X) { // If Y is even if (Y % 2 == 0) Y = parseInt(Y / 2); // If the last digit of Y is 1 else if (Y % 10 == 1) Y = parseInt(Y /= 10); // Otherwise else break ; } // Check if X is equal to Y if (X == Y) document.write( "Yes" ); else document.write( "No" ); } // Driver Code let X = 100, Y = 40021; convertXintoY(X, Y); // This code is contributed by Potta Lokesh </script> |
Yes
Time Complexity: log(Y)
Auxiliary Space: O(1)
Recursive Approach:
- Start with X as the initial number.
- Implement a recursive function that takes X and Y as parameters.
- In base case, If X == Y, return True and If X > Y, return False.
- In recursive case, Make two recursive calls with X * 2 and X * 10 + 1 as the new values of X and If either of the recursive calls returns True, return True.
- If no recursive call returns True, return False.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> using namespace std; // Function to check if it is possible to transform X to Y bool is_possible( int X, int Y) { // Base case if (X == Y) { return true ; } if (X > Y) { return false ; } // Recursive calls to explore all possible combinations // of operations return is_possible(X * 2, Y) || is_possible(X * 10 + 1, Y); } // Driver Code int main() { int X = 100; int Y = 40021; // Function Call cout << (is_possible(X, Y) ? "True" : "False" ) << endl; return 0; } |
Java
public class GFG { // Function to check if it is possible to transform X to Y public static boolean isPossible( int X, int Y) { // Base case if (X == Y) { return true ; } if (X > Y) { return false ; } // Recursive calls to explore all possible combinations of operations return isPossible(X * 2 , Y) || isPossible(X * 10 + 1 , Y); } // Driver Code public static void main(String[] args) { int X = 100 ; int Y = 40021 ; // Function Call System.out.println(isPossible(X, Y) ? "True" : "False" ); } } |
Python
# Python program for the above approach def is_possible(X, Y): # Base case if X = = Y: return True if X > Y: return False return is_possible(X * 2 , Y) or is_possible(X * 10 + 1 , Y) # Driver Code X = 100 Y = 40021 print (is_possible(X, Y)) |
C#
// C# program for the above approach using System; public class GFG { // Function to check if it is possible to transform X to Y public static bool IsPossible( int X, int Y) { // Base case if (X == Y) { return true ; } if (X > Y) { return false ; } // Recursive calls to explore all possible combinations // of operations return IsPossible(X * 2, Y) || IsPossible(X * 10 + 1, Y); } // Driver Code public static void Main() { int X = 100; int Y = 40021; // Function Call Console.WriteLine(IsPossible(X, Y) ? "True" : "False" ); } } |
Javascript
// JS program for the above approach // Function to check if it is possible to transform X to Y function is_possible(X, Y) { // Base case if (X == Y) { return true ; } if (X > Y) { return false ; } // Recursive calls to explore all possible combinations // of operations return is_possible(X * 2, Y) || is_possible(X * 10 + 1, Y); } // Driver Code let X = 100; let Y = 40021; // Function Call if (is_possible(X, Y)) console.log( "True" ); else console.log( "False" ); |
True
Time Complexity: O(2^N)
Auxiliary Space: O(log2(Y/X))