Given an array of integers of size N find minimum xor of any 2 elements.
Example 1:
Input:
N = 3
arr[] = {9,5,3}
Output: 6
Explanation: 
There are 3 pairs -
9^5 = 12
5^3 = 6
9^3 = 10
Therefore output is 6.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minxorpair() which takes the array arr[], its size N as input parameters and returns the minimum value of xor of any 2 elements.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints:
1 <= N <= 10^{5}
1^{ }<= arr[i] <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def minxorpair (self, N, arr):
        # code here 
        
        

Solutions:
class Solution:

	def minxorpair(self, N, arr):
		arr.sort()
		min_xor = float('inf')
		for i in range(N - 1):
			xor_val = arr[i] ^ arr[i + 1]
			min_xor = min(min_xor, xor_val)
		return min_xor


class Solution:

	def minxorpair(self, N, arr):
		arr.sort()
		mini = float('inf')
		for i in range(N - 1):
			if arr[i] ^ arr[i + 1] < mini:
				mini = arr[i] ^ arr[i + 1]
		return mini


class TrieNode:

	def __init__(self):
		self.bits = {}
		self.val = None

class Trie:

	def __init__(self) -> None:
		self.root = TrieNode()

	def insert(self, n):
		curr_node = self.root
		for i in range(31, -1, -1):
			bitVal = 1 if n & 1 << i else 0
			if bitVal not in curr_node.bits:
				curr_node.bits[bitVal] = TrieNode()
			curr_node = curr_node.bits[bitVal]
		curr_node.val = n

	def _findMinXOR(self, n):
		curr_node = self.root
		for i in range(31, -1, -1):
			bitVal = 1 if n & 1 << i else 0
			if bitVal in curr_node.bits:
				curr_node = curr_node.bits[bitVal]
			elif bitVal ^ 1 in curr_node.bits:
				curr_node = curr_node.bits[bitVal ^ 1]
			else:
				return float('inf')
		return n ^ curr_node.val

class Solution:

	def minxorpair(self, N, arr):
		t = Trie()
		t.insert(arr[0])
		min_xor = arr[0] ^ arr[1]
		for n in arr[1:]:
			min_xor = min(min_xor, t._findMinXOR(n))
			t.insert(n)
		return min_xor


class Solution:

	def minxorpair(self, N, arr):
		arr.sort()
		curr = []
		ans = 100000000000
		for i in range(0, N - 1):
			ans = min(ans, arr[i] ^ arr[i + 1])
		return ans


class Solution:

	def minxorpair(self, N, arr):
		arr.sort()
		minXor = 9999999
		val = 0
		for i in range(0, N - 1):
			val = arr[i] ^ arr[i + 1]
			minXor = min(minXor, val)
		return minXor


class Solution:

	def minxorpair(self, N, arr):
		min = 9999
		arr.sort()
		for i in range(N - 1):
			if arr[i] ^ arr[i + 1] < min:
				min = arr[i] ^ arr[i + 1]
		return min


class Solution:

	def minxorpair(self, N, arr):
		arr.sort()
		ans = float('inf')
		stack = list()
		for i in range(1, N):
			ans = min(ans, arr[i - 1] ^ arr[i])
		return ans


class Solution:

	def minxorpair(self, N, arr):
		arr.sort()
		l = []
		m = 10000
		for i in range(N - 1):
			m = min(m, arr[i] ^ arr[i + 1])
		return m


class Solution:

	def minxorpair(self, N, arr):
		dummy = [0] * (10 ** 5 + 1)
		for i in range(N):
			if arr[i] == dummy[arr[i]]:
				return 0
			dummy[arr[i]] = arr[i]
		minm = float('inf')
		temp = cnt = 0
		for i in range(10 ** 5 + 1):
			if dummy[i]:
				if cnt:
					temp ^= dummy[i]
					minm = min(minm, temp)
					temp = dummy[i]
					cnt = 1
				else:
					temp ^= dummy[i]
					cnt += 1
		return minm


from itertools import combinations

class Solution:

	def minxorpair(self, N, arr):
		arr.sort()
		m = 10 ** 5 + 1
		for i in range(1, N):
			m = min(m, arr[i - 1] ^ arr[i])
		return m


class Solution:

	def minxorpair(self, N, arr):
		mini = 10 ** 9
		arr.sort()
		for i in range(N - 1):
			ans = arr[i] ^ arr[i + 1]
			mini = min(ans, mini)
		return mini


class Solution:

	def minxorpair(self, n, arr):
		arr.sort()
		minm = 100000000
		for i in range(1, n):
			minm = min(arr[i] ^ arr[i - 1], minm)
		return minm


import sys

class Solution:

	def minxorpair(self, N, arr):
		arr.sort()
		ans = sys.maxsize
		for i in range(0, N - 1):
			ans = min(ans, arr[i] ^ arr[i + 1])
		return ans


class BinaryTrie:

	def __init__(self, max_bit_len=32):
		self.inf = 1 << 63
		self.cc = [0]
		self.to = [[-1], [-1]]
		self.mb = max_bit_len

	def add(self, a):
		u = 0
		self.cc[u] += 1
		for i in range(self.mb - 1, -1, -1):
			d = a >> i & 1
			if self.to[d][u] == -1:
				self.to[d][u] = len(self.cc)
				self.to[0].append(-1)
				self.to[1].append(-1)
				self.cc.append(0)
			u = self.to[d][u]
			self.cc[u] += 1

	def remove(self, a):
		if self.cc[0] == 0:
			return False
		uu = [0]
		u = 0
		for i in range(self.mb - 1, -1, -1):
			d = a >> i & 1
			u = self.to[d][u]
			if u == -1 or self.cc[u] == 0:
				return False
			uu.append(u)
		for u in uu:
			self.cc[u] -= 1
		return True

	def cnt(self, a):
		u = 0
		for i in range(self.mb - 1, -1, -1):
			d = a >> i & 1
			u = self.to[d][u]
			if u == -1 or self.cc[u] == 0:
				return 0
		return self.cc[u]

	def min_xor(self, a):
		if self.cc[0] == 0:
			return self.inf
		(u, res) = (0, 0)
		for i in range(self.mb - 1, -1, -1):
			d = a >> i & 1
			v = self.to[d][u]
			if v == -1 or self.cc[v] == 0:
				res |= 1 << i
				u = self.to[d ^ 1][u]
			else:
				u = v
		return res

	def max_xor(self, a):
		if self.cc[0] == 0:
			return -self.inf
		(u, res) = (0, 0)
		for i in range(self.mb - 1, -1, -1):
			d = a >> i & 1
			v = self.to[d ^ 1][u]
			if v == -1 or self.cc[v] == 0:
				u = self.to[d][u]
			else:
				u = v
				res |= 1 << i
		return res

class Solution:

	def minxorpair(self, N, arr):
		ans = 10 ** 20
		trie = BinaryTrie()
		for i in arr:
			ans = min(ans, trie.min_xor(i))
			trie.add(i)
		return ans


class Solution:

	def minxorpair(self, N, arr):
		b = 999999
		arr.sort()
		for i in range(0, N - 1):
			c = arr[i] ^ arr[i + 1]
			b = min(b, c)
		return b


class Solution:

	def minxorpair(self, N, arr):
		mxp = arr[0] ^ arr[1]
		arr.sort()
		for i in range(0, N - 1):
			if arr[i] ^ arr[i + 1] < mxp:
				mxp = arr[i] ^ arr[i + 1]
		return mxp


class Solution:

	def minxorpair(self, N, arr):
		mini = 99999999999
		arr.sort()
		for i in range(N - 1):
			xor = arr[i] ^ arr[i + 1]
			if xor < mini:
				mini = xor
		return mini


class Solution:

	def minxorpair(self, N, arr):
		arr.sort()
		minXOR = float('inf')
		currXOR = 0
		for i in range(N - 1):
			currXOR = arr[i] ^ arr[i + 1]
			minXOR = min(minXOR, currXOR)
		return minXOR


class Solution:

	def minxorpair(self, N, arr):
		arr.sort()
		ans = arr[-1]
		for i in range(N - 1):
			ans = min(arr[i] ^ arr[i + 1], ans)
		return ans


class Solution:

	def minxorpair(self, N, arr):
		out = []
		for i in range(N):
			val = arr[i - 1] ^ arr[i]
			out.append(val)
		return min(out)


class Solution:

	def minxorpair(self, n, arr):
		mini = 9999
		arr.sort()
		for i in range(n - 1):
			ans = arr[i] ^ arr[i + 1]
			if ans < mini:
				mini = ans
		return mini


class Solution:

	def minxorpair(self, N, arr):
		arr.sort()
		l = []
		for i in range(N - 1):
			l.append(arr[i] ^ arr[i + 1])
		return min(l)


class Solution:

	def minxorpair(self, N, arr):
		dpMax = [0] * N
		dpMin = [0] * N
		dpMax[-1] = arr[-1]
		dpMin[-1] = arr[-1]
		currMin = float('inf')
		for i in range(N - 2, -1, -1):
			dpMax[i] = max(arr[i], dpMax[i + 1])
			dpMin[i] = min(arr[i], dpMin[i + 1])
		ans = float('inf')
		for i in range(N - 1):
			ans = min(ans, arr[i] ^ dpMax[i + 1], arr[i] ^ dpMin[i + 1])
		return ans


class Solution:

	def minxorpair(self, N, arr):
		arr.sort()
		min_value = int(1000000000.0)
		running_value = 0
		for i in range(len(arr) - 1):
			first = arr[i]
			second = arr[i + 1]
			running_value = first ^ second
			min_value = min(min_value, running_value)
		return min_value


class Node:

	def __init__(self):
		self.link = [None] * 2

class Trie:

	def __init__(self):
		self.root = Node()

	def insert(self, key):
		temp = self.root
		for i in range(31, -1, -1):
			curr = key >> i & 1
			if temp.link[curr] is None:
				temp.link[curr] = Node()
			temp = temp.link[curr]

	def xorval(self, val):
		ans = 0
		temp = self.root
		for i in range(31, -1, -1):
			t = val >> i & 1
			if temp.link[t] != None:
				temp = temp.link[t]
			elif temp.link[1 - t] != None:
				ans += 1 << i
				temp = temp.link[1 - t]
		return ans

class Solution:

	def minxorpair(self, N, arr):
		root = Trie()
		ans = 1000000000000.0
		root.insert(arr[0])
		for i in range(1, N):
			ans = min(ans, root.xorval(arr[i]))
			root.insert(arr[i])
		return ans


class Solution:

	def minxorpair(self, N, arr):
		arr.sort()
		xor1 = 1000000000000
		for i in range(0, N - 1):
			xor2 = arr[i] ^ arr[i + 1]
			if xor2 < xor1:
				xor1 = xor2
		return xor1


import sys

class Solution:

	def minxorpair(self, n, arr):
		arr.sort()
		minXor = int(sys.float_info.max)
		val = 0
		for i in range(0, n - 1):
			val = arr[i] ^ arr[i + 1]
			minXor = min(minXor, val)
		return minXor


class Solution:

	def minxorpair(self, N, arr):
		arr = sorted(arr)
		minn = 10000000
		for i in range(1, N):
			minn = min(minn, arr[i] ^ arr[i - 1])
		return minn


class Solution:

	def minxorpair(self, N, arr):
		minn = 100000.0 + 1
		arr.sort()
		for i in range(N - 1):
			minn = min(minn, arr[i] ^ arr[i + 1])
		return minn


import collections

class Node:

	def __init__(self):
		self.children = [None, None]
		self.val = None

class Solution:

	def insert(self, n):
		cur = self.root
		for i in range(32)[::-1]:
			bit = n >> i & 1
			if cur.children[bit] is None:
				cur.children[bit] = Node()
			cur = cur.children[bit]
		cur.val = n

	def find(self, n):
		cur = self.root
		for i in range(32)[::-1]:
			bit = n >> i & 1
			if cur.children[bit] is not None:
				cur = cur.children[bit]
			elif cur.children[1 - bit] is not None:
				cur = cur.children[1 - bit]
		return cur.val ^ n

	def minxorpair(self, N, arr):
		self.root = Node()
		self.insert(arr[0])
		res = 2 ** 30
		for n in arr[1:]:
			res = min(res, self.find(n))
			self.insert(n)
		return res


import math

class TrieNode:

	def __init__(self):
		self.links = [None] * 2

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, key):
		curr = self.root
		for ele in key:
			if not curr.links[ord(str(ele)) - ord('0')]:
				curr.links[ord(str(ele)) - ord('0')] = TrieNode()
			curr = curr.links[ord(str(ele)) - ord('0')]

	def checkXOR(self, key):
		temp = []
		curr = self.root
		for ele in key:
			if curr.links[ord(str(ele)) - ord('0')]:
				curr = curr.links[ord(str(ele)) - ord('0')]
				temp += [0]
			else:
				curr = curr.links[1 - (ord(str(ele)) - ord('0'))]
				temp += [1]
		return temp

class Solution:

	def minxorpair(self, N, arr):

		def decimalToBinary(num, digit):
			ans = [0] * digit
			i = digit - 1
			while num:
				if num % 2:
					ans[i] = 1
				else:
					ans[i] = 0
				i -= 1
				num = num // 2
			return ans

		def binaryToDecimal(arr, digit):
			ans = 0
			j = 0
			for i in range(digit - 1, -1, -1):
				if arr[i] == 1:
					ans += 2 ** j
				j += 1
			return ans
		t = Trie()
		ans = 10 ** 9 + 7
		flag = 1
		mx = max(arr)
		digit = int(math.log(mx, 2) + 1)
		for ele in arr:
			new = decimalToBinary(ele, digit)
			if flag:
				flag = 0
			else:
				got = t.checkXOR(new)
				got = binaryToDecimal(got, digit)
				ans = min(ans, got)
			t.insert(new)
		return ans


class Solution:

	def minxorpair(self, N, arr):
		arr.sort()
		min1 = 1000
		for i in range(N - 1):
			x = arr[i] ^ arr[i + 1]
			if x < min1:
				min1 = x
			if min1 == 0:
				return 0
		return min1


class Solution:

	def minxorpair(self, N, arr):
		d = {}

		def make(num):
			curr = d
			for i in range(31, -1, -1):
				if num & 1 << i:
					if 1 not in curr:
						curr[1] = {}
					curr = curr[1]
				else:
					if 0 not in curr:
						curr[0] = {}
					curr = curr[0]
			return

		def fmin(num):
			curr = d
			s = 0
			for i in range(31, -1, -1):
				if num & 1 << i:
					if 1 in curr:
						curr = curr[1]
					else:
						s += 2 ** i
						if 0 in curr:
							curr = curr[0]
				elif 0 in curr:
					curr = curr[0]
				else:
					s += 2 ** i
					if 1 in curr:
						curr = curr[1]
			return s
		mini = 1000000.0
		make(arr[0])
		for i in arr[1:]:
			mini = min(mini, fmin(i))
			make(i)
		return mini


class Solution:

	def minxorpair(self, N, arr):
		arr.sort()
		mini = 10 ** 9
		Le = min(N, 100)
		for i in range(Le):
			for j in range(i):
				if arr[i] ^ arr[j] < mini:
					mini = arr[i] ^ arr[j]
		return mini


from numpy import inf

class Solution:

	def minxorpair(self, N, arr):
		nums = arr
		s = []
		mLen = len(bin(max(nums))[2:])
		list(map(lambda x: s.append(bin(x)[2:].zfill(mLen)), nums))
		t = [i for i in range(len(s))]
		self.min = float(inf)

		def findMinimum(tmp, i):
			if len(tmp) < 2:
				return
			if len(tmp) == 2 or i >= len(s[tmp[0]]):
				self.min = min(self.min, nums[tmp[0]] ^ nums[tmp[1]])
				return
			zeros = ones = []
			zeros = list(filter(lambda x: s[x][i] == '1', tmp))
			ones = list(filter(lambda x: s[x][i] == '0', tmp))
			findMinimum(zeros, i + 1)
			findMinimum(ones, i + 1)
		findMinimum(t, 0)
		return self.min


from itertools import combinations

class Solution:

	def minxorpair(self, N, arr):
		arr.sort()
		min = 999999
		for i in range(1, N):
			if arr[i] ^ arr[i - 1] < min:
				min = arr[i] ^ arr[i - 1]
		return min


SIZE = 16

class TrieNode:

	def __init__(self):
		self.children = [None] * 2
		self.value = 0

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, N):
		curr = self.root
		for i in range(SIZE, -1, -1):
			bit = 1 if N & 1 << i else 0
			if curr.children[bit] is None:
				curr.children[bit] = TrieNode()
			curr = curr.children[bit]
		curr.value = N

	def search(self, N):
		curr = self.root
		for i in range(SIZE, -1, -1):
			bit = N >> i & 1
			if curr.children[bit] != None:
				curr = curr.children[bit]
			else:
				curr = curr.children[bit ^ 1]
		return curr.value ^ N

class Solution:

	def minxorpair(self, N, A):
		ans = 1000000.0
		trie = Trie()
		trie.insert(A[0])
		for i in range(1, N):
			ans = min(ans, trie.search(A[i]))
			trie.insert(A[i])
		return ans


import sys

class Solution:

	def minxorpair(self, N, arr):
		arr.sort()
		min_xor = int(sys.float_info.max)
		cur_xor = 0
		for i in range(0, N - 1):
			cur_xor = arr[i] ^ arr[i + 1]
			min_xor = min(cur_xor, min_xor)
		return min_xor


class Trie:

	def __init__(self):
		self.children = {}

class Solution:

	def minxorpair(self, N, arr):
		minXor = 100001
		arr.sort()
		for i in range(N - 1):
			minXor = min(minXor, arr[i] ^ arr[i + 1])
		return minXor


class Solution:

	def minxorpair(self, N, arr):
		m = 10 ** 31
		arr.sort()
		for i in range(N - 1):
			a = arr[i] ^ arr[i + 1]
			m = min(m, a)
		return m


class Solution:

	def minxorpair(self, N, A):
		trie = {}
		ans = float('inf')
		for (j, num) in enumerate(A):
			if j > 0:
				trie1 = trie
				val = 0
				for i in range(29, -1, -1):
					x = num >> i & 1
					if x in trie1:
						trie1 = trie1[x]
					else:
						trie1 = trie1[1 - x]
				ans = min(ans, num ^ trie1['val'])
			trie1 = trie
			for i in range(29, -1, -1):
				x = num >> i & 1
				if x not in trie1:
					trie1[x] = {}
				trie1 = trie1[x]
			trie1['val'] = num
		return ans


class Solution:

	def minxorpair(self, N, A):
		A.sort()
		ans = float('inf')
		for i in range(len(A) - 1):
			ans = min(ans, A[i] ^ A[i + 1])
		return ans


class Solution:

	def minxorpair(self, N, arr):
		min_xor = float('infinity')
		arr.sort()
		for i in range(N - 1):
			xor = arr[i] ^ arr[i + 1]
			min_xor = min(min_xor, xor)
		return min_xor


class Solution:

	def minxorpair(self, N, arr):
		re = 1000000
		arr.sort()
		for i in range(N - 1):
			re = min(re, arr[i] ^ arr[i + 1])
		return re


class Solution:

	def minxorpair(self, N, arr):
		arr = sorted(arr)
		ans = 10 ** 9 + 7
		for i in range(N - 1):
			ans = min(ans, arr[i] ^ arr[i + 1])
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = input().split()
		for itr in range(N):
			arr[itr] = int(arr[itr])
		ob = Solution()
		print(ob.minxorpair(N, arr))


class Solution:

	def minxorpair(self, N, arr):
		min = 9999
		arr.sort()
		for i in range(N - 1):
			if arr[i] ^ arr[i + 1] < min:
				min = arr[i] ^ arr[i + 1]
		return min
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = input().split()
		for itr in range(N):
			arr[itr] = int(arr[itr])
		ob = Solution()
		print(ob.minxorpair(N, arr))


import sys

class Solution:

	def minxorpair(self, N, arr):
		arr.sort()
		minXor = int(sys.float_info.max)
		val = 0
		for i in range(0, N - 1):
			val = arr[i] ^ arr[i + 1]
			minXor = min(minXor, val)
		return minXor
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = input().split()
		for itr in range(N):
			arr[itr] = int(arr[itr])
		ob = Solution()
		print(ob.minxorpair(N, arr))


class Trie:

	def __init__(self):
		self.children = {}
		self.val = -1

	def insert(self, num):
		cur = self
		for i in range(31, -1, -1):
			bit = 1 & num >> i
			if bit not in cur.children:
				cur.children[bit] = Trie()
			cur = cur.children[bit]
		cur.val = num

class Solution:

	def minxorpair(self, N, arr):
		nums = arr
		n = len(nums)
		root = Trie()
		root.insert(nums[0])
		res = float('inf')
		for k in range(1, n):
			cur = root
			max_no = 0
			for i in range(31, -1, -1):
				bit = 1 if nums[k] & 1 << i else 0
				if bit in cur.children:
					cur = cur.children[bit]
				else:
					max_no = max_no | 1 << i
					cur = cur.children[1 - bit]
			root.insert(nums[k])
			res = min(res, max_no)
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = input().split()
		for itr in range(N):
			arr[itr] = int(arr[itr])
		ob = Solution()
		print(ob.minxorpair(N, arr))


class Solution:

	def minxorpair(self, N, A):
		MAX_LENGTH = 17

		def traverse(s, b):
			assert len(s) >= 2
			if b == MAX_LENGTH:
				return 0
			grp0 = []
			lgrp0 = 0
			grp1 = []
			lgrp1 = 0
			for i in s:
				if A[i] >> MAX_LENGTH - b - 1 & 1:
					grp1.append(i)
					lgrp1 += 1
				else:
					grp0.append(i)
					lgrp0 += 1
			if lgrp0 >= 2 and lgrp1 >= 2:
				return min(traverse(grp0, b + 1), traverse(grp1, b + 1))
			elif lgrp0 >= 2:
				return traverse(grp0, b + 1)
			elif lgrp1 >= 2:
				return traverse(grp1, b + 1)
			else:
				return A[grp0[0]] ^ A[grp1[0]]
		return traverse(list(range(N)), 0)


import math

class Trie:

	def __init__(self):
		self.child = {}
		self.c = 0

	def add(self, word):
		cur = self
		for w in word:
			if w not in cur.child:
				cur.child[w] = Trie()
			cur = cur.child[w]
			cur.c += 1

	def search(self, word, msb):
		cur = self
		num = 0
		flag = 1
		for w in word:
			if w not in cur.child:
				w = str(1 - int(w))
				flag = 0
			elif flag and cur.child[w].c < 2:
				w = str(1 - int(w))
				flag = 0
			if w == '1':
				num |= 1 << msb
			cur = cur.child[w]
			msb -= 1
		return num

class Solution:

	def minxorpair(self, N, nums):
		msb = 0
		bits = []
		for i in nums:
			bits.append(bin(i)[2:])
			if i != 0:
				msb = max(msb, int(math.log2(i)))
		root = Trie()
		for b in bits:
			root.add('0' * (msb + 1 - len(b)) + b)
		ans = float('inf')
		p = (1 << msb + 1) - 1
		for i in range(N):
			b = bits[i]
			b = '0' * (msb + 1 - len(b)) + b
			b = root.search(b, msb)
			ans = min(ans, nums[i] ^ b)
		return ans


class Solution:

	def minxorpair(self, N, arr):
		arr.sort()
		m = 85500
		for i in range(N - 1):
			n = arr[i] ^ arr[i + 1]
			if n < m:
				m = n
		return m


import sys

class TrieNode:

	def __init__(self):
		self.children = dict()
		self.value = -1

class Solution:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, val):
		curr = self.root
		for i in range(31, -1, -1):
			digit = 1 if val & 1 << i else 0
			if digit not in curr.children:
				curr.children[digit] = TrieNode()
			curr = curr.children[digit]
		curr.value = val

	def search(self, num):
		curr = self.root
		for i in range(31, -1, -1):
			digit = 1 if num & 1 << i else 0
			if digit in curr.children:
				curr = curr.children[digit]
			elif (not digit) in curr.children:
				curr = curr.children[not digit]
		return curr.value ^ num

	def minxorpair(self, N, arr):
		min_val = sys.maxsize
		self.insert(arr[0])
		for i in range(1, N):
			min_val = min(min_val, self.search(arr[i]))
			self.insert(arr[i])
		return min_val


class Solution:

	def minxorpair(self, N, arr):
		arr.sort()
		m = arr[0] ^ arr[1]
		for i in range(1, N - 1):
			z = arr[i] ^ arr[i + 1]
			if z < m:
				m = z
		return m


import sys

class Solution:

	def minxorpair(self, N, arr):
		arr.sort()
		minxor = int(sys.float_info.max)
		val = 0
		for i in range(N - 1):
			val = arr[i] ^ arr[i + 1]
			minxor = min(minxor, val)
		return minxor


class Solution:

	def minxorpair(self, N, arr):
		minimum = float('inf')

		def minxor(arr, i):
			if len(arr) < 2:
				return float('inf')
			if len(arr) == 2 or i == 0:
				return arr[0] ^ arr[1]
			(a1, a2) = ([], [])
			for a in arr:
				if a & 1 << i:
					a1.append(a)
				else:
					a2.append(a)
			return min(minxor(a1, i - 1), minxor(a2, i - 1))
		return minxor(arr, 31)


class TrieNode:

	def __init__(self):
		self.children = dict()

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, key):
		current = self.root
		for char in key:
			if char not in current.children:
				current.children[char] = TrieNode()
			current = current.children[char]

	def minXor(self, bin_num):
		current = self.root
		res = ''
		for bit in bin_num:
			if bit in current.children:
				res += bit
				current = current.children[bit]
			else:
				oppBit = self.getOppBit(bit)
				res += oppBit
				current = current.children[oppBit]
		return int(res, 2) ^ int(bin_num, 2)

	def getOppBit(self, bit):
		if bit == '0':
			return '1'
		return '0'

class Solution:

	def minxorpair(self, N, arr):
		trie = Trie()
		bin_num_0 = bin(arr[0])[2:].zfill(32)
		trie.insert(bin_num_0)
		minxor = 9999999
		for i in range(1, len(arr)):
			bin_num = bin(arr[i])[2:].zfill(32)
			minxor = min(minxor, trie.minXor(bin_num))
			trie.insert(bin_num)
		return minxor


class Node:

	def __init__(self):
		self.chi = {}
		self.val = 0

class trie:

	def __init__(self):
		self.root = Node()

	def add(self, val):
		t = self.root
		for i in range(31, -1, -1):
			t1 = val >> i & 1
			if t.chi.get(t1) is None:
				t.chi[t1] = Node()
			t = t.chi[t1]
		t.val = val

	def xor(self, val):
		t = self.root
		for i in range(31, -1, -1):
			t1 = val >> i & 1
			if t.chi.get(t1):
				t = t.chi[t1]
			else:
				t = t.chi[1 - t1]
		return t.val ^ val

class Solution:

	def minxorpair(self, n, arr):
		tr = trie()
		tr.add(arr[0])
		m = float('inf')
		for i in range(1, n):
			m = min(m, tr.xor(arr[i]))
			tr.add(arr[i])
		return m


class TrieNode:

	def __init__(self):
		self.links = [None, None]
		self.value = None

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, num):
		node = self.root
		for i in range(31, -1, -1):
			bit = num >> i & 1
			if node.links[bit]:
				node = node.links[bit]
			else:
				node.links[bit] = TrieNode()
				node = node.links[bit]
		node.value = num

	def findMax(self, num):
		maxnum = 0
		node = self.root
		for i in range(31, -1, -1):
			bit = num >> 1 & 1
			if node.links[1 - bit]:
				node = node.links[1 - bit]
				maxNum = maxNum | i << 1
			else:
				node = node.links[1 ^ bit]
		return maxNum

	def findMin(self, num):
		minNum = 0
		node = self.root
		for i in range(31, -1, -1):
			bit = num >> i & 1
			if node.links[bit] is not None:
				node = node.links[bit]
			elif node.links[1 - bit] is not None:
				node = node.links[1 - bit]
		return node.value ^ num

class Solution:

	def minxorpair(self, N, arr):
		TR = Trie()
		TR.insert(arr[0])
		ans = 1000000007
		for i in range(1, N):
			ans = min(ans, TR.findMin(arr[i]))
			TR.insert(arr[i])
		return ans


class Trie:

	def __init__(self):
		self.children = [None] * 2
		self.isEnd = False
		self.count = [0] * 2

class TrieNode:

	def __init__(self):
		self.root = Trie()

	def insert(self, st):
		curr = self.root
		for i in range(31, -1, -1):
			index = st >> i & 1
			if curr.children[index] == None:
				curr.children[index] = Trie()
			curr = curr.children[index]
			curr.count[index] += 1
		curr.isEnd = False

	def searchMinPair(self, st):
		curr = self.root
		value = 0
		power = 2 ** 31
		xor_val = 0
		for i in range(31, -1, -1):
			index = st >> i & 1
			if curr.children[index] != None:
				curr = curr.children[index]
			else:
				index = 1 - index
				curr = curr.children[index]
				xor_val += power
			power = power // 2
		return xor_val

class Solution:

	def minxorpair(self, N, arr):
		trienode = TrieNode()
		trienode.insert(arr[0])
		min_xor = 2 ** 32
		for i in range(1, N):
			st = arr[i]
			xor_val = trienode.searchMinPair(st)
			trienode.insert(st)
			if xor_val < min_xor:
				min_xor = xor_val
		return min_xor


class Solution:

	def minxorpair(self, n, arr):
		arr = sorted(arr)
		ans = 1000000000
		for i in range(0, n - 1):
			ans = min(ans, arr[i] ^ arr[i + 1])
		return ans


class TrieNode(object):

	def __init__(self):
		self.value = 0
		self.child = [None, None]

class MinXOR(object):
	INT_SIZE = 32

	def get_node(self):
		return TrieNode()

	def insert(self, root, key):
		temp = root
		for i in range(self.INT_SIZE - 1, -1, -1):
			bit = 1 if key & 1 << i else 0
			if temp.child[bit] == None:
				temp.child[bit] = self.get_node()
			temp = temp.child[bit]
		temp.value = key

	def minXORCalc(self, root, key):
		temp = root
		for i in range(self.INT_SIZE - 1, -1, -1):
			bit = 1 if key & 1 << i else 0
			if temp.child[bit] != None:
				temp = temp.child[bit]
			elif temp.child[1 - bit] != None:
				temp = temp.child[1 - bit]
		return temp.value ^ key

	def minXORPair(self, arr, N):
		min_xor = 2 ** 33
		root = self.get_node()
		self.insert(root, arr[0])
		for i in range(1, N):
			min_xor = min(min_xor, self.minXORCalc(root, arr[i]))
			self.insert(root, arr[i])
		return min_xor

class Solution:

	def minxorpair(self, N, arr):
		mx = MinXOR()
		return mx.minXORPair(arr, N)