XOR Basis / Linear Basis

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;
    }
}