Pattern Guide
XOR Basis (Linear Basis)
"Gaussian elimination on XOR. Find max XOR, k-th XOR value, XOR spanning set."
A linear basis (XOR basis) is a minimal set of numbers whose XOR combinations span all possible XOR values of the original set. Built via Gaussian elimination: insert numbers one by one, reducing by pivot positions. Supports: maximum XOR subset sum, k-th smallest XOR value, count of distinct XOR values. Essential for problems asking for max/min XOR over all subsets.
Problems you can solve with this pattern
4 problems · click any to start solving
class XorBasis {
constructor() { this.basis = new Array(30).fill(0); this.size = 0; }
insert(x) {
for (let i = 29; i >= 0; i--) {
if (!((x >> i) & 1)) continue; // bit i not set
if (!this.basis[i]) { this.basis[i] = x; this.size++; return true; }
x ^= this.basis[i]; // reduce by existing basis element
}
return false; // x was 0 after reduction → linearly dependent
}
// Maximum XOR achievable using any subset
maxXor() {
let res = 0;
for (let i = 29; i >= 0; i--) res = Math.max(res, res ^ this.basis[i]);
return res;
}
// Minimum non-zero XOR achievable (lowest bit basis element)
minXor() {
for (let i = 0; i <= 29; i++) if (this.basis[i]) return this.basis[i];
return 0;
}
// k-th smallest XOR value (1-indexed, must reduce basis to row echelon form first)
// First reduce: for each i from low to high, reduce higher basis elements
kthSmallest(k) {
const reduced = [];
for (let i = 0; i <= 29; i++) {
if (!this.basis[i]) continue;
let v = this.basis[i];
for (let j = i - 1; j >= 0; j--) if ((v >> j) & 1) v ^= this.basis[j];
reduced.push(v);
}
// Now reduced[i] corresponds to bit i of k
let res = 0;
for (let i = 0; i < reduced.length; i++) if ((k >> i) & 1) res ^= reduced[i];
return res;
}
}An XOR linear basis stores at most 30-60 numbers (one per bit) such that any XOR combination of the original array equals some XOR combination of basis elements. Insert: for each number, try to reduce it using existing basis elements from high bit to low. If it reduces to 0, it's linearly dependent (already representable). If not, add it at its highest bit position.
class XorBasis {
constructor() { this.basis = new Array(30).fill(0); this.size = 0; }
insert(x) {
for (let i = 29; i >= 0; i--) {
if (!((x >> i) & 1)) continue; // bit i not set
if (!this.basis[i]) { this.basis[i] = x; this.size++; return true; }
x ^= this.basis[i]; // reduce by existing basis element
}
return false; // x was 0 after reduction → linearly dependent
}
// Maximum XOR achievable using any subset
maxXor() {
let res = 0;
for (let i = 29; i >= 0; i--) res = Math.max(res, res ^ this.basis[i]);
return res;
}
// Minimum non-zero XOR achievable (lowest bit basis element)
minXor() {
for (let i = 0; i <= 29; i++) if (this.basis[i]) return this.basis[i];
return 0;
}
// k-th smallest XOR value (1-indexed, must reduce basis to row echelon form first)
// First reduce: for each i from low to high, reduce higher basis elements
kthSmallest(k) {
const reduced = [];
for (let i = 0; i <= 29; i++) {
if (!this.basis[i]) continue;
let v = this.basis[i];
for (let j = i - 1; j >= 0; j--) if ((v >> j) & 1) v ^= this.basis[j];
reduced.push(v);
}
// Now reduced[i] corresponds to bit i of k
let res = 0;
for (let i = 0; i < reduced.length; i++) if ((k >> i) & 1) res ^= reduced[i];
return res;
}
}- At most 30 elements (one per bit for 32-bit integers)
- Spans the same XOR closure as the original set
- Any number representable as XOR of subset iff it reduces to 0 during insertion
Max XOR algorithm: Greedily try to set each bit from high to low: if XOR-ing with basis element increases current result, do it.
Count distinct XOR values: 2^(basis.size) distinct values possible (including 0).
Merge two bases: Insert all elements of one into the other — O(30²) per merge.
Online vs offline: Basis supports online insertions. For "max XOR with elements ≤ limit," sort and insert offline.