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.
interesting problem; fairly straightforward once you think about it for a bit. some hints that may prove helpful if you're stuck:
[spoiler]
1) use [1,a] for the range instead of [a,b]:
f([a+1,b]) = (f([1,b])*b-f([1,a])*a)/(b-a) due to the linearity of expected value/probability
2) find the ev/prob for each i-bit subset of the range (ie numbers between 2^i and 2^(i+1)) separately and then linearly combine them at the end. this way the same algorithm can be used for both parts of the problems - just multiply each prob by i to convert from probability to the expected number of bits or divide to go in the opposite direction
3) the range spanned by the most significant bit (msb) can be written as a linear combination of i-bit ranges (with prefix bits)
[/spoiler]
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Random Integers Random Bits
You are viewing a single comment's thread. Return to all comments →
interesting problem; fairly straightforward once you think about it for a bit. some hints that may prove helpful if you're stuck:
[spoiler]
1) use [1,a] for the range instead of [a,b]:
f([a+1,b]) = (f([1,b])*b-f([1,a])*a)/(b-a) due to the linearity of expected value/probability
2) find the ev/prob for each i-bit subset of the range (ie numbers between 2^i and 2^(i+1)) separately and then linearly combine them at the end. this way the same algorithm can be used for both parts of the problems - just multiply each prob by i to convert from probability to the expected number of bits or divide to go in the opposite direction
3) the range spanned by the most significant bit (msb) can be written as a linear combination of i-bit ranges (with prefix bits)
[/spoiler]