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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Maximum Xor
  2. Discussions

Maximum Xor

Problem
Submissions
Leaderboard
Discussions
Editorial

    You are viewing a single comment's thread. Return to all comments →

  • howard_hw_lee
    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
    }
    
    4|
    Permalink
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature