LeetCode: Maximum XOR of Two Numbers in an Array

Question

Please review how clear my code is and also comment on performance.

Given a non-empty array of numbers, a0, a1, a2, ... , an-1, where 0 ≤ ai < 2^31.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.

Could you do this in O(n) runtime?

Example:

Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.

LeetCode

using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace TrieQuestions
{
 /// <summary>
 /// https://leetcode.com/explore/learn/card/trie/149/practical-application-ii/1057/
 /// </summary>
 [TestClass]
 public class FindMaxXorInArray
 {
 [TestMethod]
 public void XorTrieTreeTest()
 {
 int[] nums = {3, 10, 5, 25, 2, 8};
 Assert.AreEqual(28,FindMaximumXOR(nums));
 }
 //xor mean if the 0^0 == 0 and 1^1 == 0
 // so if we want maximum we want the maximum opposites
 public int FindMaximumXOR(int[] nums)
 {
 XorTrieTree tree = new XorTrieTree();
 tree.Insert(nums);
 return tree.GetMax(nums);
 }
 }
 public class XorTrieTree
 {
 private XorTreeNode _root;
 public XorTrieTree()
 {
 _root = new XorTreeNode();
 }
 /// <summary>
 /// for each one of the numbers we find we flags are set on with right shit all of the 32 bits
 /// and bitwise AND to understand if the bit is set on or off
 /// </summary>
 /// <param name="nums"></param>
 public void Insert(int[] nums)
 {
 foreach (var num in nums)
 {
 XorTreeNode cur = _root;
 for (int i = 31; i >= 0; i--)
 {
 int bit = (num >> i) & 1;
 if (cur.children[bit] == null)
 {
 cur.children[bit] = new XorTreeNode();
 }
 cur = cur.children[bit];
 }
 }
 }
 /// <summary>
 /// for each one of the numbers we try to understand which bits are set on.
 /// if the the bit is set on then we search for the NOT bit of that,
 /// we add the NOT bit to the temp xorValue variable, because the prefix of those two numbers are xor-ed
 /// and continue to the NOT bit next node.
 /// at the end we do max of current max and xorValue
 /// </summary>
 /// <param name="nums"></param>
 /// <returns></returns>
 public int GetMax(int[] nums)
 {
 int max = int.MinValue;
 foreach (var num in nums)
 {
 XorTreeNode cur = _root;
 int xorValue = 0;
 for (int i = 31; i >= 0; i--)
 {
 int bit = (num >> i) & 1;
 if (cur.children[bit == 1 ? 0 : 1] != null)
 {
 xorValue += (1 << i);
 cur = cur.children[bit == 1 ? 0 : 1];
 }
 else
 {
 cur = cur.children[bit];
 }
 }
 max = Math.Max(xorValue, max);
 }
 return max;
 }
 }
 //the root has 2 nodes for 0 and 1
 public class XorTreeNode
 {
 public int Val;
 public XorTreeNode[] children;
 public XorTreeNode()
 {
 children = new XorTreeNode[2];
 }
 }
}

Answer 1

In XorTreeNode you're not using the field Val

---

public void Insert(int[] nums)
public int GetMax(int[] nums)

Having two methods that must take the same data to operate on is hazardous and should be avoided. Either provide the data to the constructor or you should only have one public method with the data set as argument:

public int FindMaxXor(int[] nums) { Insert(nums); return GetMax(nums) }

---

You can invert a bit in the following way:

bit ^ 1

It can be used to simplify this:

 int bit = (num >> i) & 1;
 if (cur.children[bit == 1 ? 0 : 1] != null)
 {
 xorValue += (1 << i);
 cur = cur.children[bit == 1 ? 0 : 1];
 }
 else
 {
 cur = cur.children[bit];
 }

to

 int bit = ((num >> i) & 1) ^ 1;
 if (cur.children[bit] != null)
 {
 xorValue += (1 << i);
 cur = cur.children[bit];
 }
 else
 {
 cur = cur.children[bit ^ 1];
 }

---

You can insert numbers and search for max in the same operation, because every new number only need to compare with already existing numbers.

So you can change GetMax(...) to:

private int GetMax(int num)
{
 XorTreeNode cur = _root;
 int xorValue = 0;
 for (int i = _numBits; cur != null && i >= 0; i--)
 {
 int bit = ((num >> i) & 1) ^ 1;
 if (cur.children[bit] != null)
 {
 xorValue += (1 << i);
 cur = cur.children[bit];
 }
 else
 {
 cur = cur.children[bit ^ 1];
 }
 }
 return xorValue;
}

and Insert(...) to:

public int FindMaxXor(int[] nums)
{
 int result = int.MinValue;
 foreach (var num in nums)
 {
 result = Math.Max(result, GetMax(num));
 XorTreeNode cur = _root;
 for (int i = _numBits; i >= 0; i--)
 {
 int bit = (num >> i) & 1;
 if (cur.children[bit] == null)
 {
 cur.children[bit] = new XorTreeNode();
 }
 cur = cur.children[bit];
 }
 }
 return result;
}

where _numBits is defined as a class const field:

private const int _numBits = 31;

---

If you know that the nums array contains only small values there might be a significant performance improvement in finding the leftmost significant bit:

 int max = nums.Max();
 while (max > 0)
 {
 _numBits++;
 max >>= 1;
 }

in the start of the Insert(...) method. _numBits should then not be const and initialized to zero obviously. If the numbers span over the entire int+ domain this may slow the entire process.