You are viewing a single comment's thread. Return to all 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)
Seems like cookies are disabled on this browser, please enable them to open this website
Maximum Xor
You are viewing a single comment's thread. Return to all comments →
Full Ruby implementation of the Trie approach: