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