K-ésimo entero positivo más pequeño que tiene una suma con el número dado igual a bit a bit O con el número dado

Dados dos enteros positivos X y K , la tarea es encontrar el K -ésimo entero positivo más pequeño Y, tal que X + Y = X | Y , donde | denota la operación OR bit a bit.

Ejemplo:

Entrada: X = 5, K = 1
Salida: 2
Explicación: El primer número es 2 como (2 + 5 = 2 | 5 )

Entrada: X = 5, K = 5
Salida: 18
Explicación: La lista de valores correctos es 2, 8, 10, 16, 18. El quinto número de esta lista es 18

Enfoque: el problema dado se puede resolver siguiendo los pasos mencionados a continuación:

• Sea el valor final Y . A partir de las propiedades de las operaciones bit a bit, se sabe que X + Y = X & Y + X | Y , donde & es un AND bit a bit de dos números
• Para que la ecuación en el enunciado del problema sea verdadera, el valor de X e Y debe ser 0
• Entonces, para todas las posiciones, si el i-ésimo bit está activado en X , entonces debe estar desactivado para todas las soluciones posibles de Y.
• Por ejemplo, si X = 1001101001 en binario (617 en notación decimal), los últimos diez dígitos de y deben ser Y = 0**00*0**0, donde ‘*’ indica cero o uno. Además, podemos rellenar cualquier número de cualquier dígito al principio del número, ya que todos los bits superiores son ceros.
• Entonces, la solución final será tratar todas las posiciones donde el bit puede ser 0 o 1 como una secuencia de izquierda a derecha y encontrar la notación binaria de K .
• Rellene todas las posiciones de acuerdo con la notación binaria de K

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

// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate K-th smallest
// solution(Y) of equation X+Y = X|Y
long long KthSolution(long long X, long long K)
{
    // Initialize the variable
    // to store the answer
    long long ans = 0;
 
    for (int i = 0; i < 64; i++) {
 
        // The i-th bit of X is off
        if (!(X & (1LL << i))) {
 
            // The i-bit of K is on
            if (K & 1) {
                ans |= (1LL << i);
            }
 
            // Divide K by 2
            K >>= 1;
 
            // If K becomes 0 then break
            if (!K) {
                break;
            }
        }
    }
    return ans;
}
// Driver Code
int main()
{
    long long X = 5, K = 5;
    cout << KthSolution(X, K);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG {
 
    // Function to calculate K-th smallest
    // solution(Y) of equation X+Y = X|Y
    static long KthSolution(long X, long K)
    {
       
        // Initialize the variable
        // to store the answer
        long ans = 0;
 
        for (int i = 0; i < 64; i++) {
 
            // The i-th bit of X is off
            if ((X & (1 << i)) == 0) {
 
                // The i-bit of K is on
                if ((K & 1) > 0) {
                    ans |= (1 << i);
                }
 
                // Divide K by 2
                K >>= 1;
 
                // If K becomes 0 then break
                if (K == 0) {
                    break;
                }
            }
        }
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
         long X = 5, K = 5;
        System.out.println(KthSolution(X, K));
    }
}
 
// This code is contributed by sanjoy_62.

# python implementation for the above approach
 
# Function to calculate K-th smallest
# solution(Y) of equation X+Y = X|Y
def KthSolution(X, K):
 
    # Initialize the variable
    # to store the answer
    ans = 0
 
    for i in range(0, 64):
 
        # The i-th bit of X is off
        if (not (X & (1 << i))):
 
            # The i-bit of K is on
            if (K & 1):
                ans |= (1 << i)
 
            # Divide K by 2
            K >>= 1
 
            # If K becomes 0 then break
            if (not K):
                break
 
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    X = 5
    K = 5
    print(KthSolution(X, K))
 
    # This code is contributed by rakeshsahni

// C# implementation for the above approach
using System;
class GFG
{
   
    // Function to calculate K-th smallest
    // solution(Y) of equation X+Y = X|Y
    static long KthSolution(long X, long K)
    {
        // Initialize the variable
        // to store the answer
        long ans = 0;
 
        for (int i = 0; i < 64; i++) {
 
            // The i-th bit of X is off
            if ((X & (1LL << i)) == 0) {
 
                // The i-bit of K is on
                if ((K & 1) > 0) {
                    ans |= (1LL << i);
                }
 
                // Divide K by 2
                K >>= 1;
 
                // If K becomes 0 then break
                if (K == 0) {
                    break;
                }
            }
        }
        return ans;
    }
   
    // Driver Code
    public static void Main()
    {
        long X = 5, K = 5;
        Console.Write(KthSolution(X, K));
    }
}
 
// This code is contributed by ukasp.

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to calculate K-th smallest
        // solution(Y) of equation X+Y = X|Y
        function KthSolution(X, K)
        {
         
            // Initialize the variable
            // to store the answer
            let ans = 0;
 
            for (let i = 0; i < 64; i++) {
 
                // The i-th bit of X is off
                if (!(X & (1 << i))) {
 
                    // The i-bit of K is on
                    if (K & 1) {
                        ans |= (1 << i);
                    }
 
                    // Divide K by 2
                    K >>= 1;
 
                    // If K becomes 0 then break
                    if (!K) {
                        break;
                    }
                }
            }
            return ans;
        }
         
        // Driver Code
        let X = 5, K = 5;
        document.write(KthSolution(X, K));
         
     // This code is contributed by Potta Lokesh
    </script>

18

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