@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.
