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

  • dcgibbons
     + 10 comments

    This was a fun problem.

    I'll assume the non-efficient solution is obvious for most people.

    rene_d's hint about using a Trie is key here, as it's critical for getting O(n) efficiency out of the problem.

    I had never encountered a Trie before, so I had to grabble with it a bit before it made intuitive sense here.

    If you look up how a bitwise Trie is structured, you'll get an idea that it's a binary tree where each 1 or 0 bit at each position in a given integer points to another node. If you were to draw out any given value in a binary tree, you'd follow all 32-bits down, with 0 bits going left and 1 bits going right, until you reached a leaf node, and then you'd find the value you are searching for.

    If you take the input array of this problem and build a Trie out of all of the values in the array, you'd get a large tree with lots of values branching off from the various bit positions.

    How that helps you solve the maximum XOR problem is that you can do a query in the Trie to help you find what best possible XOR out of the possible choices.

    What's the best possible XOR companion value? It's one where all of the bits are the exact opposite of the candidate value.

    For example, if your query value (let's use nibbles for this discussion for conciseness) has a bit pattern of 0010, then the best possible XOR companion value would be 1101, which would give you a result of 1111.

    With a Trie query, you can see if there's a branch at the opposite bit value at each bit position. In the example above, for the MSB of 4, you'd try and see if there was a branch with a bit value of 1; in this case there is, but if not then you would take the branch with a bit value of 0 since that path actually exists.

    The end result is that you can query the Trie quickly and find the best possible match for every single query.

    • acalvino4
       + 1 comment
      [deleted]

      • yashpalsinghdeo1
         + 1 comment
        [deleted]

        • yashpalsinghdeo1
           + 0 comments

          here is problem solution in python and c++ programming.

          HackerRank Maximum Xor solution

    • acalvino4
       + 3 comments

      Why is this faster? You still need to add every element of the array to the tree in order to search the tree, which must take some time, whereas the obvious solution just xor's with each array element straight up. That is: Obvious algorithm: just xor with each array element and see which is greatest. More Optimal algorithm: add each array element to tree, then search the tree to find the max xor. Why is the second significatntly more optimal? They both run in O(array.length), though I can see how perhaps the second is faster by a constant factor. Is that it or am I missing something?

      • samuele8
         + 0 comments

        the "obvious algorithm" is doing the XOR on each element of the array arr, for each element of the array queries, i.e. there are two nested loops which result in a O(arr.length * queries.length) complexity.

        The trie algorithm is running in O(queries.length * height(trie)) where the height of the trie is the size of an integer (32 bits) so we can consider the height constant, which makes the whole algorithm run linearly, overall.

    • qwrtyuiuytres
       + 1 comment

      if n=2, (0,3) and query value=2. then with your way 2(10) ^ 3(11) = 1 is max value than 2(10) ^ 0(00) = 2. how?

      • bakaitBaalak
         + 0 comments

        The trie for [0,3] would be like

              root
      /   \
    0/     \1
    /       \
   0         3
        • By algorithm first we should obtain the 1's complement of 2, which can be obtained as 2^3 = 01
        • Now traverse the trie using 01 we first have to follow 0 for which an actual path exists and hence we arrive at a leaf node. Thus 0 is our answer which is what exactly is expected

    • [deleted]       + 1 comment

      I must admit I'm stumped by this problem.

      I cheated and found somebody else's trie solution on github. Is there any faster solution than a trie?

      • bonnotguillaume
         + 0 comments

        Yes, a compact trie :)

        How can you go faster than this ?

        You iterate a single time through each array, and the complexity of max is constant O(32)

    • m_d_elliott
       + 1 comment
      [deleted]

      • m_d_elliott
         + 1 comment

        Accidentally deleted my first post. Thanks so much for your help, helped me solve this in two hours and I knew nothing of Tries before hand! Not sure why this is formatting incorrectly, but I fixed it (kinda) with p tags

        // Class I use to construct the Trie:

        class BinTrie:

        head = {}

        def add(self, integer):
    cur = self.head
    b = "{:032b}".format(integer)

    for l in b:
        l = int(l)
        if l not in cur:
            cur[l] = {}
        cur = cur[l]
    cur['*'] = True

def max_companion(self, integer):
    cur = self.head
    b = "{:032b}".format(integer)
    m_comp = ''

    for l in b:
        l = int(l)
        opp = l ^ 1
        if opp in cur:
            l = opp
        cur = cur[l]
        m_comp += str(l)
    return int(m_comp, 2)

        def maxXor(arr, queries):

        d = BinTrie()

        out = []

        for x in arr:

        d.add(x)

        for v in queries:

        out.append(v ^ d.max_companion(v))

        return out

        • wf001
           + 0 comments

          You can shave 2 levels off your tree given that the maximum value as stated in the problem is 10^9 which is 111011100110101100101000000000. That's only 30 bits.

          In other words, you should be able to use "{:030b}" and get a slightly faster answer.

    • FaxMachin3
       + 0 comments

      TRIE C# implementation:

      using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Trie{
    Trie left;
    Trie right;

    public void Insert(Trie head, int n){
        for(int i = 31; i >= 0; i--){
            int value = (n>>i)&1;
            if(value == 0){//move left
                if(head.left == null)
                    head.left = new Trie();
                head = head.left;
            }
            else{//move right
                if(head.right == null)
                    head.right = new Trie();
                head = head.right;
            }
        }
    }
    
    public uint MaxXor(Trie head, int n){
        uint max = 0;
        for(int i = 31; i >= 0; i--){
            int value = (n>>i)&1;
            //for max xor you have to move alternate
            if(value == 0){//move right
                if(head.right != null){
                    max += (uint)Math.Pow(2,i);
                    head = head.right;
                }
                else
                    head = head.left;
            }
            else{//move left
                if(head.left != null){
                    max += (uint)Math.Pow(2,i);
                    head = head.left;
                }
                else
                    head = head.right;
            }
        }
        return max;
    }
}
class Solution {
    static int[] maxXor(int[] arr, int[] queries) {
        int[] result = new int[queries.Length];
        Trie head = new Trie();
        for(int i = 0; i < arr.Length; i++){
            head.Insert(head, arr[i]);
        }
        for(int i = 0; i < queries.Length; i++){
            result[i] = Convert.ToInt32(head.MaxXor(head, queries[i]));
        }
        return result;
    }

    static void Main(string[] args) {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        int n = Convert.ToInt32(Console.ReadLine());

        int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), arrTemp => Convert.ToInt32(arrTemp))
        ;
        int m = Convert.ToInt32(Console.ReadLine());

        int[] queries = new int [m];

        for (int i = 0; i < m; i++) {
            int queriesItem = Convert.ToInt32(Console.ReadLine());
            queries[i] = queriesItem;
        }

        int[] result = maxXor(arr, queries);

        textWriter.WriteLine(string.Join("\n", result));

        textWriter.Flush();
        textWriter.Close();
    }
}

    • michellerodri247
       + 1 comment

      XOR is the exclusive or that is a logical operation. 0 and 1 are used to represent the input and output of it. The best wrongful death lawyers near me value of it is true if it is having the number of true input is odd.

    • bonginimarco
       + 0 comments

      Thank you so much for the hint! I solved the problem with a trie :) and it was fun.

    • RamaKrishnaA
       + 0 comments

      it was very helpful. guys for code reference check https://www.geeksforgeeks.org/find-the-maximum-subarray-xor-in-a-given-array/

      have to change query and maxSubarrayXOR methodes.

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

Join us

Create a HackerRank account

Be part of a 26 million-strong community of developers

Already have an account?Log in