good solution On Wed, Jul 20, 2011 at 6:23 PM, ~*~VICKY~*~ <[email protected]>wrote:
> @Deepthi: Thanks a lot :) > > > On Wed, Jul 20, 2011 at 11:33 AM, Deepthi Srinivasan > <[email protected]>wrote: > >> @Vicky >> Piyush's algo is based on a little trick to determine divisibility by 3. >> Number of bits set in odd position - Number of bits set in even position 'll >> be divisible by 3 >> For example, take 9. 1001. No. of bits set in odd position - number of >> bits set in even position is 0. Hence divisible by 3. >> For 21, 10101. Difference is 3.. SO just keep count of the number of bits >> set in odd position and even position as the stream >> progresses and ur done... >> >> >> On Tue, Jul 19, 2011 at 10:35 PM, SAMM <[email protected]> wrote: >> >>> 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. >>> >>> >> -- >> 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. > -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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.
