Given a continuous stream of 1's and 0's how do

Interview Questions

Given a continuous stream of 1's and 0's how do you determine .....

Microsoft Interview Questions and Answers

79. Given a continuous stream of 1's and 0's how do you determine .....

Question:
Given a continuous stream of 1's and 0's how do you determine whether the number so far is divisible by 3? At any point of time, you will have previous sequence in hand and a 1 or a 0 appears, without looking at the entire sequence we should be able to tell whether the sequence formed by adding the new number will is divisible by 3 or not?

maybe an answer:

Let a sequence of already seen bit stream = n (modulo 3) i.e. n = 0, 1, or 2.

If next bit is 0, we get 2n (modulo 3), and if next bit is 1, we get 2n+1 (modulo 3). From this observation, we get two mapping tables (based on next bit value) which could solve the problem straight forwardly. Here's the code to check ideone.com/6Wdsa

I remember there are some easier methods (less obvious). One is like (# of 1s in odd pos - # of 1s in even pos) % 3 == 0. Anyone care to prove this?

An example explains the idea:
{{
1 0 1 0 1 1 1
1st bit 1 : 1 % 3 = 1
2nd bit 0 : (2*1) % 3 = 2
3rd bit 1 : (2*2 + 1) % 3 = 2
4th bit 0 : (2*2) % 3 = 1
5th bit 1 : (2*1+1) % 3 = 0
6th bit 1 : (2*0+1) % 3 = 1
7th bit 1 : (2*1+1) % 3 = 0
}}}

Proof for second idea
Let counting starts from 0 from LSB in binary
representation of given number.So in this manner
Let number of 1s at odd positions is Xd.
Let number of 1s at even postions is Xn.
Then the number can be represented as
i j
N=Sumation(2) + Sumation(2)
i=d1,d2..Xd j=e1,e2..Xn
d1,d2.. are odd positions with 1
e1,e2.. are even positions with 1.
now all even power of 2 can be written as 3p+1 and all odd
powers of 2 can be written as 3q+2. (deduce it by urself).
Therfore we have:
N=Sumation(3q+2) + Sumation(3p+1)
i=d1,d2..Xd j=e1,e2..Xn
So N can be represented as:
N = (3M+2Xd) + (3P+Xn)
N = 3(P+M)+2Xd+Xn
N = 3(P+M+Xd)+Xn-Xd
Therfore N is divisible by 3 if (Xn-Xd) is divisible by 3.
This can be implimented very easily.

(Continued on next question...)