Thursday, May 17, 2012

To decide whether the stream of 0 and 1 is divisible by 3 or not

Problem Statement :-  Stream of bits are being received on a network port. As obvious, each bit is either 0 or 1. Incoming stream is a never ending sequence of such 0's and 1's and we want to check at any given time that whatever stream received so far is divisible by 3 or not.  So let say we have got 110010101000101....0, then we want to have an answer ready for whether the decimal number formed by taking this input will be divisible by 3 or not. Least position value is the latest/last bit received.

Solution:- 

As soon as port starts receiving the bit values, Use the first three bits to decide whether its divisible by 3 or not. If its divisible by 3 then consider it to be at state "3x" else based on the reminder consider it to be "3x+1" or "3x+2" state. For example if first three digits are 110 then its equal to 6 and should be considered as state "3x" else if its 111 then its 7 and should be considered as state "3x+1"(for 7 = 3*2+1).

Now we just need to follow the state transition diagram below to keep track of on which state we are right now. As depicted by the State Transition Diagram, State change happens based on considering the next bit arrived. for example if we are at state "3x" at any given moment and we receive 0 as next bit then the new state we are in is state "3x" only....But if we get next bit as 1 then we move to state "3x+1". This way, no matter how many bits have been received so far(million...trillion or whatever..) we just need constant space to save the current state. Now, If at any point someone asks that if the sequence of bits received is divisible by three or not....We just need to see the current state and if its "3x" then its divisible otherwise its not. This logic can be extended for checking the divisibility by any number and not only three. Its a classical example of usage of DFA or Deterministic Finite Automaton.

 


Why this state transition diagram is correct? If we have a number divisible by 3 and we get one additional bit at the last as 0, then its simple left shift which makes the number to get doubled i.e. its still divisible by 3 and hence the state is named as "3x" as this number can be represented by 3x for some positive value of 'x'. But if the new bit is 1, its double the number and adds 1 to it making the remainder as 1 when the number is divisible by 3 and hence the state name is kept as "3x+1". same argument follows for state "3x+2".