@above...
The above explanation is based on the answer that i gave to the
following question asked:
Given an infinite stream of bits, at any given point of time u have
tell whether the no. formed by the bits sent till now is divisible by
3.
The catch in the above question is that you can't store the integral
value formed by the bit pattern. At any given point of time u will
only have the current bit. Hence, we need to preprocess the bits sent
to us and then generate the answer.
The same approach can be applied here..
2^0, 2^1 gives remainder 1 and 2(-1) when divided by 3.
Code:
int r[2]= {1,2};
int i =0;
While(there is an incoming bit X)
{
if(X&1)
{
currRem += r[i%2];
if (currRem >=3) currRem -=3;
}
++i;
}
-------------------------------------------------
Hence, the actual question can be changed saying that given an
infinite stream of bits, at any given point of time we need to figure
out whether its divisible by 5.
The above given code will work for this case as well.
On Jan 22, 12:19 pm, Lucifer <sourabhd2...@gmail.com> wrote:
> @another approach..
>
> The remainders when the following nos. are divided by 5 are :
> Numbers Remainder
> 2^0 1
> 2^1 2
> 2^2 4 (-1)
> 2^3 3 (-2)
>
> Now, we know that given a product of nos. a1, a2, ... aN when divided
> by a no. K, the remainder is:
> the product of (a1 mod K).... (aN mod K) i.e
>
> [ Lets call this as NumTheoProp1]
> a1* a2* a3*...*aN = x*K + (a1 mod K)*(a2 mod K)*....*(aN mod K)..
> [ the above can be proved by representing ai = xi * K + (ai mod K),
> and then multiplying all the ai's..]
>
> We can then recursively apply the same approach to the product of
> remainders until and unless the remainder is smaller than K.
> But a complete reduction into a value < K is not the point here. We
> are going to use the above fact for the following:
>
> Say, the given no. is 2^R ...
> Now, the above can be interpreted as,
> 2^R = 2^(4q) * 2^r, where R = 4q + r and 0<=r < 4
>
> Now we know that, 2^4 when divided by 5 gives a remainder 1..
>
> Hence applying the [NumTheoProp1] :
>
> 2^(4q) = (2^4)*(2^4)*... (q times)..
>
> when 2^(4q) = x*5 + (2^4 mod 5)^q..
> = x* 5 + 1..
>
> Hence,
> 2^R = 2^(4q) * 2^r
> = x*5 + (2^4q mod 5)*(2^r mod 5)
> = x*5 + (2^r mod 5)..
>
> Now, as 0<=r < 4, based on the remainder jolted at the starting..
> 2^r mod 5 = one of (1, 2, 4, 3)..
>
> But if you closely observe there is a pattern..
> For any no. 2^R where R>= 4 we can reduce it to 2^r where r < 4 by
> using [NumTheoProp1]
> Hence,
> No.( 2^r) Remainder
> 0 1
> 1 2
> 2 4
> 3 3
> 4 1
> 5 2
> 6 4
> 7 3
> .... and the cycle continues..
>
> Now. say a no. N is given, then it can be represented as,
> N = b0* (2^0) + b1* (2^1) + .... + bN* (2^logN)..
> where bi is either 0 or 1 [ basically it mimics the bit pattern)
>
> N mod 5 = ( [sum over all i ( (bi* (2^i)) mod 5 )] mod 5)
>
> Now, the inner mod 5 can be directly calculated based on the index of
> i (as there is a pattern). Btw it also depends on the value of bi. If
> bi =0, then the remainder will be 0 otherwise we will get the
> remainder based on the pattern..
>
> The outer mod 5, can be handled by following an incremental process,
> i.e whenever the current remainder becomes >=5 we will subtract 5 from
> it.
>
> Code:
>
> int N; // given number..
> int r[4] = {1, 2, 4, 3};
> int currRem = 0;
> int i = 0;
> while (N)
> {
> if (N&1)
> {
> currRem += r[i%4];
> if (currRem >=5)
> currRem -=5;
> }
> ++i;
> N >>= 1;}
>
> if ( currRem == 0)
> {
> printf("N is divisible by 5");
>
> }
>
> On Jan 22, 2:42 am, Dave <dave_and_da...@juno.com> wrote:
>
>
>
>
>
>
>
> > @Arun: Proof that n = 4*a + b is a multiple of 5 if and only if a - b
> > is a multiple of 5:
>
> > Given n, write it as n = 4*a + b where 0 <= b <= 3.
> > Note that 5*a is a multiple of 5, and 5*a - n = 5*a - (4*a + b) = a -
> > b.
> > If n is a multiple of 5, then 5*a - n is a multiple of 5, so a - b is
> > a multiple of 5.
> > Similarly if n is not a multiple of 5.
>
> > QED
>
> > Dave
>
> > On Jan 21, 11:57 am, Arun Vishwanathan <aaron.nar...@gmail.com> wrote:
>
> > > @dave: thanks for that..but i just wanted to know as to how u thot of
> > > converting n to a-b in the iteration. when u say 4a +b is a multiple of 5
> > > iff a-b is a muliple of 5 i was able to get that only when i tried an
> > > example...if they ask divisbility by 3 or 6 or 7 how wud the logic
> > > change??
>
> > > On Sat, Jan 21, 2012 at 9:34 AM, karthikeyan muthu <
>
> > > keyankarthi1...@gmail.com> wrote:
> > > > check the last char ... it should be 0 or 5 , int to string without mod
>
> > > > On Sat, Jan 21, 2012 at 10:05 PM, Dave <dave_and_da...@juno.com> wrote:
>
> > > >> @Karthikeyan: Is this supposed to relate to the question of
> > > >> determining divisibility by 5?
>
> > > >> Dave
>
> > > >> On Jan 21, 9:25 am, karthikeyan muthu <keyankarthi1...@gmail.com>
> > > >> wrote:
> > > >> > @dave
>
> > > >> > int no=10;
> > > >> > char ans[100];
> > > >> > sprintf(ans,"%d",no);
> > > >> > cout<<ans;
>
> > > >> > On Fri, Jan 20, 2012 at 10:29 PM, Arun Vishwanathan
> > > >> > <aaron.nar...@gmail.com>wrote:
>
> > > >> > > @dave or anyone: can u pls explain the logic of n&3 in dave's
> > > >> solution?
> > > >> > > why is it subtracted from n(which is divided by 4 using >>2) and
> > > >> > > what
> > > >> does
> > > >> > > n& 3 indicate?
>
> > > >> > > On Sat, May 7, 2011 at 9:38 AM, Dave <dave_and_da...@juno.com>
> > > >> > > wrote:
>
> > > >> > >> @Umer: Do you suppose that you can convert an int into a string
> > > >> > >> without using division or mod, either directly or indirectly?
>
> > > >> > >> Dave
>
> > > >> > >> On May 4, 1:12 am, Umer Farooq <the.um...@gmail.com> wrote:
> > > >> > >> > 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- 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.
>
> > > >> > > --
> > > >> > > "People often say that motivation doesn't last. Well, neither does
> > > >> > > bathing - that's why we recommend it daily."
>
> ...
>
> read more »
--
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.
