El par más pequeño de enteros con diferencia mínima cuyo Bitwise XOR es N

Dado un entero positivo N , la tarea es encontrar los dos enteros más pequeños A y B tales que el XOR bit a bit de A y B sea N y la diferencia entre A y B sea mínima.

Ejemplos:

Entrada: N = 26
Salida: 10 16
Explicación:
El XOR bit a bit de 10 y 16 es 26 y la diferencia entre ellos es mínima.

Entrada: N = 1
Salida: 0 1

Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los pares posibles de números en el rango [0, N] e imprimir ese par de números cuyo Bitwise XOR es el número N dado y ambos números son los más pequeños. 

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior también se puede optimizar en función de las siguientes observaciones:

• Considere que la representación binaria de cualquier número es «1100011» , luego el número se puede dividir en torno a su bit más significativo (MSB) como «1000000» y «100011» y el XOR bit a bit de estos números es el número dado.
• De la división anterior, se puede observar que el número formado por «1000000» (digamos A ) y «100011» (digamos B ) es mínimo y su diferencia entre ellos es mínima ya que el valor formado por B será siempre más pequeño y más cercano . a A. _

De las observaciones anteriores, el valor mínimo de A y B que satisface los criterios dados es dividir el número N dado alrededor de su bit más significativo (MSB) .

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 find the numbers A and
// B whose Bitwise XOR is N and the
// difference between them is minimum
void findAandB(int N)
{
 
    // Find the MSB of the N
    int K = log2(N);
 
    // Find the value of B
    int B = (1 << K);
 
    // Find the value of A
    int A = B ^ N;
 
    // Print the result
    cout << A << ' ' << B;
}
 
// Driver Code
int main()
{
 
    int N = 26;
    findAandB(N);
 
    return 0;
}

// Java program for the above approach
public class MyClass
{
   
// Function to find the numbers A and
// B whose Bitwise XOR is N and the
// difference between them is minimum
static void findAandB(int N)
{
 
    // Find the MSB of the N
    int K = (int)(Math.log(N) / Math.log(2));
 
    // Find the value of B
    int B = (1 << K);
 
    // Find the value of A
    int A = B ^ N;
 
    // Print the result
    System.out.println(A + " " + B);
}
 
    public static void main(String args[]) {
      int N = 26;
      findAandB(N);
 
    }
}
 
// This code is contributed by SoumikMondal

# Python3 program for the above approach
from math import log2
 
# Function to find the numbers A and
# B whose Bitwise XOR is N and the
# difference between them is minimum
def findAandB(N):
     
    # Find the MSB of the N
    K = int(log2(N))
 
    # Find the value of B
    B = (1 << K)
 
    # Find the value of A
    A = B ^ N
 
    # Print the result
    print(A, B)
 
# Driver Code
if __name__ == '__main__':
     
    N = 26
     
    findAandB(N)
 
# This code is contributed by SURENDRA_GANGWAR

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the numbers A and
// B whose Bitwise XOR is N and the
// difference between them is minimum
static void findAandB(int N)
{
     
    // Find the MSB of the N
    int K = (int)(Math.Log(N) /
                  Math.Log(2));
 
    // Find the value of B
    int B = (1 << K);
 
    // Find the value of A
    int A = B ^ N;
 
    // Print the result
    Console.Write(A + " " + B);
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 26;
     
    findAandB(N);
}
}
 
// This code is contributed by sanjoy_62

<script>
 
        // JavaScript program for the above approach
 
        // Function to find the numbers A and
        // B whose Bitwise XOR is N and the
        // difference between them is minimum
        function findAandB(N) {
 
            // Find the MSB of the N
            let K = Math.log2(N);
 
            // Find the value of B
            let B = (1 << K);
 
            // Find the value of A
            let A = B ^ N;
 
            // Print the result
            document.write(A + ' ' + B);
        }
 
        // Driver Code
 
        let N = 26;
        findAandB(N);
 
 
  // This code is contributed by Potta Lokesh
   
 </script>

10 16

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)