Richa,
Did you see http://geeksforgeeks.org/?p=511
I think, above link provides the kind of solution you are looking for
On Thu, Aug 20, 2009 at 11:33 PM, Ralph Boland <rpbol...@gmail.com> wrote:
>
>
>
> On Aug 16, 7:29 pm, Ralph Boland <rpbol...@gmail.com> wrote:
> > On Aug 14, 1:45 am, richa gupta <richa.cs...@gmail.com> wrote:
> >
> > > can we check the divisibility of a given number by 3 withoutusing
> > > operators like '/' or '%'.
> > > I want the efficient solution to this problem ..
> >
> > > can someone help ??
> > > --
> > > Richa Gupta
> > > (IT-BHU,India)
> >
> > If the number is an arbitrarily large binary number then
> > 0) Let X be the input number.
> > 1) Add the binary values of each byte of X. Let result be X.
> > 2) If X > 255 goto step 1).
> > 3) Look up the answer in a table or
> > b1) treat X as a base 16 number and add digits. Let the
> > result be X.
> > b2) if X > 16 go to step b1.
>
> 16 should be 15 here. That is: if X > 15 go to step b1.
>
> > b3) The original number is divisible by 3 IFF X is
> > divisible by 3 (X in {0,3,6,9,12,15}).
> >
>
> Note that the rule of 3s and the rule of 9s for decimal numbers is be
> being
> applied here but for the the number 255 and its factors; that is
> 3, 5, 15, 17, 51, and 85.
> It works for the same reason that the rule of 9's (and its factor
> rules; i.e.
> rule of 3's) works for decimal numbers.
> We could call these rules for base 256 numbers
> the rule of 3s base 256, the rule of 5's base 256, the rule of 15's
> base 256 etc.
>
> > The above algorithm can be modified to use 16 bit numbers or 32 bit
> > numbers instead of bytes.
>
> For 16 bit numbers for the digit base the method can be applied
> to factors of 2^16 -1, that is 3,5,17, and 257.
>
> However step 3 cannot be applied to 17 or 257.
> For 32 bit numbers you have the additional factor 2^16 + 1 (and the
> numbers in its prime factorization but unfortunately 2^ 16 + 1 is
> prime).
>
> > It can also be modified to determine if the input number is divisible
> > by 5,6,7,9,12, 14, or 15.
>
> To do digits 7 or 9 one has to use base 64 digits instead of base
> 256.
> (7 * 9 = 63 = 64 - 1).
> > I believe divisibility by 13 can also be done but a different
> > algorithm is needed.
>
> >
> > Ralph Boland
>
> Ralph Boland
> >
>
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
