# Choose X such that (A xor X) + (B xor X) is minimized

Given two integers **A** and **B**. The task is to choose an integer **X** such that **(A xor X) + (B xor X)** is the minimum possible.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:A = 2, B = 3Output:X = 2, Sum = 1

Input:A = 7, B = 8Output:X = 0, Sum = 15

A **simple solution** is to generate all possible sum by taking xor of **A** and **B** with all possible values of **X â‰¤ min(A, B)**. To generate all possible sums it would take **O(N)** time where **N = min(A, B)**.

An **efficient solution** is based on the fact that the number **X** will contain the set bits only at that index where both **A** and **B** contain a set bit such that after xor operation with **X** that bit will be unset. This would take only **O(Log N)** time.**Other cases:** If at a particular index one or both the numbers contain **0** (unset bit) and the number **X** contains **1** (set bit) then **0** will be set after xor with **X** in **A** and **B** then the sum couldn’t be minimized.

Below is the implementation of the above approach:

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

**Output**

X = 2, Sum = 1

Time Complexity: O(log(max(A, B)))

Auxiliary Space: O(1)

**Most Efficient Approach:**

Using the idea that** X **will contain only the set bits as A and B,** X = A & B**. On replacing X, the above equation becomes **(A ^ (A & B)) + (B ^ (A & B))** which further equates to **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)

Click here to know more about Boolean Properties.

Below is the implementation of the above approach:

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

**Output**

X = 2, Sum = 1

Time Complexity: O(1)

Auxiliary Space: O(1)