Min Xor Value

Problem

Given an array of N integers, find the pair of integers in the array which have minimum XOR value. Report the minimum XOR value.

Examples

Example 1

1
2
3

Input: 0 2 5 7
Output: 2 (0 XOR 2)
Explanation: The minimum XOR value is 2, achieved by the pair (0, 2).

Example 2

1
2
3

Input: 0 4 7 9
Output: 3 (4 XOR 7)
Explanation: The minimum XOR value is 3, achieved by the pair (4, 7).

Constraints

• 2 ≤ N ≤ 100000
• 0 ≤ A[i] ≤ 1000000000

Solution

Method 1 – Brute Force

Intuition

Check every possible pair in the array and compute their XOR. This guarantees finding the minimum, but is inefficient for large arrays.

Approach

1. Initialize ans to a large value.
2. For every pair of indices (i, j) with i ≠ j, compute A[i] ^ A[j] and update ans if it is smaller.
3. Return ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	public int findMinXorBrute(int[] A) {
		int ans = Integer.MAX_VALUE;
		for (int i = 0; i < A.length; i++) {
			for (int j = 0; j < A.length; j++) {
				if (i != j) {
					ans = Math.min(ans, A[i] ^ A[j]);
				}
			}
		}
		return ans;
	}
}

1
2
3
4
5
6
7
8
9

from typing import List
class Solution:
	def findMinXorBrute(self, A: List[int]) -> int:
		ans = float('inf')
		for i in range(len(A)):
			for j in range(len(A)):
				if i != j:
					ans = min(ans, A[i] ^ A[j])
		return ans

Complexity

• ⏰ Time complexity: O(n^2) — Every possible pair is checked.
• 🧺 Space complexity: O(1) — Only a few variables are used.

Method 2 – Sort and Compare Adjacent Pairs

Intuition

The minimum XOR value for any pair in the array will always be found between two numbers that are next to each other in sorted order. This is because sorting brings similar numbers together, minimizing their XOR.

Approach

1. Sort the array.
2. Initialize ans to a large value.
3. For each pair of adjacent elements, compute their XOR and update ans if it is smaller.
4. Return ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
	int findMinXor(vector<int> &A) {
		sort(A.begin(), A.end());
		int ans = INT_MAX;
		for (int i = 0; i < (int)A.size() - 1; ++i) {
			ans = min(ans, A[i] ^ A[i+1]);
		}
		return ans;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
	public int findMinXor(int[] A) {
		Arrays.sort(A);
		int ans = Integer.MAX_VALUE;
		for (int i = 0; i < A.length - 1; i++) {
			ans = Math.min(ans, A[i] ^ A[i+1]);
		}
		return ans;
	}
}

1
2
3
4
5
6
7
8

from typing import List
class Solution:
	def findMinXor(self, A: List[int]) -> int:
		A.sort()
		ans = float('inf')
		for i in range(len(A) - 1):
			ans = min(ans, A[i] ^ A[i+1])
		return ans

Complexity

• ⏰ Time complexity: O(n log n) — Sorting the array dominates the runtime.
• 🧺 Space complexity: O(1) — Sorting can be done in-place, and only a few variables are used.