Funcia
Lv.3bit-manipulationtrie

Maximum XOR of Two Numbers

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Return the maximum of nums[i] XOR nums[j] over indices i ≠ j.

Examples

numsresult
[3, 10, 5, 25, 2, 8]28
[7, 7]0
[0, 1073741823]1073741823

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(nums: int[]) → int

Constraints

  • 2≤2 \le nums.length ≤200,000\le 200{,}000, 0≤0 \le nums[i] <230< 2^{30}

Expected complexity

Time
O(N log C)
Space
O(N log C)

Examples

numsExpected
[3,10,5,25,2,8]28
[7,7]0
[0,1073741823]1073741823

Hint

Hint

Higher bits dominate. Insert the numbers into a binary trie (bit 29 down to 0) and, for each x, walk towards the opposite bit whenever possible; or fix the answer bit by bit with a hash set of prefixes. Checking all pairs is O(N2)O(N^2).

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)246 msestimated
C++ (GCC, gnu++23)246 msderived
Python 3.131000 msderived
Java 251842 msderived
Kotlin 2.4 (JVM)1492 msestimated
C# 14 (.NET 10)1492 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness408verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.