Maximum Xor

  • + 0 comments

    Full Ruby implementation of the Trie approach:

    def max_xor(arr, queries)
      trie = Trie.new
      arr.each do |e|
        trie.insert(e)
      end
      queries.map do |q|
        q ^ trie.find_max_xor(q)
      end
    end
    
    class TrieNode
      attr_accessor :value, :children
    
      def initialize(value = nil)
        @value = value
        @children = {}
      end
    end
    
    class Trie
      def initialize(keypadding = 30)
        @keypadding = keypadding
        @root = TrieNode.new
      end
    
      def insert(value)
        key = pad_key(value)
        node = @root
        key.each_char do |c|
          node.children[c] = TrieNode.new if node.children[c].nil?
          node = node.children[c]
        end
        node.value = value
      end
    
      def find_max_xor(key)
        key = pad_key(key)
        node = @root
        key.each_char do |c|
          comp = (c.to_i ^ 1).to_s
          c = node.children[comp].nil? ? c : comp
          return nil if node.children[c].nil?
    
          node = node.children[c]
        end
        node.value
      end
    
      private
      def pad_key(key)
        format("%0#{@keypadding}b", key)
      end
    end
    
    _n = gets.to_i
    arr = gets.split.map(&:to_i)
    m = gets.to_i
    queries = Array.new(m)
    m.times { |i| queries[i] = gets.to_i }
    puts max_xor(arr, queries)