CareerCup

Suppose we have to divide a number ie 1279 by 3. we get 1279 as streams ..first i get 1 ..1%3=1..1 is stored in rem.Now 2 comes, we do rem=(1*10+2)%3=0.Now 7 is in teh stream,
rem=(rem*10+7)%3=1, when 9 comes rem=(1*10+9)%3=1. So we get at each step where the stream entered till that place is divisible by three or not.
Same is the case when stream cotains 0 and 1.Insteam of multiplying the rem by 10, multiply by 2.

//
// main.c
// DivisibleBy3
//
// Created by Srikant Aggarwal on 07/12/11.
// Copyright 2011 NSIT. All rights reserved.
//

#include <stdio.h>

int getBits()
{
int bit;
scanf("%d", &bit);
return bit;
}

int main (int argc, const char * argv[])
{
int rem = 0;
int bit;

while(1)
{
bit = getBits();

rem = ((rem << 1) + bit)%3;

if(rem == 0)
printf("\n Divisible by 3 \n");
else
printf("\n Not divisible by 3 \n");
};

}

we have to just count the number of 1's (set bits) at even position and number of 1's (set bits) at odd position .

if((number of 1's at even position - number of 1's at odd position)%3==0)
then number is divisible by 3.

every time number obtained till now is getting left shifted by 1 bit and a new bit is getting added.

Therefore,

here is the code:
{{
int input =0; // to srore a bit either 0 or 1
int num=0; // to store the number formed using bit received till now.

while(true){
scanf("%d",&input);
num=num<<1;
if(input==1){
num=num+1;
}
}

}}

#include<stdio.h>
#include<conio.h>

void driver()
{
	int oddcount = 0;
	int evencount = 0;
	int i;
	char c;
	int temp = 0;
	while(1)
	{
		c = getch();
		putchar(c);
		if(c < '0' || c > '1')
			break;
		i = c - '0';
		temp = oddcount;
		oddcount = evencount;
		evencount = temp;
		if(i)
			oddcount++;
		if(oddcount == evencount)
			printf("\ny");

		else
			printf("\nn");
	}
}
void main()
{
	driver();
}

Logic is to keep a count of the number of ones in even position and number of ones in odd positions, if at any moment, they are equal, then the number is divisible by 3. tricky part is keep swapping the odd count and even count as each arrived bit actually changes the previous bits from odd to even and from even to odd

one way will be generating FSM .
else
for the given stream , generate the decimal counter part . How to generate from MSB is

if the current bit is "1" , then multiply the value till this instant with 2 aand add 1 , else , if that is 0 just multiply by 2.
ex:
1101
from MSB .
first bit(1) : 1
currentVal = 1;
second bit 2 (1):
current val = currentVal*2+1 .. //currentVal = 3;
third bit (0):
currentVal = currentVal*2; // currentVal = 6;
fourth bit (1) :
currentVal = currentVal*2+1 ; //currentVal = 13.
now as the num is in decimal , can find easily whether it is divisible by any required number (in our case , it is 3) .

Assuming the number initially is 0.
int i=0;
if(incoming_bit==1)
i=(2*i+1)%3;
if(i==0)
Number is divisible by 3


If at any time resultant number is divisible by 3 and incoming bit is 0 the resultant number will still be divisible by 3
But if the incoming bit is 1 we check the variable i.

it is similar to check a decimal number divisibility by 11(which is 10+1).
For checking decimal number divisibility by 11 you do a diference of sum on even and odd places and if the difference is divisible by 11 then the number is divisible by 11.
Same way checking divisibility by 3(2+1) can be done by same way checking the dofference of sums at even and odd places to be divisible by 3.

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

3x moves to 3x+1 if 1 comes and stays in 3x if 0 comes in the stream
3x+1 moves to 3x if 1 comes and moves to 3x+2 if 0 comes in the stream
3x+2 moves to 3x+1 if 0 comes and stays in 3x+2 if 1 comes

Initial states can be
3x if 0 comes (first in the stream)
3x+1 if 1 comes (first in the stream)

This way we will need minimum computation and works with the stream. Only condition is that initial stages should not mess up.

Solution of 'difference between sum of odd and even bits divisble by 3' is correct
However its not scalable. So if i change problem to find out if its divisible by 7, we need to rework. So we should think about scale machine kind of solution.

Here is my understanding.
lets always store the remainder. and when new bits arrive shift remainder left and put new bit at lsb. if this is divisible by 3, signal it out, divide this number by 3, keep the remainder, wait for next bit.

Now i just notice, code for this is posted by srikant aggarwal (thanks to you sir.)
that code will work for any number 3 or 2300 (as long as an 'int' can hold it).

rem = ((rem << 1) + bit)%3;

this piece of code can be replaced by

if (rem)
{
if(bit)
{ rem = 0; }
else
{ rem = 1; }
}
else

rem = bit ;

Y dont u use a linked list and keep on mutlipying 2 to evry bit occured and add it to the sum obtained before a node is added

I think for getting a number divisible by three in binary...juss the number of 1's in it..if these are even then divisible by 3 else not....

int ans(0);
     while (cin >> n)
     {
          ans = mod(ans*2, 3);
          ans = mod(ans + n, 3);
          cout << (ans ? "NO" : "YES" ) << endl;
     }

public static void main(String args[]) throws Exception {
		computeDecimal("10111111000111111111111111111111111");
	}

	public static void computeDecimal(String binary) {
		long binLen = binary.length();
		long decLen = (int) Math.ceil(Math.log(binLen) / Math.log(2))+4;
		char elems[] = binary.toCharArray();
		long sum = 0;
		long mod = 0;
		for (int i = elems.length - 1; i >= 0; i--) {
			long temp = ((long) (Math.pow(2, elems.length - 1 - i) * Integer.parseInt("" + elems[i])));
			sum = sum + temp;
			mod = (mod + (temp % 3)) % 3;
			System.out.printf("Decimal = %" + decLen + "d Binary = %" + binLen + "s Reminder = %d\n", sum, binary.substring(i), mod);
		}
	}