## Divisible by 3 Problem

**Problem**: 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?

#include<iostream> using namespace std; int main() { int zero[3] = {0,2,1}; int one[3] = {1,0,2}; int x, mod = 0; while ( cin >> x && x != -1) { mod = x ? one [mod] : zero [mod]; } cout << (mod == 0 ? "divisible by 3" : "NOT divisible by 3") ; return 0; }

Advertisements

Another approach:

#include

using namespace std;

int main()

{

int x, mod = 0;

while ( cin >> x && x != -1) {

mod = ((mod * 3) + x) % 3;

}

cout << (mod == 0 ? "divisible by 3" : "NOT divisible by 3") ;

return 0;

}

Comment by Igor Ostrovsky | August 28, 2011 |

@ronzii : Could you explain how to go about on such problems? The first thing that popped up in my head after I read this problem was to try to find a regular expression for all binary strings divisible by 3. Using the code that you’ve posted I could easily find the regular expression used but before that I spent about half an hour or so (in vain) to find a pattern in the binary strings divisible by 3. I came up with ( 0+ 1(01*0)*1 )* using your code though. How did you come up with the regular expression?

@Igor : I believe your code does not check divisibility by 3 but instead checks divisibility by 2.

–zingoba

Comment by Himanshu Sachdeva | September 21, 2011 |

@zingoba It’s given that there are only 0’s and 1’s hinting using something similar to DFA’s. I found out all states by a bit of hit and trial and some googling. Here is one of the links I found useful http://goo.gl/UWBJq

Comment by ronzii | September 21, 2011 |

If i enter 11 then it says “Divisible by 3”. Am i doing something wrong ?

Comment by Aamir Khan | October 9, 2011 |

The input is in binary. So 11 corresponds to 3.

Comment by ronzii | October 9, 2011 |

Oops..Got it.

Comment by Aamir Khan | October 9, 2011