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 endvoid 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 Codeint main(){ int X = 100, Y = 40021; convertXintoY(X, Y); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to check if X can be// converted to Y by multiplying// X by 2 or appending 1 at the endstatic 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 Codepublic 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 enddef 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 Codeif __name__ == '__main__': X,Y = 100, 40021 convertXintoY(X, Y)# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;class GFG{// Function to check if X can be// converted to Y by multiplying// X by 2 or appending 1 at the endstatic 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 Codepublic 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> |
Output
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 Ybool 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 Codeint 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 approachdef 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 CodeX = 100Y = 40021print(is_possible(X, Y)) |
C#
// C# program for the above approachusing 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 Yfunction 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 Codelet X = 100;let Y = 40021;// Function Callif (is_possible(X, Y)) console.log("True");else console.log("False"); |
Output
True
Time Complexity: O(2^N)
Auxiliary Space: O(log2(Y/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!
