We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Maximum Xor
  2. Discussions

Maximum Xor

  • foxstonks
     + 0 comments

    Most useful comment without giving an exact solution, thanks @dcgibbons !

    Based on this here is my (hopefully clear) javascript solution (passing all tests):

    const nodeOf = bit => ({ bit, '0': null, '1': null });

const opposite = bit => bit === '1' ? '0' : '1';

const toBinary = number => number.toString(2).padStart(32, 0);

const toDecimal = binary => parseInt(binary, 2);

function insert(node, binary) {
  const head = binary[0];
  const tail = binary.substring(1);

  if (!node[head]) {
    node[head] = nodeOf(head);
  }

  if (tail) {
    insert(node[head], tail);
  }
}

function buildTrie(numbers) {
  const root = nodeOf(null);

  numbers.forEach(value => insert(root, toBinary(value)));

  return root;
}

function findBest(node, binary) {
  const head = binary[0];
  const tail = binary.substring(1);

  // the best is the opposite (xor -> 1) at each stage but we move forward until we can anyway
  const next = node[opposite(head)] || node[head];

  if (next) {
    return next.bit + findBest(next, tail);
  }

  return '';
}

function maxXor(arr, queries) {
  const root = buildTrie(arr);

  return queries.map(query => query ^ toDecimal(findBest(root, toBinary(query))));
}