Colin Chang

# 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:

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.