I'm surprised to see that why are you guys making this problem so complex.
This problem can be solved in two steps only.
1- Convert the given int into string
2- Check if the last character is 0 or 5. // it yes, then return true else
return false
for e.g.
125 (last character is 5 ... therefore it is divisible by 5)
120 (last character is 0 ... therefore it is divisible by 5)
111 (last character is 1 ... therefore it is not divisible by 5)
The pseudo-code has been written in my above email.
On Wed, May 4, 2011 at 1:49 AM, Dave <dave_and_da...@juno.com> wrote:
> @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.
>
>
--
Umer
--
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.
