Maximum Xor Discussions |

4 years ago+ 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
}