@anshu: Spoiler alert... I was thinking of something more along the
line
int DivisibleBy5 (int n)
{
n = n > 0 ? n : -n;
while( n > 0 )
n = (n >> 2) - (n & 3);
return (n == 0);
}
To see that it works, write n as n = 4*a + b, where 0 <= b <= 3. Then
the iteration replaces n by a - b. Consider (4*a + b) + (a - b), the
sum of two consecutive values of n. This simplifies to 5*a, which is a
multiple of 5. Thus, n is a multiple of 5 before an iteration if and
only if it also is a multiple of 5 afterwards,
It is clearly log n because n is replaced by a number no greater than
n/4 on each iteration.
Examples:
n = 125. The sequence of iterates is 30, 5, 0. Ergo, 125 is a multiple
of 5.
n = 84. The sequence of iterates is 21, 4, -1. Ergo, 84 is not a
multiple of 5.
Dave
On May 3, 3:13 am, anshu <[email protected]> wrote:
> algorithm:
>
> if any number(a) is divisible by 5 it can be wriiten as 4*b + b -->
> this cleary shows the last two bit of a & b will be same.
>
> lets understand by an example (35)10 = (100011)2
>
> xx1100
> + xx11
> ---------
> 100011
>
> now this clearly shows we can calculate the unknowns(x) by traversing
> right to left
>
> code:
>
> int main()
> {
> int n, m;
> cin >> n;
> m = n;
>
> int a, b;
> int i=2;
>
> a = (m&3)<<2;
> b = (m&3);
> m >>= 2;
>
> bool rem = 0,s,r;
>
> while (m>3)
> {
> r = a&(1<<i);
> s = r^(m&1)^rem;
> b = b|(s<<i);
> a = a|(s<<(i+2));
> rem = (r&s)|(s&rem)|(r&rem) ;
> i++;
> m >>= 1;
> }
>
> if (a+b == n) cout << "yes\n";
> else cout << "no\n";
>
> return 0;
>
>
>
> }- Hide quoted text -
>
> - Show quoted text -
--
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.
