Given two integers A and B. The task is to check whether it is possible to convert A into B by performing below operations any number of times.
- Convert current number x to 2 * x.
- Convert current number x to (10 * x) + 1.
Examples:
Input: A = 2, B = 82
Output: Yes
2 -> 4 -> 41 -> 82
Input: A = 2, B = 5
Output: No
Approach:
- Create a queue and add A to the queue.
- While the queue is not empty, pop the front element from the queue and check if it’s equal to B. If yes, return true.
- Otherwise, check if it’s possible to apply the first operation (multiply by 2) or the second operation (multiply by 10 and add 1) to the popped element. If the result is less than or equal to B, add it to the queue.
- Repeat steps 2-3 until the queue is empty.
- If no path is found, return false.
- Print “Yes” if the function returns true, otherwise print “No”.
C++
#include <bits/stdc++.h>using namespace std;bool canConvert(int a, int b) { queue<int> q; q.push(a); while (!q.empty()) { int x = q.front(); q.pop(); if (x == b) { return true; } if (x * 2 <= b) { q.push(x * 2); } if ((10 * x + 1) <= b) { q.push(10 * x + 1); } } return false;}int main() { int A = 2, B = 82; if (canConvert(A, B)) cout << "Yes"; else cout << "No"; return 0;} |
Java
import java.util.*;public class Main { public static void main(String[] args) { int A = 2, B = 82; // Check if it is possible to convert A to B using the canConvert function if (canConvert(A, B)) System.out.println("Yes"); else System.out.println("No"); } // Function to check if it is possible to convert integer a to integer b public static boolean canConvert(int a, int b) { Queue<Integer> queue = new LinkedList<>(); // Start with the initial value a and add it to the queue queue.offer(a); // Perform a Breadth-First Search (BFS) to explore all possible conversions while (!queue.isEmpty()) { int x = queue.poll(); // If the current value is equal to the target value b, we can convert a to b if (x == b) { return true; } // Generate the next possible conversion by doubling the current value if (x * 2 <= b) { queue.offer(x * 2); } // Generate the next possible conversion by appending a '1' to the current value if ((10 * x + 1) <= b) { queue.offer(10 * x + 1); } } // If we have explored all possible conversions without finding b, it's not possible to convert a to b return false; }} |
Python3
from queue import Queuedef canConvert(a, b): # Create a queue to perform BFS q = Queue() q.put(a) while not q.empty(): x = q.get() if x == b: return True if x * 2 <= b: q.put(x * 2) if (10 * x + 1) <= b: q.put(10 * x + 1) return Falseif __name__ == "__main__": A = 2 B = 82 if canConvert(A, B): print("Yes") else: print("No") |
C#
using System;using System.Collections.Generic;public class GFG{ public static void Main(string[] args) { int A = 2, B = 82; // Check if it is possible to convert A to B using the CanConvert function if (CanConvert(A, B)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } // Function to check if it is possible to convert integer a to integer b public static bool CanConvert(int a, int b) { Queue<int> queue = new Queue<int>(); // Start with the initial value a and add it to the queue queue.Enqueue(a); // Perform a Breadth-First Search (BFS) to explore all possible conversions while (queue.Count > 0) { int x = queue.Dequeue(); // If the current value is equal to the target value b, we can convert a to b if (x == b) { return true; } // Generate the next possible conversion by doubling the current value if (x * 2 <= b) { queue.Enqueue(x * 2); } // Generate the next possible conversion by appending a '1' to the current value if ((10 * x + 1) <= b) { queue.Enqueue(10 * x + 1); } } // If we have explored all possible conversions // without finding b, it's not possible to convert a to b return false; }} |
Javascript
// Function to check if it is possible to convert integer a to integer bfunction canConvert(a, b) { let q = [a];// Perform a Breadth-First Search (BFS) to explore all possible conversions while (q.length > 0) { let x = q.shift();// If the current value is equal to the target value b, we can convert a to b if (x == b) { return true; }// Generate the next possible conversion by doubling the current value if (x * 2 <= b) { q.push(x * 2); } // Generate the next possible conversion by appending a '1' to the current value if ((10 * x + 1) <= b) { q.push(10 * x + 1); } }// If we have explored all possible conversions without finding b, it's not possible to convert a to b return false;}let A = 2, B = 82;if (canConvert(A, B)) console.log("Yes");else console.log("No"); |
Output
Yes
Time Complexity: O(B), where B is the upper bound of the range of possible values of the number b. In the worst case, the entire range from a to B needs to be traversed.
Space Complexity: O(B), since the size of the queue can grow up to B in the worst case, when all the possible values of x are added to the queue.
Approach: Let’s solve this problem in a reverse way – try to get the number A from B.
Note, that if B ends with 1 the last operation was to append the digit 1 to the right of the current number. Because of that let’s delete the last digit of B and move to the new number.
If the last digit is even then the last operation was to multiply the current number by 2. Because of that let’s divide B by 2 and move to the new number.
In the other cases (if B ends with an odd digit except 1) the answer is No.
We need to repeat the described algorithm after every time we get a new number. If at some point, we get a number that is equal to A then the answer is Yes, and if the new number is less than A then the answer is No.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function that returns true if A can be// converted to B with the given operationsbool canConvert(int a, int b){ while (b > a) { // If the current number ends with 1 if (b % 10 == 1) { b /= 10; continue; } // If the current number is divisible by 2 if (b % 2 == 0) { b /= 2; continue; } // If above two conditions fail return false; } // If it is possible to convert A to B if (b == a) return true; return false;}// Driver codeint main(){ int A = 2, B = 82; if (canConvert(A, B)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approachclass GFG{ // Function that returns true if A can be // converted to B with the given operations static boolean canConvert(int a, int b) { while (b > a) { // If the current number ends with 1 if (b % 10 == 1) { b /= 10; continue; } // If the current number is divisible by 2 if (b % 2 == 0) { b /= 2; continue; } // If above two conditions fail return false; } // If it is possible to convert A to B if (b == a) return true; return false; } // Driver code public static void main(String[] args) { int A = 2, B = 82; if (canConvert(A, B)) System.out.println("Yes"); else System.out.println("No"); }}// This code contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach # Function that returns true if A can be # converted to B with the given operations def canConvert(a, b) : while (b > a) : # If the current number ends with 1 if (b % 10 == 1) : b //= 10; continue; # If the current number is divisible by 2 if (b % 2 == 0) : b /= 2; continue; # If the above two conditions fail return false; # If it is possible to convert A to B if (b == a) : return True; return False; # Driver code if __name__ == "__main__" : A = 2; B = 82; if (canConvert(A, B)) : print("Yes"); else : print("No"); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System;class GFG{ // Function that returns true if A can be // converted to B with the given operations static bool canConvert(int a, int b) { while (b > a) { // If the current number ends with 1 if (b % 10 == 1) { b /= 10; continue; } // If the current number is divisible by 2 if (b % 2 == 0) { b /= 2; continue; } // If above two conditions fail return false; } // If it is possible to convert A to B if (b == a) return true; return false; } // Driver code public static void Main() { int A = 2, B = 82; if (canConvert(A, B)) Console.WriteLine("Yes"); else Console.WriteLine("No"); }}// This code is contributed by anuj_67.. |
Javascript
<script>// Javascript implementation of the approach// Function that returns true if A can be// converted to B with the given operationsfunction canConvert(a, b){ while (b > a) { // If the current number ends with 1 if (b % 10 == 1) { b = parseInt(b / 10); continue; } // If the current number is divisible by 2 if (b % 2 == 0) { b = parseInt(b / 2); continue; } // If above two conditions fail return false; } // If it is possible to convert A to B if (b == a) return true; return false;}// Driver code let A = 2, B = 82; if (canConvert(A, B)) document.write("Yes"); else document.write("No"); </script> |
Output
Yes
Time Complexity: O(logn)
Auxiliary Space: O(1)
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!
