Randomized algorithm
1.How to generate 0,1 with 50% probability??
Ans:- we can think of natural number . We know that every two consecutive number is always odd and even or even and odd.

Ex. 1(odd) 2(even) 3(odd) 4(even) 5(odd) 6(even) 7(odd) 8(even) 9(odd) 10(even).
At each iteration we try to generate a number it could be either even number or odd.If we do AND operation with 1 then if number is odd then it will give you 1 else 0.

int rand2()
{
   return rand()&1;
}

Qno.2 Given a function rand2() that returns 0 or 1 with equal probability, write a function that returns 1 with 75% probability and 0 with 25% probability using rand2() only.

Ans:-The idea is to use Bitwise OR. A bitwise OR takes two bits and returns 0 if both bits are 0, while otherwise the result is 1. So it has 75% probability that it will return 1.

int rand2()
{
    // rand() function will generate odd or even
    // number with equal probability. If rand()
    // generates odd number, the function will
    // return 1 else it will return 0.
    return rand() & 1;
}
 
// Random Function to that returns 1 with 75%
// probability and 0 with 25% probability using
// Bitwise OR
bool rand75()
{
    return rand2() | rand2();
}

On similar lines, we can also use Bitwise AND. Since it returns 0 with 75%.

bool rand75() 
{
    return !(rand50() & rand50());
}

There are various kind of problem like generate rand6() from rand2() and many more. I will explain some of them here.

Qno.3 Given a function rand6() that returns random numbers from 1 to 6 with equal probability, implement one-liner function rand12() using rand6() that returns random numbers from 1 to 12 with equal probability.

ans:-rand6() can generate 1,2,3,4,5,6 but what about 7,8,9,10,11,12.

So we can think of like this rand6()&1 which will always generate number 1,0 and if multiply with 6 then

(rand6()&1 )*6=0,6
rand6()+(rand6()&1)*6=> first rand6() will generate number between 1 to 6 and then second one will 0,6 after adding these two number it will result in generation of number from 1 to 12.

// if rand6() is even
if (rand6() & 1)
return 6 + rand6();
else // if rand6() is odd
return rand6();

int rand6()
{
    // rand() will generate random numbers between 0 and
    // RAND_MAX with equal probability
    // rand() % 6 returns number from 0 to 5 equal probability
    // (rand() % 6) + 1 returns number from 1 to 6 with
    // equal probability
    return (rand() % 6) + 1;
}
  // The function uses rand6() to return random numbers
// from 1 to 12 with equal probability
int rand12()
{
    return rand6() + (rand6() % 2) * 6;
}
 

Q.Given a function rand2() that returns 0 or 1 with equal probability, implement rand3() using rand2() that returns 0, 1 or 2 with equal probability.

ANS:-The idea is to use expression 2 * rand2() + rand2(). It returns 0, 1, 2, 3 with equal probability. To make it return 0, 1, 2 with equal probability, we eliminate the undesired event 3.

// Random Function to that returns 0 or 1 with
// equal probability
int rand2()
{
    // rand() function will generate odd or even
    // number with equal probability. If rand()
    // generates odd number, the function will
    // return 1 else it will return 0.
    return rand() & 1;
}
  
// Random Function to that returns 0, 1 or 2 with
// equal probability 1 with 75%
int rand3()
{
    // returns 0, 1, 2 or 3 with 25% probability
    int r = 2 * rand2() + rand2();
     
    if (r < 3)
        return r;
     
    return rand3();
}

Generalization:-
Implement randM() using randN() when M > N:
Use randX() to generate randM().

Note: N^b * (randN() - 1) + N^(b - 1) * (randN() - 1) + N^(b - 2) * (randN() - 1) + ... + N^0 * (randN() - 1) generates randX() - 1, where X = N^(b + 1).

More Examples
(1) Implement rand11() using rand3():

 int rand11() {
    int result = 22;
    while (result >= 22) {result = 3 * 3 * (rand3() - 1) + 3 * (rand3() - 1) + (rand3() - 1);}
    return result % 11 + 1;
}

Idea: rand3() -> rand27() -> rand22 -> rand11
Time Comlexity: O(27/22)
(2) Implement rand9() using rand7():

int rand9() {
    int result = 45;
    while (result >= 45) {result = 7 * (rand7() - 1) + (rand7() - 1);}
    return result % 9 + 1;
}

Idea: rand7() -> rand49() -> rand45() -> rand9()
Time Comlexity: O(49/45)
(3) Implement rand13() using rand6():

int rand13() {
    int result = 26;
    while (result >= 26) {result = 6 * (rand6() - 1) + (rand6() - 1);}
    return result % 13 + 1;
}

Idea: rand6() -> rand36() -> rand26 -> rand13()
Time Comlexity: O(36/26)