Given a function called
rand5() that returns a random number between 1 and 5, write a function called
rand2() that returns a number between 1 and 2.
Non uniform distribution
The initial intuition would be to take the modulo of
rand5() directly, but just as was the case with the rand 5 question, you will not get an even distribution since
rand5() has an odd number of elements. You will however have a
O(1) function, so if uniform distribution is not that important, this may be an okay solution.
In order to get a uniform distributions, we will need to make a trade off in terms of potential computational cycles. We can query for any number that is less than 4, and take the modulo of that, which will give us an equal chance of getting 1 or 2, but at the cost of the loop executing multiple times.
def rand2(): i = 5 while i == 5: i = rand5() return (i % 2) + 1
You may also want to read:
Given a function called rand5() that returns a random number between 1 and 5, write a function called rand7() that returns a number between 1 and 7.Read More >>
Given a singly linked list, write a function that returns a linked list with all the nodes in reverse order.Read More >>