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.
I used count sort as a starting point. Built an array of 32768 elements. Each element -- a list of indexes of corresponding value from input array. Index in the array itself is a value from input array. Obviously not all elements in the array will be filled.
Next I built an "ideal index" that is a ^ 32767. If we have an element with such index in the above array and list of indexes includes left and right limits -- we are good, we found the max value, which will be a ^ index.
If index points to an empty element or if list of indexes does not include left and right limits we need to modify "ideal index" by XOR-ing it with a mask.
Mask can be an integer between 1 and 32767 incremented after each failure to find the right element in the array.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
XOR key
You are viewing a single comment's thread. Return to all comments →
I used count sort as a starting point. Built an array of 32768 elements. Each element -- a list of indexes of corresponding value from input array. Index in the array itself is a value from input array. Obviously not all elements in the array will be filled.
Next I built an "ideal index" that is a ^ 32767. If we have an element with such index in the above array and list of indexes includes left and right limits -- we are good, we found the max value, which will be a ^ index.
If index points to an empty element or if list of indexes does not include left and right limits we need to modify "ideal index" by XOR-ing it with a mask. Mask can be an integer between 1 and 32767 incremented after each failure to find the right element in the array.