Maximizing XORs - riemann79/hello-world GitHub Wiki

Find the maximum number obtained by XORing all pairs of numbers in the range [L, R]. See https://www.hackerrank.com/challenges/maximizing-xor

The basic approach consists of performing all the XORs and updating the maximum.

function maxXor(l, r) {

    var max = 0;
    
    for(var i = l; i <= r; i++) {
        for(var j = i + 1; j <= r; j++) {
            var xor = i ^ j;
            
            if(xor > max) {
                max = xor;
            }
        }
    }
    
    return max;
}

Improvement based on exiting the inner loop when a local maximum has been found.

function maxXor(l, r) {

    var last = 0;
    var max = 0;
    
    for(var i = l; i <= r; i++) {
        for(var j = i + 1; j <= r; j++) {
            var xor = i ^ j;
            
            if(xor < last) {
                // When XOR starts decreasing, local max
                // has been found.
                last = 0;
                break;
            }
            
            last = xor;
            
            if(xor > max) {
                max = xor;
            }
        }
    }
    
    return max;
}

Often, an important improvement can be found by performing a numerical analysis on the problem. The intuition that XORs reach a "local maximum" can be formalised by noting that only a certain number of digits can be turned into 1 after a XOR. By comparing the binary representations of L and R, we can find the maximum number n of digits that can be turned into 1 by XORing numbers in [L, R]. From this observation follows that the maximum is 2^n - 1.

function maxXor(l, r) {
    return Math.pow(2, Math.ceil(log2(l ^ r))) - 1;
}