No. of paths in integer array

An integer array {3,1,2,7,5,6}. One can move forward through the array either each element at a time or can jump a few elements based on the value at that index.

count the number of possible paths to reach the end of the array from start index.

Ex – input {3,1,2,7,5,6}

sol[6] = 1;
for (i = 4; i>=0;i--) {
     sol[i] = sol[i+1];
     if (i+input[i] < 6 && input[i] != 1)
         sol[i] += sol[i+input[i]];             
}

return sol[0];

DFA based division

Example

Suppose we want to check whether a given number ‘num’ is divisible by 3 or not

1. When we are at state 0 and read 0, we remain at state 0.
2. When we are at state 0 and read 1, we move to state 1, The number so formed(1) in decimal gives remainder 1.
3. When we are at state 1 and read 0, we move to state 2, The number so formed(10) in decimal gives remainder 2.
4. When we are at state 1 and read 1, we move to state 0, The number so formed(11) in decimal gives remainder 0.
5. When we are at state 2 and read 0, we move to state 1, The number so formed(100) in decimal gives remainder 1.
6. When we are at state 2 and read 1, we remain at state 2, The number so formed(101) in decimal gives remainder 2.

The transition table looks like following:

state   0   1
_____________
0      0   1
1      2   0
2      1   2

Let us check whether 6 is divisible by 3?
Binary representation of 6 is 110
state = 0
1. state=0, we read 1, new state=1
2. state=1, we read 1, new state=0
3. state=0, we read 0, new state=0
Since the final state is 0, the number is divisible by 3.

Let us take another example number as 4
state=0
1. state=0, we read 1, new state=1
2. state=1, we read 0, new state=2
3. state=2, we read 0, new state=1
Since, the final state is not 0, the number is not divisible by 3. The remainder is 1.

Note that the final state gives the remainder.

Make a fair coin from a biased coin

Question

You are given a function foo() that represents a biased coin. When foo() is called, it returns 0 with 60% probability, and 1 with 40% probability. Write a new function that returns 0 and 1 with 50% probability each. Your function should use only foo()

Answer
We call foo() two times. Both calls will return 0 with 60% probability. So the two pairs (0, 1) and (1, 0) will be generated with equal probability from two calls of foo().
(0, 1): The probability to get 0 followed by 1 from two calls of foo() = 0.6 * 0.4 = 0.24
(1, 0): The probability to get 1 followed by 0 from two calls of foo() = 0.4 * 0.6 = 0.24
So the two cases appear with equal probability. The idea is to return consider only the above two cases, return 0 in one case, return 1 in other case. For other cases [(0, 0) and (1, 1)], recur until you end up in any of the above two cases.

int my_fun() 
{
    int val1 = foo();
    int val2 = foo();
    if (val1 == 0 && val2 == 1)
        return 0;   // Will reach here with 0.24 probability
    if (val1 == 1 && val2 == 0)
        return 1;   // // Will reach here with 0.24 probability
    return my_fun();  // will reach here with (1 - 0.24 - 0.24) probability
}

Check divisibility by 7

A number of the form 10a + b is divisible by 7 if and only if a – 2b is divisible by 7
Example:

the number 371: 37 – (2×1) = 37 – 2 = 35; 3 – (2 × 5) = 3 – 10 = -7; thus, since -7 is divisible by 7, 371 is divisible by 7.

Solution
return isDivisibleBy7( num / 10 – 2 * ( num – num / 10 * 10 ) );

LOGIC

   10.a + b 
after multiplying by 2, this becomes
   20.a + 2.b 
and then
   21.a - a + 2.b 
Eliminating the multiple of 21 gives
   - a + 2b
and multiplying by -1 gives
    a - 2b

Equal Probability

Question

Given a function foo() that returns integers from 1 to 5 with equal probability, write a function that returns integers from 1 to 7 with equal probability using foo() only.

Solution

If we somehow generate integers from 1 to a-multiple-of-7 (like 7, 14, 21, …) with equal probability, we can use modulo division by 7 followed by adding 1 to get the numbers from 1 to 7 with equal probability.
We can generate from 1 to 21 with equal probability using the following expression.

 5*foo() + foo() -5

Let us see how above expression can be used.
1. For each value of first foo(), there can be 5 possible combinations for values of second foo(). So, there are total 25 combinations possible.
2. The range of values returned by the above equation is 1 to 25, each integer occurring exactly once.
3. If the value of the equation comes out to be less than 22, return modulo division by 7 followed by adding 1. Else, again call the method recursively. The probability of returning each integer thus becomes 1/7.

CODE

int my_rand() // returns 1 to 7 with equal probability
{
    int i;
    i = 5*foo() + foo() - 5;
    if (i < 22)
        return i%7 + 1;
    return my_rand();
}