puzzle - Given a function for a fair coin, write a function for a biased coin? -

i came across reported interview question when doing reviewing (the following quote info found problem):

given function fair coin, write function biased coin returns heads 1/n times (n param)

at first glance wrote:

int biased_coin(n) { //0=tails, 1=heads   int sum = 0;    if(n==1)     return 1;    for(int i=0;i<n;i++) {     sum += unbiased(); //unbiased returns 0 50% of time , 1 50% of time   }    if(sum == 1)     return 1;    return 0; } 

but doesn't work. n=4, instance, work: since probability of getting single head given 4 tosses 4/(2^4)=1/4. n=3, 3/(2^3)!=1/3.

what proper way implement assuming can't use random number generator?

assuming:

int faircointoss(); 

returns 1 heads , 2 tails, writing:

int biasedcointoss(int n); 

where heads (1) appear 1/n of time should work:

int biasedcointoss(int n) {   if (n == 1) {     return 1; // 1/1 = 1 = heads   } else if (n == 2) {     return faircointoss(); // 1/2 = 50% = fair coint oss   }   int r = random_number(n);   return r == 0 ? 1 : 0; } 

where random_number(n) generates fair random integer such 0 <= < n. random_number(3) 0, 1 or 2. assuming distribution, value 0 come out 1/3 of time.

of course can't use native random number generator can create 1 anyway. faircointoss() randomly generates 1 or 0. multiple coin tosses can combined generate larger number. example:

faircointoss() << 1 | faircointoss() 

will generate:

00 = 0 01 = 1 10 = 2 11 = 3 

which definition random number 0 3 (n = 4).

that's fine if n power-of-2 isn't necessarily. that's easy enough cater however. assume n = 5. @ best can generate random number 0 7. if "reroll" 5, 6 or 7 until number in range of 0 4 have (non-deterministically) constructed random number distributed 0 4 inclusive, satisfying requirement.

code looks this:

int random_number(int n) {   int ret;   {     int limit = 2;     ret = faircointoss();     while (limit < n) {       ret <<= 1;       ret |= faircointoss();       limit <<= 1;     }   } while (ret >= n);   return ret; }