Dados dos enteros A y B . La tarea es elegir un entero X tal que (A xor X) + (B xor X) sea el mínimo posible.
Ejemplos:
Entrada: A = 2, B = 3
Salida: X = 2, Suma = 1Entrada: A = 7, B = 8
Salida: X = 0, Suma = 15
Una solución simple es generar todas las sumas posibles tomando xor de A y B con todos los valores posibles de X ≤ min(A, B) . Para generar todas las sumas posibles, tomaría O(N) tiempo donde N = min(A, B) .
Una solución eficiente se basa en el hecho de que el número X contendrá los bits establecidos solo en ese índice donde tanto A como B contienen un bit establecido, de modo que después de la operación xor con X , ese bit se desactivará. Esto tomaría solo el tiempo O (Log N) .
Otros casos: si en un índice en particular, uno o ambos números contienen 0 (bit no establecido) y el número X contiene 1 (bit establecido), entonces 0 se establecerá después de x o con X en A y B , entonces la suma no podría minimizarse .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <iostream> using namespace std; // Function to return the integer X such that // (A xor X) + (B ^ X) is minimized int findX(int A, int B) { int j = 0, x = 0; // While either A or B is non-zero while (A || B) { // Position at which both A and B // have a set bit if ((A & 1) && (B & 1)) { // Inserting a set bit in x x += (1 << j); } // Right shifting both numbers to // traverse all the bits A >>= 1; B >>= 1; j += 1; } return x; } // Driver code int main() { int A = 2, B = 3; int X = findX(A, B); cout << "X = " << X << ", Sum = " << (A ^ X) + (B ^ X); return 0; }
Java
// Java implementation of the approach class GFG { // Function to return the integer X such that // (A xor X) + (B ^ X) is minimized static int findX(int A, int B) { int j = 0, x = 0; // While either A or B is non-zero while (A != 0 || B != 0) { // Position at which both A and B // have a set bit if ((A % 2 == 1) && (B % 2 == 1)) { // Inserting a set bit in x x += (1 << j); } // Right shifting both numbers to // traverse all the bits A >>= 1; B >>= 1; j += 1; } return x; } // Driver code public static void main(String[] args) { int A = 2, B = 3; int X = findX(A, B); System.out.println( "X = " + X + ", Sum = " + ((A ^ X) + (B ^ X))); } } // This code has been contributed by 29AjayKumar
Python3
# Python 3 implementation of the approach # Function to return the integer X such that # (A xor X) + (B ^ X) is minimized def findX(A, B): j = 0 x = 0 # While either A or B is non-zero while (A or B): # Position at which both A and B # have a set bit if ((A & 1) and (B & 1)): # Inserting a set bit in x x += (1 << j) # Right shifting both numbers to # traverse all the bits A >>= 1 B >>= 1 j += 1 return x # Driver code if __name__ == '__main__': A = 2 B = 3 X = findX(A, B) print("X =", X, ", Sum =", (A ^ X) + (B ^ X)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach using System; class GFG { // Function to return the integer X such that // (A xor X) + (B ^ X) is minimized static int findX(int A, int B) { int j = 0, x = 0; // While either A or B is non-zero while (A != 0 || B != 0) { // Position at which both A and B // have a set bit if ((A % 2 == 1) && (B % 2 == 1)) { // Inserting a set bit in x x += (1 << j); } // Right shifting both numbers to // traverse all the bits A >>= 1; B >>= 1; j += 1; } return x; } // Driver code public static void Main(String[] args) { int A = 2, B = 3; int X = findX(A, B); Console.WriteLine( "X = " + X + ", Sum = " + ((A ^ X) + (B ^ X))); } } // This code has been contributed by 29AjayKumar
PHP
<?php // PHP implementation of the approach // Function to return the integer X such that // (A xor X) + (B ^ X) is minimized function findX($A, $B) { $j = 0; $x = 0; // While either A or B is non-zero while ($A || $B) { // Position at which both A and B // have a set bit if (($A & 1) && ($B & 1)) { // Inserting a set bit in x $x += (1 << $j); } // Right shifting both numbers to // traverse all the bits $A >>= 1; $B >>= 1; $j += 1; } return $x; } // Driver code $A = 2; $B = 3; $X = findX($A, $B); echo "X = " , $X , ", Sum = ", ($A ^ $X) + ($B ^ $X); // This code is contributed by ajit. ?>
Javascript
<script> // Javascript implementation of the approach // Function to return the integer X such that // (A xor X) + (B ^ X) is minimized function findX(A, B) { let j = 0, x = 0; // While either A or B is non-zero while (A != 0 || B != 0) { // Position at which both A and B // have a set bit if ((A % 2 == 1) && (B % 2 == 1)) { // Inserting a set bit in x x += (1 << j); } // Right shifting both numbers to // traverse all the bits A >>= 1; B >>= 1; j += 1; } return x; } let A = 2, B = 3; let X = findX(A, B); document.write("X = " + X + ", Sum = " + ((A ^ X) + (B ^ X))); // This code is contributed by suresh07. </script>
X = 2, Sum = 1
Complejidad del tiempo: O(log(max(A, B)))
Espacio Auxiliar: O(1)
Enfoque más eficiente:
Usando la idea de que X contendrá solo los bits establecidos como A y B, X = A & B. Al reemplazar X, la ecuación anterior se convierte en (A ^ (A & B)) + (B ^ (A & B)) que equivale a A^B .
Proof: Given (A ^ X) + (B ^ X) Taking X = (A & B), we have (A ^ (A & B)) + (B ^ (A & B)) (using x ^ y = x'y + y'x ) = (A'(A & B) + A(A & B)') + (B'(A & B) + B(A & B)') (using (x & y)' = x' + y') = (A'(A & B) + A(A' + B')) + (B'(A & B) + B(A' + B')) (A'(A & B) = A'A & A'B = 0, B'(A & B) = B'A & B'B = 0) = (A(A' + B')) + (B(A' + B')) = (AA' + AB') + (BA' + BB') (using xx' = x'x = 0) = (AB') + (BA') = (A ^ B)
Haga clic aquí para saber más sobre las propiedades booleanas.
A continuación se muestra la implementación del enfoque anterior:
C++
// c++ implementation of above approach #include <iostream> using namespace std; // finding X int findX(int A, int B) { return A & B; } // finding Sum int findSum(int A, int B) { return A ^ B; } // Driver code int main() { int A = 2, B = 3; cout << "X = " << findX(A, B) << ", Sum = " << findSum(A, B); return 0; } // This code is contributed by yashbeersingh42
Java
// Java implementation of above approach import java.io.*; class GFG { // finding X public static int findX(int A, int B) { return A & B; } // finding Sum public static int findSum(int A, int B) { return A ^ B; } // Driver Code public static void main(String[] args) { int A = 2, B = 3; System.out.print("X = " + findX(A, B) + ", Sum = " + findSum(A, B)); } } // This code is contributed by yashbeersingh42
Python3
# Python3 implementation of above approach # finding X def findX(A, B): return A & B # finding Sum def findSum(A, B): return A ^ B # Driver code A, B = 2, 3 print("X =", findX(A, B) , ", Sum =" , findSum(A, B)) # This code is contributed by divyeshrabadiya07
C#
// C# implementation of above approach using System; class GFG{ // Finding X public static int findX(int A, int B) { return A & B; } // Finding Sum public static int findSum(int A, int B) { return A ^ B; } // Driver Code public static void Main(String[] args) { int A = 2, B = 3; Console.Write("X = " + findX(A, B) + ", Sum = " + findSum(A, B)); } } // This code is contributed by Princi Singh
Javascript
<script> // Javascript implementation of the approach // finding X function findX(A, B) { return A & B; } // finding Sum function findSum(A, B) { return A ^ B; } let A = 2, B = 3; document.write("X = " + findX(A, B) + ", Sum = " + findSum(A, B)); </script>
X = 2, Sum = 1
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por NikhilRathor y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA