Infinite Bit Stream Problems

All such Problems we cannot store the input strings. For all such questions which require computation on infinite Bit Streams we use a FSM(Finite State Machine). Let us discuss some such problems.

1. Find out remainder when the given bit stream is divided by 2.
Input : 010
Output: 0

Input : 0101
Output : 1

Solution:
Design an FSM in which u have states as remainder. So for 2 we can have only two possible remainders 0 or 1.

Now start with a state 0. Be in this state till u get a 1. If in 1 you get a zero then move to state 0 this looks something like this. The end state will give us the remainder.





Similarly we can apply the same logic to find the remainder when the number is divided by 3...(Remainder can be 0,1,2)


In General:

If you are finding the remainder of a bit stream when divided by N then...
if you are in state A. then

CASE 1: Input is 0
nextState = (A * 2 + 0) % N

CASE 2: Input is 1
nextState = (A * 2 + 1) % N

When u reach the end of the i/p you state is the remainder....

Code
/*************************************************************
arr contains the input. arr will contain 0/1....
**************************************************************/
unsigned int findRemainder(int arr[],int len, int divisor)
{
int i=0;
int currState = 0;
while(i lessThan len)
{
currState = (currState * 2 + arr[i]) % divisor;
i++;
}
return currState;
}
/************************************************************************
-numberSystem if 2 then input string contains 0/1...
-numberSystem if 10 then input string contains 0/1/2/3/4/5/6/7/8/9
-arr contains the input. arr will contain [0,9]
*************************************************************************/
unsigned int findRemainder(int arr[],unsigned int numberSystem,int len, int divisor)
{
int i=0;
int currState = 0;
while(i lessThan len)
{
currState = (currState * numberSystem + arr[i]) % divisor;
i++;
}
return currState;
}