[algogeeks] Re: Divisibility by five

[Lucifer]

@another approach..

The remainders when the following nos. are divided by 5 are :
Numbers   Remainder
2^01
2^12
2^24 (-1)
2^33 (-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  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  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  wrote:
>
> > >> @Karthikeyan: Is this supposed to relate to the question of
> > >> determining divisibility by 5?
>
> > >> Dave
>
> > >> On Jan 21, 9:25 am, karthikeyan muthu 
> > >> wrote:
> > >> > @dave
>
> > >> > int no=10;
> > >> > char ans[100];
> > >> > sprintf(ans,"%d",no);
> > >> > cout<
> > >> > On Fri, Jan 20, 2012 at 10:29 PM, Arun Vishwanathan
> > >> > 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  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  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 ... theref

[algogeeks] KMP Failure Function Problem

[Sanjay Rajpal]

Below is the code for KMP failure function :

int F[]; //assume F is a global arary.
int Fill-Prefix-Table(int P[], int m)
{
int i,j;
F[0]=0;
j=0;
i=1;
while(i < m)
{
if(P[i] == P[j])
{
  F[i]=j+1;
  i++;
  j++;
}
else if(j > 0)
{
  j = F[j-1];
}
else
{
 F[i]=0;
 i++;
}
}
}

In the above function,

in the "else if" case, why is it j = F[j-1] ? Plz explain with an example..

Thanx in advance :)
*
*

-- 
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.

Re: [algogeeks] segment tree

[arun kumar]

this link deal with applying lazy propagation for the problem LITE in spoj.
hope this one help you
http://apps.topcoder.com/forums/?module=Thread&threadID=690098&messageID=1298729&mc=8&view=tree#1298729
regards
arun

On Sat, Jan 21, 2012 at 6:10 PM, UTKARSH SRIVASTAV
wrote:

> Hi can anyone please give a good link to study lazy propagation in segment
> tree with example or code. I know segment tree but not about lazy
> propagation.
>
> --
> *UTKARSH SRIVASTAV
> CSE-3
> B-Tech 3rd Year
> @MNNIT ALLAHABAD*
>
>
>  --
> 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.
>

-- 
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.

Re: [algogeeks] Re: vertical level sum in Binary tree

[Arun Vishwanathan]

no jst thinking if any practical application of this sort of thing..:)

On Sat, Jan 21, 2012 at 3:11 PM, UTKARSH SRIVASTAV
wrote:

> why arun?
>
>
> On Sun, Jan 22, 2012 at 1:44 AM, Arun Vishwanathan  > wrote:
>
>> my god why do companies question like this???
>>
>>
>> On Sat, Jan 21, 2012 at 4:10 AM, UTKARSH SRIVASTAV <
>> usrivastav...@gmail.com> wrote:
>>
>>> yes atul I wanted to say only that may be not able to convey it . n is
>>> maximum number of vertical lines sum that you can calculate
>>>
>>> On 1/21/12, atul anand  wrote:
>>> > @ UTKARSH : how will you calculate number of vertical lines before
>>> passing
>>> > it to vsum().
>>> >
>>> > i guess n should be max(no. of nodes to the extreme left from the root
>>> ,
>>> > no. of nodes to the extreme right from root)
>>> >
>>> > On Fri, Jan 20, 2012 at 10:35 PM, UTKARSH SRIVASTAV <
>>> usrivastav...@gmail.com
>>> >> wrote:
>>> >
>>> >> void vsum(struct  node *p ,int i)
>>> >> {
>>> >> if(p)
>>> >> {
>>> >> sum[i] = sum[i] + p->data;
>>> >> vsum(p->left,i-1);
>>> >> vsum(p->right,i+1);
>>> >> }
>>> >> }
>>> >>
>>> >> construct an array of int sum[n] where n will be maximum no. of
>>> vertical
>>> >> lines and call vsum with vsum(root,n/2)
>>> >>
>>> >>
>>> >> On Fri, Jan 20, 2012 at 9:06 PM, sravanreddy001
>>> >> wrote:
>>> >>
>>> >>> what does it mean.. we cannot use an array? (a static array?)
>>> >>>
>>> >>> a vector is an array..but a dynamic one... what other DS can be
>>> used? a
>>> >>> linked list allowed?
>>> >>>
>>> >>> (each of the two algorithms can be mate to work with linked list
>>> too...
>>> >>> (except that it takes more time.. )
>>> >>>
>>> >>>  --
>>> >>> You received this message because you are subscribed to the Google
>>> Groups
>>> >>> "Algorithm Geeks" group.
>>> >>> To view this discussion on the web visit
>>> >>> https://groups.google.com/d/msg/algogeeks/-/GN5SzfqtYlgJ.
>>> >>>
>>> >>> 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.
>>> >>>
>>> >>
>>> >>
>>> >>
>>> >> --
>>> >> *UTKARSH SRIVASTAV
>>> >> CSE-3
>>> >> B-Tech 3rd Year
>>> >> @MNNIT ALLAHABAD*
>>> >>
>>> >>
>>> >>  --
>>> >> 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.
>>> >>
>>> >
>>> > --
>>> > 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.
>>> >
>>> >
>>>
>>>
>>> --
>>> *UTKARSH SRIVASTAV
>>> CSE-3
>>> B-Tech 3rd Year
>>> @MNNIT ALLAHABAD*
>>>
>>> --
>>> 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."
>>
>>  --
>> 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.
>>
>
>
>
> --
> *UTKARSH SRIVASTAV
> CSE-3
> B-Tech 3rd Year
> @MNNIT ALLAHABAD*
>
>
>  --
> 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."

-- 
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://g

Re: [algogeeks] Re: vertical level sum in Binary tree

[UTKARSH SRIVASTAV]

why arun?

On Sun, Jan 22, 2012 at 1:44 AM, Arun Vishwanathan
wrote:

> my god why do companies question like this???
>
>
> On Sat, Jan 21, 2012 at 4:10 AM, UTKARSH SRIVASTAV <
> usrivastav...@gmail.com> wrote:
>
>> yes atul I wanted to say only that may be not able to convey it . n is
>> maximum number of vertical lines sum that you can calculate
>>
>> On 1/21/12, atul anand  wrote:
>> > @ UTKARSH : how will you calculate number of vertical lines before
>> passing
>> > it to vsum().
>> >
>> > i guess n should be max(no. of nodes to the extreme left from the root ,
>> > no. of nodes to the extreme right from root)
>> >
>> > On Fri, Jan 20, 2012 at 10:35 PM, UTKARSH SRIVASTAV <
>> usrivastav...@gmail.com
>> >> wrote:
>> >
>> >> void vsum(struct  node *p ,int i)
>> >> {
>> >> if(p)
>> >> {
>> >> sum[i] = sum[i] + p->data;
>> >> vsum(p->left,i-1);
>> >> vsum(p->right,i+1);
>> >> }
>> >> }
>> >>
>> >> construct an array of int sum[n] where n will be maximum no. of
>> vertical
>> >> lines and call vsum with vsum(root,n/2)
>> >>
>> >>
>> >> On Fri, Jan 20, 2012 at 9:06 PM, sravanreddy001
>> >> wrote:
>> >>
>> >>> what does it mean.. we cannot use an array? (a static array?)
>> >>>
>> >>> a vector is an array..but a dynamic one... what other DS can be used?
>> a
>> >>> linked list allowed?
>> >>>
>> >>> (each of the two algorithms can be mate to work with linked list
>> too...
>> >>> (except that it takes more time.. )
>> >>>
>> >>>  --
>> >>> You received this message because you are subscribed to the Google
>> Groups
>> >>> "Algorithm Geeks" group.
>> >>> To view this discussion on the web visit
>> >>> https://groups.google.com/d/msg/algogeeks/-/GN5SzfqtYlgJ.
>> >>>
>> >>> 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.
>> >>>
>> >>
>> >>
>> >>
>> >> --
>> >> *UTKARSH SRIVASTAV
>> >> CSE-3
>> >> B-Tech 3rd Year
>> >> @MNNIT ALLAHABAD*
>> >>
>> >>
>> >>  --
>> >> 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.
>> >>
>> >
>> > --
>> > 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.
>> >
>> >
>>
>>
>> --
>> *UTKARSH SRIVASTAV
>> CSE-3
>> B-Tech 3rd Year
>> @MNNIT ALLAHABAD*
>>
>> --
>> 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."
>
>  --
> 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.
>



-- 
*UTKARSH SRIVASTAV
CSE-3
B-Tech 3rd Year
@MNNIT ALLAHABAD*

-- 
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.

[algogeeks] Re: Divisibility by five

[Dave]

@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  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  wrote:
>
> >> @Karthikeyan: Is this supposed to relate to the question of
> >> determining divisibility by 5?
>
> >> Dave
>
> >> On Jan 21, 9:25 am, karthikeyan muthu 
> >> wrote:
> >> > @dave
>
> >> > int no=10;
> >> > char ans[100];
> >> > sprintf(ans,"%d",no);
> >> > cout<
> >> > On Fri, Jan 20, 2012 at 10:29 PM, Arun Vishwanathan
> >> > 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  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  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 
> >> 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  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< >> > >> > > >                 s = r^(m&1)^rem;
> >> > >> > > >                 b = b|(s< >> > >> > > >                 a = a|(s<<(i+2));
> >> > >> > > >                 rem = (r&s)|(s&rem)|(r&rem) ;
> >> > >> > > >                 i++;
> >> > >> > > >                 m >>= 1;
> >> > >> > > >         }
>
> >> > >> > > >         if (a+b == n) cout << "yes\n";
> >> > >>

[algogeeks] Re: Divisibility by five

[Dave]

@Arun: Some time ago, there was a question about determining
divisibility by 3. I thought about determining divisibility of decimal
numbers by 9 using the "casting out nines" procedure: sum the decimal
digits of the number; the number is divisible by 9 if the sum of the
digits is divisible by 9. Casting out nines works because 9 is one
less than the base of the decimal number system. Since we can
translate binary numbers to base 4 just by grouping adjacent pairs of
bits, I came up with the algorithm for divisibility by 3 that I posted
in http://groups.google.com/group/algogeeks/msg/a4894e12805381ca.

To make that algorithm look more like my divisibility by 5 algorithm
posted earlier in this string, rewrite it as

int DivisibileBy3(int n)
{
n = n > 0 ? n : -n;
while(n>3)
n = (n>>2) + (n & 3);
return n == 3 || n == 0;
}

So if divisibility by 3 (= 4-1) is as above, I thought maybe
divisibility by 5 (= 4+1) might be related. I tried it and it works!

Divisibility by 7: change the 3's above to 7's and  the 2 above to 3.

Divisibility by 11 would be more difficult.

Dave

On Jan 21, 11:57 am, Arun Vishwanathan  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  wrote:
>
> >> @Karthikeyan: Is this supposed to relate to the question of
> >> determining divisibility by 5?
>
> >> Dave
>
> >> On Jan 21, 9:25 am, karthikeyan muthu 
> >> wrote:
> >> > @dave
>
> >> > int no=10;
> >> > char ans[100];
> >> > sprintf(ans,"%d",no);
> >> > cout<
> >> > On Fri, Jan 20, 2012 at 10:29 PM, Arun Vishwanathan
> >> > 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  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  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 
> >> 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  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;
> >> > >> >

[algogeeks] Re: Divisibility by five

[Dave]

@Karthikeyan: Again I ask: Do you think that you have used neither
division nor mod indirectly? I.e., can you assert with certainty that
there is no division or mod in sprintf() or anything it calls? I
didn't think so. In fact, I am willing to assert with certainty that
division is used, since the algorithms for converting binary integers
into base 10 use division by 10.

Dave

On Jan 21, 11:34 am, karthikeyan muthu 
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  wrote:
> > @Karthikeyan: Is this supposed to relate to the question of
> > determining divisibility by 5?
>
> > Dave
>
> > On Jan 21, 9:25 am, karthikeyan muthu 
> > wrote:
> > > @dave
>
> > > int no=10;
> > > char ans[100];
> > > sprintf(ans,"%d",no);
> > > cout<
> > > On Fri, Jan 20, 2012 at 10:29 PM, Arun Vishwanathan
> > > 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  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  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 
> > 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  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< > > >> > > >                 s = r^(m&1)^rem;
> > > >> > > >                 b = b|(s< > > >> > > >                 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...@googlegroup

Re: [algogeeks] Re: vertical level sum in Binary tree

[Arun Vishwanathan]

my god why do companies question like this???

On Sat, Jan 21, 2012 at 4:10 AM, UTKARSH SRIVASTAV
wrote:

> yes atul I wanted to say only that may be not able to convey it . n is
> maximum number of vertical lines sum that you can calculate
>
> On 1/21/12, atul anand  wrote:
> > @ UTKARSH : how will you calculate number of vertical lines before
> passing
> > it to vsum().
> >
> > i guess n should be max(no. of nodes to the extreme left from the root ,
> > no. of nodes to the extreme right from root)
> >
> > On Fri, Jan 20, 2012 at 10:35 PM, UTKARSH SRIVASTAV <
> usrivastav...@gmail.com
> >> wrote:
> >
> >> void vsum(struct  node *p ,int i)
> >> {
> >> if(p)
> >> {
> >> sum[i] = sum[i] + p->data;
> >> vsum(p->left,i-1);
> >> vsum(p->right,i+1);
> >> }
> >> }
> >>
> >> construct an array of int sum[n] where n will be maximum no. of vertical
> >> lines and call vsum with vsum(root,n/2)
> >>
> >>
> >> On Fri, Jan 20, 2012 at 9:06 PM, sravanreddy001
> >> wrote:
> >>
> >>> what does it mean.. we cannot use an array? (a static array?)
> >>>
> >>> a vector is an array..but a dynamic one... what other DS can be used? a
> >>> linked list allowed?
> >>>
> >>> (each of the two algorithms can be mate to work with linked list too...
> >>> (except that it takes more time.. )
> >>>
> >>>  --
> >>> You received this message because you are subscribed to the Google
> Groups
> >>> "Algorithm Geeks" group.
> >>> To view this discussion on the web visit
> >>> https://groups.google.com/d/msg/algogeeks/-/GN5SzfqtYlgJ.
> >>>
> >>> 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.
> >>>
> >>
> >>
> >>
> >> --
> >> *UTKARSH SRIVASTAV
> >> CSE-3
> >> B-Tech 3rd Year
> >> @MNNIT ALLAHABAD*
> >>
> >>
> >>  --
> >> 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.
> >>
> >
> > --
> > 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.
> >
> >
>
>
> --
> *UTKARSH SRIVASTAV
> CSE-3
> B-Tech 3rd Year
> @MNNIT ALLAHABAD*
>
> --
> 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."

-- 
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.

[algogeeks] Re: algo qstn

[sravanreddy001]

@Don, Jaimedp:

the value here is not 1018, but its pow(10,18) and this will take for 
ever.. on a system.
its something to do with some short cut logic and not from a code point of 
view.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/ZEdfelAgVcUJ.
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.

Re: [algogeeks] Re: Divisibility by five

[Arun Vishwanathan]

@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  wrote:
>
>> @Karthikeyan: Is this supposed to relate to the question of
>> determining divisibility by 5?
>>
>> Dave
>>
>> On Jan 21, 9:25 am, karthikeyan muthu 
>> wrote:
>> > @dave
>> >
>> > int no=10;
>> > char ans[100];
>> > sprintf(ans,"%d",no);
>> > cout<> >
>> > On Fri, Jan 20, 2012 at 10:29 PM, Arun Vishwanathan
>> > 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  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  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 
>> 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  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<> > >> > > > s = r^(m&1)^rem;
>> > >> > > > b = b|(s<> > >> > > > 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 t

Re: [algogeeks] Re: Divisibility by five

[karthikeyan muthu]

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  wrote:

> @Karthikeyan: Is this supposed to relate to the question of
> determining divisibility by 5?
>
> Dave
>
> On Jan 21, 9:25 am, karthikeyan muthu 
> wrote:
> > @dave
> >
> > int no=10;
> > char ans[100];
> > sprintf(ans,"%d",no);
> > cout< >
> > On Fri, Jan 20, 2012 at 10:29 PM, Arun Vishwanathan
> > 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  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  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 
> 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  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< > >> > > > s = r^(m&1)^rem;
> > >> > > > b = b|(s< > >> > > > 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/algog

Re: [algogeeks] c++_Output

[priyanka jaggi]

i=i++ + ++i;
j++ + ++j;
k=k++ + k++ + ++k;

All these Statements have compiler Dependent Output, As they violet
sequence point rule ( here value of a variable is modified two or more
times between two successive sequence points.)
Standard does not specify the exact order of execution of these type
of statements.




On Sat, Jan 21, 2012 at 5:12 PM, Kailash Bagaria
 wrote:
>
> Please explain the output of the following program
>
> #include 
> using namespace std;
> int main()
> {
>     int i=5;
>     i=i++ + ++i;
>     cout<
>     int j=5;
>     cout<
>     int k=5;
>     k=k++ + k++ + ++k;
>     cout<
>     system("pause");
>     return 0;
> }
> --
>
> --
>
> ‘Kailash Bagaria’
> B-tech 3rd year
> Computer Science & Engineering
> Indian Institute of Technology, Roorkee
> Roorkee, India (247667)
>
>
> --
> 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.

-- 
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.

[algogeeks] Re: c++_Output

[Dave]

@Kailash: The code violates the sequence point rule, which says that
you may not change the value of a variable more than once between
sequence points. The result is compiler dependent.

Dave

On Jan 21, 5:42 am, Kailash Bagaria 
wrote:
> Please explain the output of the following program
>
> #include 
> using namespace std;
> int main()
> {
>     int i=5;
>     i=i++ + ++i;
>     cout<
>     int j=5;
>     cout<
>     int k=5;
>     k=k++ + k++ + ++k;
>     cout<
>     system("pause");
>     return 0;}
>
> --
>
> --
>
> ‘Kailash Bagaria’
> B-tech 3rd year
> Computer Science & Engineering
> Indian Institute of Technology, Roorkee
> Roorkee, India (247667)

-- 
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.

[algogeeks] Re: Divisibility by five

[Dave]

@Karthikeyan: Is this supposed to relate to the question of
determining divisibility by 5?

Dave

On Jan 21, 9:25 am, karthikeyan muthu 
wrote:
> @dave
>
> int no=10;
> char ans[100];
> sprintf(ans,"%d",no);
> cout<
> On Fri, Jan 20, 2012 at 10:29 PM, Arun Vishwanathan
> 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  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  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  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  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< >> > > >                 s = r^(m&1)^rem;
> >> > > >                 b = b|(s< >> > > >                 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."
>
> >  --
> > 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 t

[algogeeks] Re: Divisibility by five

[Dave]

@Arun: (n & 3) is the bitwise logical product of the integer n and the
binary number 0...0011. The result simply is the two low-order bits of
n. I.e., if n = 0...011100110 in binary, then (n & 3) is 0...010 in
binary, because the two lowest order bits of n are 1 and 0.

There is an explanation of why the code works in
http://groups.google.com/group/algogeeks/msg/5fd29d9458057f9f. In that
explanation, n is written in the form 4*a + b. (n >> 2) gives a, and
(n & 3) gives b. So we start with n and produce (a - b), which is a
multiple of 5 if and only if n is a multiple of 5.

Dave

On Jan 20, 10:59 am, Arun Vishwanathan  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  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  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  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  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< > > > >                 s = r^(m&1)^rem;
> > > > >                 b = b|(s< > > > >                 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."

-- 
You received this message because you are subscribed to the Google

Re: [algogeeks] Re: google questions

[Arun Vishwanathan]

@all: how is the problem solved using a heap...can someone explain. did not
understand what was on the net...

On Thu, Feb 3, 2011 at 2:23 AM, Avik Mitra  wrote:

> I am proposing a solution for problem 2..
> >2.
> > Given a text file, implement a solution to find out if a pattern
> > similar to wild cards can be detected.
> > fort example find if a*b*cd*, or *win or *def* exists in the text.
>
> Whatever be the pattern sort it must be regular expression. So in
> principle, there always exists a deterministic finite automata with
> exactly one finite state to accept the pattern.
> Thus, the problem can be solved. For example take the case for
> a*b*cd*. The automaton can  can written as:
>
> 1.Set state=1.
> 2. Scan the string until end of string is reached.
>2.1. If state is 1 and the letter is a then do not change the
> state.
>   If the state is 1 and the letter is b then go to state 2.
>   if the state is 1 and the letter is c then go to state 3.
>   if the state is 1 and the letter is d then go to state 4.
>
>   if the state is 2 and letter is a then go to state 4.
>   if the state is 2 and the letter is b then do not change
> the state.
>   if the state is 2 and the letter is c the go to state 3.
>   if the state is 2 and the letter is d then go to state 4.
>
>   if the state is 3 and the letter is a,b or c then go to
> state 4.
>   if the state is 3 and the letter is d then do not change
> state.
>
>   if the state is 4 then do not change state.
>
>   3. If the state is 3 output "accept" else output "reject".
>
> --
> 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."

-- 
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.

Re: [algogeeks] Re: distinct substring

[Arun Vishwanathan]

@juver: further explanation?

On Tue, Jan 25, 2011 at 6:27 AM, juver++  wrote:

> suffix trees.
>
> --
> 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."

-- 
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.

Re: [algogeeks] Re: Divisibility by five

[karthikeyan muthu]

@dave

int no=10;
char ans[100];
sprintf(ans,"%d",no);
cout @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  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  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  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  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<> > > > s = r^(m&1)^rem;
>> > > > b = b|(s<> > > > 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."
>
>  --
> 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.
>

-- 
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.
F

Re: [algogeeks] c++_Output

[atul anand]

output is complier dependent .

On Sat, Jan 21, 2012 at 5:12 PM, Kailash Bagaria  wrote:

> Please explain the output of the following program
>
> #include 
> using namespace std;
> int main()
> {
> int i=5;
> i=i++ + ++i;
> cout<
> int j=5;
> cout<
> int k=5;
> k=k++ + k++ + ++k;
> cout<
> system("pause");
> return 0;
> }
> --
>
> --
>
> ‘Kailash Bagaria’
> B-tech 3rd year
> Computer Science & Engineering
> Indian Institute of Technology, Roorkee
> Roorkee, India (247667)
>
>  --
> 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.
>

-- 
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.

Re: [algogeeks] Re: Divisibility by five

[Arun Vishwanathan]

@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  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  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  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  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< > > > s = r^(m&1)^rem;
> > > > b = b|(s< > > > 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."

-- 
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.

Re: [algogeeks] how to convert a floating point number into binary representation.

[Arun Vishwanathan]

@immanuel:
in this part
 while (decimalPart > 0 && decimalPart < 1 && str.length < 64) {
decimalPart *= 2;
str[str.length] = (decimalPart - 0) + '0';
}

is this decimalPart-0 correct here?
if decimalpart (say) starts as 0.584 then after doing that into 2 we 1.164.
What happens next according to your code?


On Tue, May 24, 2011 at 1:45 AM, immanuel kingston <
kingston.imman...@gmail.com> wrote:

> correct me if I am wrong.
>
> String convertFloatToBinary(float num) {
>String str = "";
>int numBeforeDecimal = (int)num;
>float decimalPart = num - (float)numBeforeDecimal;
>int sign=1;
>if (numBeforeDecimal < 0 ) sign = -1;
>if (sign < 0) str[str.length] = '-';
>while(numBeforeDecimal > 0) {
>  str[str.length] = numBeforeDecimal % 2 + '0';
>  numBeforeDecimal /= 2;
>}
>str[str.length] = '.';
>while (decimalPart > 0 && decimalPart < 1 && str.length < 64) {
> decimalPart *= 2;
> str[str.length] = (decimalPart - 0) + '0';
>}
>return str;
> }
>
> Thanks,
> Immanuel
>
>
> On Tue, May 24, 2011 at 12:15 PM, Naveen Kumar  > wrote:
>
>> http://kipirvine.com/asm/workbook/floating_tut.htm
>>
>>
>>
>> On Tue, May 24, 2011 at 12:09 PM, saurabh agrawal 
>> wrote:
>>
>>>
>>>  --
>>> 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.
>>>
>>
>>
>>
>> --
>> Cheers
>> Naveen Kumar
>>
>>  --
>> 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.
>>
>
>  --
> 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."

-- 
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.

[algogeeks] c++_Output

[Kailash Bagaria]

Please explain the output of the following program

#include 
using namespace std;
int main()
{
int i=5;
i=i++ + ++i;
cout

[algogeeks] segment tree

[UTKARSH SRIVASTAV]

Hi can anyone please give a good link to study lazy propagation in segment
tree with example or code. I know segment tree but not about lazy
propagation.

-- 
*UTKARSH SRIVASTAV
CSE-3
B-Tech 3rd Year
@MNNIT ALLAHABAD*

-- 
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.

Re: [algogeeks] Re: vertical level sum in Binary tree

[UTKARSH SRIVASTAV]

yes atul I wanted to say only that may be not able to convey it . n is
maximum number of vertical lines sum that you can calculate

On 1/21/12, atul anand  wrote:
> @ UTKARSH : how will you calculate number of vertical lines before passing
> it to vsum().
>
> i guess n should be max(no. of nodes to the extreme left from the root ,
> no. of nodes to the extreme right from root)
>
> On Fri, Jan 20, 2012 at 10:35 PM, UTKARSH SRIVASTAV > wrote:
>
>> void vsum(struct  node *p ,int i)
>> {
>> if(p)
>> {
>> sum[i] = sum[i] + p->data;
>> vsum(p->left,i-1);
>> vsum(p->right,i+1);
>> }
>> }
>>
>> construct an array of int sum[n] where n will be maximum no. of vertical
>> lines and call vsum with vsum(root,n/2)
>>
>>
>> On Fri, Jan 20, 2012 at 9:06 PM, sravanreddy001
>> wrote:
>>
>>> what does it mean.. we cannot use an array? (a static array?)
>>>
>>> a vector is an array..but a dynamic one... what other DS can be used? a
>>> linked list allowed?
>>>
>>> (each of the two algorithms can be mate to work with linked list too...
>>> (except that it takes more time.. )
>>>
>>>  --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msg/algogeeks/-/GN5SzfqtYlgJ.
>>>
>>> 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.
>>>
>>
>>
>>
>> --
>> *UTKARSH SRIVASTAV
>> CSE-3
>> B-Tech 3rd Year
>> @MNNIT ALLAHABAD*
>>
>>
>>  --
>> 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.
>>
>
> --
> 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.
>
>


-- 
*UTKARSH SRIVASTAV
CSE-3
B-Tech 3rd Year
@MNNIT ALLAHABAD*

-- 
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.

Re: [algogeeks] Re: Amazon ques

[gaurav arora]

yeah...u r right 

-- 
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.

Re: [algogeeks] Re: vertical level sum in Binary tree

[atul anand]

@ UTKARSH : how will you calculate number of vertical lines before passing
it to vsum().

i guess n should be max(no. of nodes to the extreme left from the root ,
no. of nodes to the extreme right from root)

On Fri, Jan 20, 2012 at 10:35 PM, UTKARSH SRIVASTAV  wrote:

> void vsum(struct  node *p ,int i)
> {
> if(p)
> {
> sum[i] = sum[i] + p->data;
> vsum(p->left,i-1);
> vsum(p->right,i+1);
> }
> }
>
> construct an array of int sum[n] where n will be maximum no. of vertical
> lines and call vsum with vsum(root,n/2)
>
>
> On Fri, Jan 20, 2012 at 9:06 PM, sravanreddy001 
> wrote:
>
>> what does it mean.. we cannot use an array? (a static array?)
>>
>> a vector is an array..but a dynamic one... what other DS can be used? a
>> linked list allowed?
>>
>> (each of the two algorithms can be mate to work with linked list too...
>> (except that it takes more time.. )
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/GN5SzfqtYlgJ.
>>
>> 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.
>>
>
>
>
> --
> *UTKARSH SRIVASTAV
> CSE-3
> B-Tech 3rd Year
> @MNNIT ALLAHABAD*
>
>
>  --
> 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.
>

-- 
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.