Fair Coin from a Biased Coin
Problem statement
You need a fair coin, but the only coin you have is biased. It lands heads with some unknown probability p, where 0 < p < 1, and tails otherwise, and every flip is independent of the others.
The string flips records the biased coin's results in order: 'H' is heads and 'T' is tails. Turn it into at most k fair results with this procedure:
- Read the flips in consecutive pairs that do not overlap: positions
0and1, then2and3, and so on. - If the two flips of a pair differ, the pair produces one fair result equal to its first flip:
HTgives'H'andTHgives'T'. - If the two flips of a pair are the same (
HHorTT), the pair produces nothing and is discarded. - Stop as soon as
kfair results have been produced. If the flips run out first, stop there. A last flip without a partner is ignored.
Return the fair results in the order they were produced, as one string. It can be shorter than k, or empty, when the flips run out.
Examples
Example 1
flips = "HHTHTTHT"k = 2return = "TH"The pairs are HH, TH, TT and HT. HH and TT are discarded. TH gives T and HT gives H, so the two fair results are "TH".
Unlock this recently reported problem
FastPrep Pro gives you full access to interview problems reported within the last week.
- Full problem statement and constraints
- 2 more worked examples, explained
- Guided hints and editorial
- Run your code on real test cases
$99 billed yearly — or $19 month-to-month. Cancel anytime.