Jim
BAN USERSeems like maths, does it not?
ab2c3 10
((2*2)+1)*3 > 10
So it is somewhere in the (2*2)+1 chunk. 10%5 = 0 (or 5) = 5
Ignoring the info in the 4 chunk, we take the 5th. So the answer is c.
A more complex example:
ab10c9de5 53
((2*10) + 1) *9 > 53
Consider [(2*10) + 1] chunk. It will be the 53 % 21 = 11th
(2*10) > 11
Conside the [2] chunk. It will be the 11%2 = 1st character
= a
This would work if you could additionally have the XOR of all the unique numbers in a list. Lemma. A way to XOR all unique numbers, not doing any of them twice in O(n) time, O(n) space. Then XOR the result from above with the result of XORing all the unique numbers that exist in the array will give the even value.
If you can solve that unique numbers lemma, then you can just avoid XORing the first occurrence and then the result would work.
Pretty easy question. It is just hard to think in those interviews sometimes.
- Jim August 28, 2014