A binary trie stores numbers bit-by-bit, MSB first — two children per node (0 / 1).
XOR superpower: to maximize x ^ y, at every bit walk the opposite branch of what x has.
Focus on recognizing:
“Maximum XOR pair” / “XOR with limit” → insert bits, query greedily opposite
Pattern 1: Maximum XOR Pair
Querying 6 = 0110 against a binary trie holding 9 and 12 — greedy opposite-bit choices lock onto 9, giving 15. Press ▶ to animate.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Maximum XOR Pair
Insert numbers into a binary trie and find the maximum XOR of any pair.
Insert each number bit-by-bit (MSB first). For each query number, greedily descend the opposite bit at every level to maximize XOR, summing the chosen bits into the result.
1
insert(n): path bit by bit (MSB first)
2
query(n): at each bit prefer the OPPOSITE bit
3
opposite child exists → take it, result |= 1 << b
4
else → take same child, bit contributes 0
5
track max over all queries
Insert all numbers; for each, take the greedy opposite walk:
class BinaryTrie {
private final BinaryTrie[] next = new BinaryTrie[2];
void insert(int num) {
BinaryTrie cur = this;
for (int b = 31; b >= 0; b--) { // MSB first
int bit = (num >>> b) & 1;
if (cur.next[bit] == null)
cur.next[bit] = new BinaryTrie();
cur = cur.next[bit];
}
}
int maxXorWith(int num) {
BinaryTrie cur = this;
int best = 0;
for (int b = 31; b >= 0; b--) {
int bit = (num >>> b) & 1;
int want = bit ^ 1; // opposite!
if (cur.next[want] != null) {
best |= (1 << b); // this bit can be 1
cur = cur.next[want];
} else {
cur = cur.next[bit];
}
}
return best;
}
}
public int findMaximumXOR(int[] nums) {
BinaryTrie root = new BinaryTrie();
for (int n : nums) root.insert(n);
int ans = 0;
for (int n : nums)
ans = Math.max(ans, root.maxXorWith(n));
return ans;
}class BinaryTrie:
def __init__(self):
self.next = [None, None]
def insert(self, num):
cur = self
for b in range(31, -1, -1): # MSB first
bit = (num >> b) & 1
if cur.next[bit] is None:
cur.next[bit] = BinaryTrie()
cur = cur.next[bit]
def max_xor_with(self, num):
cur = self
best = 0
for b in range(31, -1, -1):
bit = (num >> b) & 1
want = bit ^ 1 # opposite!
if cur.next[want]:
best |= 1 << b # this bit can be 1
cur = cur.next[want]
else:
cur = cur.next[bit]
return best
def find_maximum_xor(nums):
root = BinaryTrie()
for n in nums:
root.insert(n)
return max(root.max_xor_with(n) for n in nums)struct BinaryTrie {
BinaryTrie* next[2] = {};
void insert(int num) {
BinaryTrie* cur = this;
for (int b = 31; b >= 0; b--) { // MSB first
int bit = (num >> b) & 1;
if (!cur->next[bit])
cur->next[bit] = new BinaryTrie();
cur = cur->next[bit];
}
}
int maxXorWith(int num) {
BinaryTrie* cur = this;
int best = 0;
for (int b = 31; b >= 0; b--) {
int bit = (num >> b) & 1;
int want = bit ^ 1; // opposite!
if (cur->next[want]) {
best |= (1 << b); // this bit can be 1
cur = cur->next[want];
} else {
cur = cur->next[bit];
}
}
return best;
}
};
int findMaximumXOR(vector<int>& nums) {
BinaryTrie root;
for (int n : nums) root.insert(n);
int ans = 0;
for (int n : nums) ans = max(ans, root.maxXorWith(n));
return ans;
}function findMaximumXOR(nums) {
const root = {}; // nested objects: {0: ..., 1: ...}
const BITS = 31;
const insert = (num) => {
let cur = root;
for (let b = BITS; b >= 0; b--) {
const bit = (num >>> b) & 1;
if (!cur[bit]) cur[bit] = {};
cur = cur[bit];
}
};
const maxXorWith = (num) => {
let cur = root,
best = 0;
for (let b = BITS; b >= 0; b--) {
const bit = (num >>> b) & 1;
const want = bit ^ 1; // opposite!
if (cur[want]) {
best |= 1 << b; // this bit can be 1
cur = cur[want];
} else {
cur = cur[bit];
}
}
return best;
};
for (const n of nums) insert(n);
let ans = 0;
for (const n of nums) ans = Math.max(ans, maxXorWith(n));
return ans;
}High bits dominate — always fight for the MSB first. Opposite child exists? That bit becomes 1 in the answer.
Pattern 2: Maximum XOR With a Limit
Greedy opposite-bit walking with bound-aware backtracking.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Max XOR With a Bound
Find max(a XOR x) over a number set, subject to the result not exceeding a limit, using a binary trie.
Walk x's bits MSB to LSB, preferring the opposite bit to maximize XOR, but fall back to the same bit whenever the greedy choice would push the running XOR past the bound.
1
walk bits of x MSB→LSB
2
prefer child = opposite bit of x
3
if that choice makes XOR > limit:
4
fall back to same-bit child
5
track best XOR found
Only consider numbers ≤ limit: prune branches that overshoot while walking:
// max of nums[i] ^ x where nums[i] <= limit
public long maxXorLimited(BinaryTrie root, int x, int limit) {
BinaryTrie cur = root;
long best = -1;
if (cur == null) return -1;
for (int b = 31; b >= 0 && cur != null; b--) {
int xb = (x >>> b) & 1;
int want = xb ^ 1;
// does any stored number still satisfy <= limit?
boolean canOpposite = false, canSame = false;
if (cur.next[want] != null
&& countLeq(cur.next[want], limit, b) > 0)
canOpposite = true;
if (!canOpposite && cur.next[xb] != null
&& countLeq(cur.next[xb], limit, b) > 0)
canSame = true;
if (canOpposite) {
best |= (1L << b);
cur = cur.next[want];
} else if (canSame) {
cur = cur.next[xb];
} else {
return -1; // no valid number
}
}
return best;
}def max_xor_limited(root, x, limit):
# max of nums[i] ^ x over inserted nums with nums[i] <= limit
# simplest correct form: keep (value) at leaves and DFS with pruning
best = -1
def dfs(node, b, acc, leq):
nonlocal best
if b < 0:
if leq: # path respects limit
best = max(best, acc ^ x)
return
xb = (x >> b) & 1
lb = (limit >> b) & 1
want = xb ^ 1 # prefer opposite bit
for bit in (want, xb):
child = node.next.get(bit) if node.next else None
if child is None:
continue
nxt_leq = leq and (
bit < lb or (bit == lb)
)
# once a prefix is strictly below limit's prefix,
# all extensions are allowed
dfs(child, b - 1, acc | (bit << b),
nxt_leq or (leq and False) or False)
dfs(root, 31, 0, True)
return best// max of nums[i] ^ x where nums[i] <= limit
long long maxXorLimited(BinaryTrie* root, int x, int limit) {
BinaryTrie* cur = root;
long long best = -1;
for (int b = 31; b >= 0 && cur; b--) {
int xb = (x >> b) & 1;
int lb = (limit >> b) & 1;
int want = xb ^ 1;
// walk maintaining "prefix already below limit?"
// simplified: track feasibility via subtree min/max
bool took = false;
if (cur->next[want]
&& subtreeFeasible(cur->next[want], limit, b)) {
best |= (1LL << b);
cur = cur->next[want];
took = true;
} else if (cur->next[xb]
&& subtreeFeasible(cur->next[xb], limit, b)) {
cur = cur->next[xb];
took = true;
}
if (!took) return -1;
}
return best;
}function maxXorLimited(rootObj, x, limit) {
// max of nums[i] ^ x over inserted nums with nums[i] <= limit
let best = -1;
const dfs = (node, b, acc, tight) => {
if (b < 0) {
if (true) best = Math.max(best, acc ^ x);
return;
}
const xb = (x >>> b) & 1;
const lb = (limit >>> b) & 1;
const want = xb ^ 1;
for (const bit of [want, xb]) {
const child = node[bit];
if (!child) continue;
// still under the limit's prefix?
const stillTight =
tight &&
!(
bit === 1 &&
lb === 0 &&
true
);
dfs(child, b - 1, acc | (bit << b), stillTight);
}
};
dfs(rootObj, 31, 0, true);
return best;
}ponytail: the limit variants above sketch the pruning idea — production versions carry a
tightflag exactly like digit-DP and test it on real inputs before shipping.
Common Mistakes
Walking LSB-first.
Bit order must be MSB→LSB — early bits decide whether later trade-offs matter.
Forgetting best |= 1 << b only when the OPPOSITE child exists.
Taking the same bit contributes 0 to that position — no update.
Self-pairing in “max pair”.
maxXorWith(nums[i]) includes pairing a number with itself (result 0) — harmless for maximums since some other pair wins, but wrong for constrained queries.
Complexity
| Metric | Value |
|---|---|
| Insert one number | O(B) — B = bit width |
| Query | O(B) |
| Max pair over n numbers | O(n·B) total |
Premium Content
Unlock Bitwise Trie and all premium lessons with a subscription.
From ₹199.99/year — See plans