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 <ecstasy.piy...@gmail.com> 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 <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. > > -- 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 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.
