Logic implementation in Trie

[kaneki13]

• Link to question : https://www.hackerrank.com/challenges/maximizing-xor/problem
• Link to Logic : https://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems
• Link to code : https://repl.it/@NikhilAgrawal/TrustingShorttermBarebirdbat

I am trying to implement above logic but made a mistake somewhere and could not identify it. Please help.

PS: I know that question can be solved using brute force too.

TIA

[shreybatra]

your loop to insert the elements in TRIE is wrong. try to add a “cout << temp” just before “ins(trie,s)”. You’ll see that numbers 10-15 are not correct for the input 10 15. convert to binary string in a better way. check this link to convert the number into binary but limit the bits to max 12, not 32. as limits for the question is just 10^3 and not 10^9.

Regards.

[kaneki13]

“temp” is the value obtained after XOR. While “string s” is the binary representation of “temp”. If I cout s, then it’s working fine.
Correct me if I am wrong.
Thanks!

[kaneki13]

I found the bug!

[shreybatra]

you are inserting temp. you dont have to insert the XOR. you just have to insert the no. and calculate the max xor with the elements in the trie not with the ‘i’ loop. Hope you get it.

[kaneki13]

@shreybatra I figured it out yesterday! Between thanks for the effort.

[shreybatra]

always!