Check Divisibility In a Stream Of 1′s and 0′s

A stream of 1′s and 0′s are coming. At any time we have to tell that the resultant number from the binary digits till that point is divisible by 3 or not.

For eg: let’s see one example. Let 1 come (not div by 3).then 1 come so resultant binary number is 11(3) which is divisible by 3, then 0 come make it to 110(3) which is divisible by 3, then 0 come make it to 1100(12) which also divisible by 3.

Solution

How about a state machine with 3 states 3x, 3x+1, 3x+2 where x is just a symbol.
3x denotes divisible by 3 and no remainder
3x+1 denotes remainder is 1
3x+2 denotes remainder is 2

Now, suppose you have binary number 1.
If it is appended by 0 it will become 10 (2 in decimal) means 2 times of the previous value.
If it is appended by 1 it will become 11(3 in decimal), 2 times of previous value +1.

When a binary number is appended by 0 (means
multiplied by 2), the new remainder can be
calculated based on current remainder only.
r = 2*r % n;

And when a binary number is appended by 1.
r = (2*r + 1) % n;

void CheckDivisibility(int n) 
{ 
    int remainder = 0; 
    std::cout << "press any key other than 0"
                 " and 1 to terminate \n"; 
    while (true) 
    { 
        int incomingBit; 
        cin >> incomingBit; 
  
        // Update remainder 
        if (incomingBit == 1) 
            remainder = (remainder * 2 + 1) % n; 
        else if (incomingBit == 0) 
            remainder = (remainder * 2) % n; 
        else
            break; 
  
        // If remainder is 0. 
        if (remainder % n == 0) 
            cout << "yes \n"; 
        else
            cout << "no \n"; 
    } 
} 
  
// main
int main() 
{ 
    CheckDivisibility(3); 
    return 0; 
}