Thursday, October 23, 2025
HomeData Modelling & AICheck whether it is possible to convert A into B

Check whether it is possible to convert A into B

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.  

  1. Convert current number x to 2 * x.
  2. 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 Queue
 
def 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 False
 
if __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 b
function 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 operations
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
int main()
{
    int A = 2, B = 82;
 
    if (canConvert(A, B))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}


Java




// Java implementation of the approach
class 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 approach
using 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 operations
function 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!

Dominic
Dominichttp://wardslaus.com
infosec,malicious & dos attacks generator, boot rom exploit philanthropist , wild hacker , game developer,
RELATED ARTICLES

Most Popular

Dominic
32361 POSTS0 COMMENTS
Milvus
88 POSTS0 COMMENTS
Nango Kala
6728 POSTS0 COMMENTS
Nicole Veronica
11892 POSTS0 COMMENTS
Nokonwaba Nkukhwana
11954 POSTS0 COMMENTS
Shaida Kate Naidoo
6852 POSTS0 COMMENTS
Ted Musemwa
7113 POSTS0 COMMENTS
Thapelo Manthata
6805 POSTS0 COMMENTS
Umr Jansen
6801 POSTS0 COMMENTS