Minimice los pasos para hacer que dos números enteros sean iguales incrementándolos o haciendo OR bit a bit de ellos

Dados dos enteros positivos A y B . La tarea es igualarlos usando operaciones mínimas tales que: 

• A = A + 1 (aumentar a en 1).
• B = B + 1 (aumentar b en 1).
• UN = UN | B (reemplace A con el OR bit a bit de A y B).

Ejemplos :

Entrada : A = 5, B = 9
Salida : 4
Explicación : es mejor usar la primera operación, es decir, aumentar A en 1 cuatro veces 
Entrada : A = 2, B = 5
Salida : 2
Explicación : es mejor aplicar la segunda operación luego tercera operación,

Enfoque codicioso: el problema se puede resolver utilizando la técnica codiciosa con la ayuda de la manipulación de bits .

Intuición: 

• Intenta aumentar A o B en 1, los pasos serán los máximos pasos posibles.
• Ahora para reducir estos pasos,
  • Necesitamos encontrar un número intermedio X tal que X OR B = B, porque solo así podemos saltar más de 1 número en un solo paso.
  • Una vez que hemos encontrado valores posibles para X, podemos verificar qué valor entre ellos es alcanzable para A en menos pasos.
  • Esos pasos mínimos + 1 paso (para hacer OR bit a bit de X con B) será uno de los pasos más pequeños para que A llegue a B.
• Otra forma de reducir estos pasos:
  • Considere el caso cuando en lugar de hacer que X O B = B, encontremos valores posibles de Y tales que A O Y = Y, ya que B también se puede mover según el problema dado.
  • Entonces podemos encontrar el paso mínimo necesario para mover B a Y y luego agregar 1 paso más para hacer OR bit a bit de A con B.
• Ahora intente encontrar el mínimo entre los dos posibles pasos menores como el número requerido de pasos para cambiar A a B.

Ilustración:

Supongamos que A = 2, B = 5

Caso 1: valor posible de X tal que (X O B = B) => [0, 1, 4, 5]
    Ahora, los pasos necesarios para convertir A en B si primero convertimos A en cada valor posible de X son:
        Convertir A a 0 => no es posible ya que no podemos decrementar A 
        Convertir A a 1 => no es posible ya que no podemos decrementar A 
        Convertir A a 4 => 2 operaciones de incremento, y luego 1 operación para 4 O 5 para convertir A en 5. Por lo tanto, la operación total = 3
        Convierte A en 5 => 3 incrementa la operación para convertir A en 5. Por lo tanto, la operación total = 3
Caso 2: Valor posible de Y tal que (A O Y = Y) => [2, 6, 7, …]
    Ahora, los pasos requeridos para convertir A en B si primero convertimos B en cada valor posible de Y, son:
        Convertir B en 2 => no es posible ya que no podemos decrementar B 
        Convierta B a 6 => 1 operación de incremento, y luego 1 operación para 2 O 6 para hacer A como 6. Por lo tanto, la operación total = 2
        Convierta B a 7 => 2 operaciones de incremento, y luego 1 operación para 2 O 7 para hacer A como 7. Por lo tanto, la operación total = 3
        De manera similar, para cualquier conversión de B a un valor mayor que 7 tomará más pasos. 

Por lo tanto, los pasos mínimos necesarios para convertir A en B usando las operaciones dadas = min(3, 2) = 2 pasos.

Siga los pasos que se mencionan a continuación para implementar el enfoque:

• Iterar de i = A a B y verificar si ( i | B ) es lo mismo que B y los pasos necesarios para eso.
• Encuentre los pasos mínimos (digamos x ) requeridos para hacer que A y B sean iguales de esta manera.
• Ahora iterar para j = B a B+x :
  • Compruebe si ese j satisface el caso 2 como se mencionó anteriormente.
  • Actualice los pasos mínimos necesarios para que A y B sean iguales.
• Devuelve el número mínimo de pasos.

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

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find min steps
// to convert A to B
int AToB(int a, int b)
{
    int ans = INT_MAX;
 
    // If a is greater than b, swap them
    if (a > b) {
        int temp = b;
        b = a;
        a = temp;
    }
 
    // Check for every i from 0 to b
    for (int i = a; i <= b; i++) {
 
        // If i or b equals to b then
        // update the answer
        if ((i | b) == b) {
            int j = abs(a - i);
            if (i != b)
                j++;
            ans = min(ans, j);
        }
    }
 
    for (int i = b + 1; i <= b + ans; i++) {
        if ((i | a) == i) {
            ans = min(ans, i - b + 1);
        }
    }
 
    return ans;
}
 
// Driver Code
int main()
{
    int A = 2;
    int B = 5;
    cout << AToB(A, B);
    return 0;
}
 
// This code is contributed by Rohit Pradhan

// Java code to implement the approach
 
import java.io.*;
import java.lang.*;
class GFG {
 
    // Function to find min steps
    // to convert A to B
    public static int AToB(int a, int b)
    {
        int ans = Integer.MAX_VALUE;
 
        // If a is greater than b, swap them
        if (a > b) {
            int temp = b;
            b = a;
            a = temp;
        }
 
        // Check for every i from 0 to b
        for (int i = a; i <= b; i++) {
 
            // If i or b equals to b then
            // update the answer
            if ((i | b) == b) {
                int j = Math.abs(a - i);
                if (i != b)
                    j++;
                ans = Math.min(ans, j);
            }
        }
 
        for (int i = b + 1; i <= b + ans; i++) {
            if ((i | a) == i) {
                ans = Math.min(ans, i - b + 1);
            }
        }
 
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int A = 2;
        int B = 5;
        System.out.println(AToB(A, B));
    }
}

# Python3 code to implement the approach
INT_MAX = 2147483647
 
# Function to find min steps
# to convert A to B
def AToB(a, b):
 
    ans = INT_MAX
 
    # If a is greater than b, swap them
    if (a > b):
        temp = b
        b = a
        a = temp
 
    # Check for every i from 0 to b
    for i in range(a, b+1):
 
        # If i or b equals to b then
        # update the answer
        if ((i | b) == b):
            j = abs(a - i)
            if (i != b):
                j += 1
            ans = min(ans, j)
 
    for i in range(b+1, b+ans+1):
        if ((i | a) == i):
            ans = min(ans, i - b + 1)
 
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    A = 2
    B = 5
    print(AToB(A, B))
 
# This code is contributed by rakeshsahni

// C# code to implement the above approach
using System;
 
class GFG {
 
  // Function to find min steps
  // to convert A to B
  public static int AToB(int a, int b)
  {
    int ans = Int32.MaxValue;
 
    // If a is greater than b, swap them
    if (a > b) {
      int temp = b;
      b = a;
      a = temp;
    }
 
    // Check for every i from 0 to b
    for (int i = a; i <= b; i++) {
 
      // If i or b equals to b then
      // update the answer
      if ((i | b) == b) {
        int j = Math.Abs(a - i);
        if (i != b)
          j++;
        ans = Math.Min(ans, j);
      }
    }
 
    for (int i = b + 1; i <= b + ans; i++) {
      if ((i | a) == i) {
        ans = Math.Min(ans, i - b + 1);
      }
    }
 
    return ans;
  }
 
  // Driver code
  public static void Main()
  {
    int A = 2;
    int B = 5;
    Console.Write(AToB(A, B));
  }
}
 
// This code is contributed by sanjoy_62.

<script>
// JavaScript code to implement the approach
 
// Function to find min steps
// to convert A to B
function AToB(a, b)
{
    var ans = Number.MAX_SAFE_INTEGER;
 
    // If a is greater than b, swap them
    if (a > b) {
        var temp = b;
        b = a;
        a = temp;
    }
 
    // Check for every i from 0 to b
    for (var i = a; i <= b; i++) {
 
        // If i or b equals to b then
        // update the answer
        if ((i | b) == b) {
            var j = Math.abs(a - i);
            if (i != b)
                j++;
            ans = Math.min(ans, j);
        }
    }
 
    for (var i = b + 1; i <= b + ans; i++) {
        if ((i | a) == i) {
            ans = Math.min(ans, i - b + 1);
        }
    }
 
    return ans;
}
 
// Driver Code
var A = 2;
var B = 5;
document.write(AToB(A, B));
 
// This code is contributed by phasing17
</script>

2

Complejidad de Tiempo: O(B * log B)
Espacio Auxiliar: O(1)