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 <sud.nit...@gmail.com> wrote: > use automata theory. draw dfa for divisibility by 3.. > > On Tue, Jul 19, 2011 at 11:23 PM, siva viknesh > <sivavikne...@gmail.com>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 algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
