On Aug 14, 1:45 am, richa gupta <[email protected]> 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.
b3) The original number is divisible by 3 IFF X is
divisible by 3 (X in {0,3,6,9,12,15}).
The above algorithm can be modified to use 16 bit numbers or 32 bit
numbers instead of bytes.
It can also be modified to determine if the input number is divisible
by 5,6,7,9,12, 14, or 15.
I believe divisibility by 13 can also be done but a different
algorithm is needed.
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 [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
-~----------~----~----~----~------~----~------~--~---
