@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 <anshumishra6...@gmail.com> 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 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?hl=en.