Maximum Xor

  • + 0 comments

    In swift. At first I add submit code and I failed in only test case 5 then I do nothing any change and jst again click submit code I passed in all test cases.

    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) >> bitPos // Extract the bit at the current position
      let remainder = value & (power - 1) // Calculate the remainder
    
      if let child = children[bit] {
                child.add(value: remainder, index: index + 1)
      } else {
                children[bit] = TrieNode()
        children[bit]!.add(value: remainder, index: index + 1)
            }
    }
    }
    
    struct BitTrie {
        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) >> bitPos // Extract the bit at the current position
        remainder = remainder & (power - 1) // Calculate the remainder
    
        if let child = current.children[bit ^ 1] {
                    xorValue += power
          current = child
                 } else {
                     current = current.children[bit]!
         }
       }
    
       return xorValue
            }
        }
    
    // Complete the maxXor function below.
    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
    }