# Hacker Rank — Maximizing XOR

Problem: https://www.hackerrank.com/challenges/maximizing-xor My solution:

The solution ended up being more condensed than I had hoped. My original solution resembled:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

function createPairs(l, r) {
var result = [];
for (var i = l; i <= r; i++) {
for (var j = l; j <= r ; j++) {
if (i <= j) {
result.push([i, j]);
}
}
}
return result;
}
function maxXor(l, r) {
var l = parseInt(l, 10), r = parseInt(r, 10);
var pairs = createPairs(l, r)
var xors = pairs.map(function(pair) {
return pair[0] ^ pair[1];
});
return Math.max.apply(Math, xors);
}

I’ll walk through my original solution first. `maxXor`

takes two Strings of Numbers that ranged from \(1 ≤ L ≤ R ≤ 10^{3}\). The function must return the maximal values of A xor B given, \(L ≤ A ≤ B ≤ R\). First, we need the Numbers out of the Strings (line 14). Next, delegate to creating all possible pairs of A and B given the constraints of the problem. The function `createPairs`

runs a two dimensional loop that returns an Array of Arrays (the inner Array representing a ‘pair’). Next, xor all of the pairs, obtaining a new Array of Numbers. Next, courtesy of John Resig’s advice find the max Number of the Array.

Unfortunately, `Max.apply`

yields a `RangeError: Maximum call stack size exceeded`

for `l=1, r=1000`

. Surprisingly, `Function.prototype.apply`

can only receive an array of limited length and since the result of `createPairs(1, 1000)`

is quite large, yet well within the problem constraints, we’ll need to re-think finding the max approach. We could either find a better way to determine the max value of an Array of values, or we could keep a running value of the max. A quick glance over maxXor told me that runtime could be trivially optimized from it’s current \(O(3nm)\) to a semi-palatable \(O(nm)\) if we did maintained everything in the loops. Since this was still pretty simple, I went with it. If this were production code, and optimization was not yet a concern, I’d consider organizing the code how I’d originally done for readability.