Redirecting to
NADOS

Min Xor Pairs

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given an array of distinct integers.
2. You have to print all pairs of integers in the array whose XOR value is minimum.
Input Format 
A number N
arr1
arr2..
N numbers
Output Format 
Check the sample output and question video.
Question Video
Constraints 
1 <= n <= 10^5
-10^9 <= arr[i] <= 10^9
Sample Input 
4
2
0
5
7
Sample Output 
0, 2
5, 7


  • Editorial

    In this problem, we are provided with an array of integers and we need to print all integer pairs from this given array which have minimum XOR result.

    A brute force approach would be to generate all pairs with two nested loops so we get the number of pairs equals NC2 and for every pair, we can calculate the XOR result and then return the minimum result. This approach has a time complexity of O(N2).

    We can optimize the solution to O(NlogN) by using sorting.

    Claim: If a <= b <= c then, either a ^ b < a ^ c or b ^ c < a ^ c

    Proof:

    a -> 1 1 0 1 0 ... => [same bits] [different bit] [non-significant bits]

    b -> 1 1 0 1 0 ... => [same bits] [different bit] [non-significant bits]

    c -> 1 1 0 1 1 ... => [same bits] [different bit] [non-significant bits]

    a^b 0 0 0 0 1 ... => [0s...] [1] [redundant]

    a^c 0 0 0 0 0 ... => [0s...] [0] [redundant]

    Here a^b < a^c

    a -> 1 1 0 1 0 ... => [same bits] [different bit] [non-significant bits]

    b -> 1 1 0 1 1 ... => [same bits] [different bit] [non-significant bits]

    c -> 1 1 0 1 1 ... => [same bits] [different bit] [non-significant bits]

    b^c 0 0 0 0 1 ... => [0s...] [1] [redundant]

    a^c 0 0 0 0 0 ... => [0s...] [0] [redundant]

    Here b^c < a^c

    Hence proved.

    This claim implies that XOR of non-adjacent sorted numbers will always be less than XOR of the adjacent sorted number, i.e., if we have numbers [a, b, c] we already know that either pair (a, b) or pair (b, c) will be our result so pair (a, c) will be redundant. Expanding this idea to numbers [ a, b, c, d, e] then we only need to check XORs of (a, b), (b, c), (c, d), and (d, e).

    Hence after sorting which takes O(NlogN) time we only need to traverse the array once to get our adjacent pairs XOR values.

    Time Complexity: O(NlogN)

    Sorting is involved which takes NlogN time.

    Space Complexity: O(1)

    The space complexity for the function is constant.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name