Convierte X en Y multiplicando repetidamente X por 2 o agregando 1 al final

Dados dos números enteros positivos X e Y , la tarea es verificar si es posible convertir el número X en Y , ya sea multiplicando X por 2 o agregando 1 al final de X. Si es posible convertir X en Y , imprima “Sí” . De lo contrario, escriba “No” .

Ejemplos:

Entrada: X = 100, Y = 40021
Salida: Sí
Explicación:
A continuación se muestran las operaciones realizadas para convertir X en Y:
Operación 1: Multiplicar X(= 100) por 2, modifica el valor X a 200.
Operación 2: Agregar 1 en al final de X(= 200), modifica el valor X a 2001.
Operación 3: Multiplica X(= 2001) por 2, modifica el valor X a 4002.
Operación 4: Agrega 1 al final de X(= 4002), modifica el valor X a 40021.
Por lo tanto, de las operaciones anteriores, se puede ver que el valor X se puede convertir en Y. Por lo tanto, imprima Sí.

Entrada: X = 17 e Y = 35
Salida: No

Enfoque: El problema dado puede resolverse realizando las operaciones de manera inversa, es decir, intente convertir el valor Y en X. Siga los pasos a continuación para resolver el problema:

• Iterar hasta que el valor de Y sea mayor que X y realizar los siguientes pasos:
  • Si el valor del último dígito de Y es 1, divida el valor de Y entre 10 .
  • De lo contrario, si el valor de Y es divisible por 2, entonces divida Y por 2 .
  • De lo contrario, sal del bucle .
• Después de completar los pasos anteriores, si el valor de Y es el mismo que el valor de X , imprima Sí . De lo contrario , imprima No.

A continuación se muestra la implementación del enfoque anterior:

// 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 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.

# 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# 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

<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

Complejidad de tiempo: log(Y)
Espacio auxiliar: O(1)