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

  • howard_hw_lee
     + 0 comments

    That was tough. Trie based Swift solution.

    A few things it seems people aren't exploiting:

    • you can test a bit by doing a division by 1 << bit position
    • you can strip a MSB by doing a mod by 1 << bit position
    • you can flip a bit by XOR with 1
    // Complete the maxXor function below.
struct BitTrie {
  class TrieNode {
    var children = Array<TrieNode?>(repeating: nil, count: 2)
    
    func add(value: Int, index: Int) {
      let bitPos = 31-index
      if bitPos < 0 { return }
      
      let power = 1 << bitPos
      let bit = value / power
      let remainder = value % power

      if let child = children[bit] {
        child.add(value: remainder, index: index+1)
      } else {
        children[bit] = TrieNode()
        children[bit]!.add(value: remainder, index: index+1)
      }
    }
  }
  
  let root = TrieNode()
  
  func add(_ value: Int) {
    root.add(value: value, index: 0)
  }
  
  func getMaxXor(_ value: Int) -> Int {
    var current = root
    var xorValue = 0
    var remainder = value
    
    for i in 0..<32 {
      let bitPos = 31-i      
      let power = 1 << bitPos
      let bit = remainder / power
      remainder = remainder % power

      if let child = current.children[bit^1] {
        xorValue += power
        current = child
      } else {
        current = current.children[bit]!
      }
    }
    
    return xorValue
  }
}

func maxXor(arr: [Int], queries: [Int]) -> [Int] {
  var maxVals = [Int]()
  let trie = BitTrie()

  for value in arr {
    trie.add(value)
  }
  
  for query in queries {
   maxVals.append(trie.getMaxXor(query))
  }
  
  return maxVals
}