Ronzii's Blog

Just your average geek's blog

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

July 31, 2011 - Posted by | C++ |

6 Comments »

  1. 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 | Reply

  2. @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 | Reply

  3. @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 | Reply

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

    Comment by Aamir Khan | October 9, 2011 | Reply

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

      Comment by ronzii | October 9, 2011 | Reply

      • Oops..Got it.

        Comment by Aamir Khan | October 9, 2011


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s