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.
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.structBitTrie{classTrieNode{varchildren=Array<TrieNode?>(repeating:nil,count:2)funcadd(value:Int,index:Int){letbitPos=31-indexifbitPos<0{return}letpower=1<<bitPosletbit=value/powerletremainder=value%powerifletchild=children[bit]{child.add(value:remainder,index:index+1)}else{children[bit]=TrieNode()children[bit]!.add(value:remainder,index:index+1)}}}letroot=TrieNode()funcadd(_value:Int){root.add(value:value,index:0)}funcgetMaxXor(_value:Int)->Int{varcurrent=rootvarxorValue=0varremainder=valueforiin0..<32{letbitPos=31-iletpower=1<<bitPosletbit=remainder/powerremainder=remainder%powerifletchild=current.children[bit^1]{xorValue+=powercurrent=child}else{current=current.children[bit]!}}returnxorValue}}funcmaxXor(arr:[Int],queries:[Int])->[Int]{varmaxVals=[Int]()lettrie=BitTrie()forvalueinarr{trie.add(value)}forqueryinqueries{maxVals.append(trie.getMaxXor(query))}returnmaxVals}
Cookie support is required to access HackerRank
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 →
That was tough. Trie based Swift solution.
A few things it seems people aren't exploiting: