find the difference between the set bits in the odd and even position, if this diff is divisible by 3, then it is the multiple of 3..
On 7/20/11, ~*~VICKY~*~ <[email protected]> wrote: > @Piyush Sinha: > > Can u plz state an example? I don get ur algo > > On Wed, Jul 20, 2011 at 12:52 AM, SAMM <[email protected]> wrote: > >> The above method is good , I was going to suggest another algo it >> takes the same complexity but lengthy so I am not posting my algo... >> >> On 7/19/11, Piyush Sinha <[email protected]> wrote: >> > Divisibility of 3 of numbers in base 2 can be seen same as >> > divisibility of numbers by 11 in base 10... >> > >> > maintain two variable even_sum & odd_sum, both initialized to 0 >> > >> > when an odd location in the number is set increment odd_sum >> > when an even location in the number is set increment even_sum >> > >> > if(abs(even_sum-odd_sum)%3==0) number is divisible by 3... >> > >> > Hence keep the track of even_sum and odd_sum as the bits are getting >> > appended.. >> > >> > Hope I am clear... :) >> > >> > On 7/19/11, sudhanshu pandey <[email protected]> wrote: >> >> use automata theory. draw dfa for divisibility by 3.. >> >> >> >> On Tue, Jul 19, 2011 at 11:23 PM, siva viknesh >> >> <[email protected]>wrote: >> >> >> >>> Given an infinite stream of bits with bits being appended at the >> >>> highest significant position. Give an algorithm to say whether the >> >>> number formed by sequence of bits that had been processed till then , >> >>> is divisible by 3 or not ? >> >>> >> >>> >> >>> My sol: >> >>> >> >>> have a variable sum.......find the sum of bits....whenever u add a bit >> >>> do sum+="bit value" ... check whether sum%3==0..... >> >>> ....Is my solution ok?? anyother good solutions ?? >> >>> >> >>> -- >> >>> You received this message because you are subscribed to the Google >> Groups >> >>> "Algorithm Geeks" group. >> >>> To post to this group, send email to [email protected]. >> >>> To unsubscribe from this group, send email to >> >>> [email protected]. >> >>> For more options, visit this group at >> >>> http://groups.google.com/group/algogeeks?hl=en. >> >>> >> >>> >> >> >> >> >> >> -- >> >> SUDHANSHU PANDEY >> >> >> >> --only fair thing in this world is a chance-- >> >> >> >> -- >> >> You received this message because you are subscribed to the Google >> Groups >> >> "Algorithm Geeks" group. >> >> To post to this group, send email to [email protected]. >> >> To unsubscribe from this group, send email to >> >> [email protected]. >> >> For more options, visit this group at >> >> http://groups.google.com/group/algogeeks?hl=en. >> >> >> >> >> > >> > >> > -- >> > *Piyush Sinha* >> > *IIIT, Allahabad* >> > *+91-7483122727* >> > * <https://www.facebook.com/profile.php?id=100000655377926> "NEVER SAY >> > NEVER" >> > * >> > >> > -- >> > You received this message because you are subscribed to the Google >> > Groups >> > "Algorithm Geeks" group. >> > To post to this group, send email to [email protected]. >> > To unsubscribe from this group, send email to >> > [email protected]. >> > For more options, visit this group at >> > http://groups.google.com/group/algogeeks?hl=en. >> > >> > >> >> >> -- >> Somnath Singh >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > Cheers, > > Vicky > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Somnath Singh -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
