[algogeeks] [brain teaser ] Greater than God Riddle 18 may

[Lavesh Rawat]

Greater than God Riddle 18 MAY PUZZLE

*What is Greater than God, worse than evil, the poor have it, the rich
require it, and if you eat it, you die?*
*
*

*Update Your Answers at* : Click
Here


Solution:
Will be updated after 1 day




-- 

"Never explain yourself. Your friends don’t need it and
your enemies won’t believe it" .

-- 
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] [brain teaser ] Greater than God Riddle 18 may

[Piyush Sinha]

*NOTHING*.

*Greater than GOD - NOTHING*
*Worse than EVIL - NOTHING*
*Poor have it and rich want it - NOTHING*
*if you eat it, you die - NOTHING
*
On Wed, May 18, 2011 at 12:35 PM, Lavesh Rawat wrote:

>Greater than God Riddle 18 MAY PUZZLE
>
> *What is Greater than God, worse than evil, the poor have it, the rich
> require it, and if you eat it, you die?*
> *
> *
>
> *Update Your Answers at* : Click 
> Here
>
>
> Solution:
> Will be updated after 1 day
>
>
>
>
> --
>
> "Never explain yourself. Your friends don’t need it and
> your enemies won’t believe it" .
>
> --
> 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.
>



-- 
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926 *

-- 
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] Array problem

[amit kumar]

@kunal patil
your soln does not work for
5 3 4 5 3 3

On Tue, May 17, 2011 at 9:57 PM, Kunal Patil  wrote:

> Ohh..If it is so...Sorry !![?]  I understood it the different way...[?]
> But if the question is as mentioned in your 2nd case then also I believe
> there is O(n) solution.[?]
>
> Maintain
> two pointers: *START* and *END*
> two variables: max1 and max2
> Assume arr[MAX_SIZE] to be the array containing the given elements.
>
> Algorithm:
> *1) Initially, make START point to zeroth element and END pointing to last
> element of the array.
> 2) Calculate max1 as:
> 2a) Compare arr[**START**] and arr[**END**].
>If arr[**START**] < arr[**END**]
>   {
>  max1 = **END** - **START**;
>  Jump to 3rd step
>   }
> 2b) If arr[**START**] >= arr[**END**]
>{
>  **END**-- ;
>  jump to step 2a and repeat this procedure till **
> END** != **START*
> *   }
> 3) Reset **END** so that it points to last element of the array.
> 4) Calculate max2 as:
> 4a) Compare arr[**START**] and arr[**END**].
>If arr[**START**] < arr[**END**]
>   {
>  max2 = **END** - **START**;
>  Jump to 5th step
>   }
> 4b) If arr**[START**] >= arr[**END**]
>{
> **START**++ ;
>  jump to step 4a and repeat this procedure till **
> START** != **END*
> *}
> 5) Return max( max1, max2)*
>
> Hope this algo is clear.
> This algo makes two passes over the array. Thus it is O(2n) = O(n)..[?]
> Let me know if this algo fails for any case you can think of..[?]
>
> --
> 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.

<<363.gif>><<361.gif>><<33D.gif>><<322.gif>><<360.gif>>

Re: [algogeeks] Array problem

[amit kumar]

i dnt htink a o(n) soln exists for this problem.

On Wed, May 18, 2011 at 3:47 PM, amit kumar  wrote:

> @kunal patil
> your soln does not work for
> 5 3 4 5 3 3
>
> On Tue, May 17, 2011 at 9:57 PM, Kunal Patil  wrote:
>
>> Ohh..If it is so...Sorry !![?]  I understood it the different way...[?]
>> But if the question is as mentioned in your 2nd case then also I believe
>> there is O(n) solution.[?]
>>
>> Maintain
>> two pointers: *START* and *END*
>> two variables: max1 and max2
>> Assume arr[MAX_SIZE] to be the array containing the given elements.
>>
>> Algorithm:
>> *1) Initially, make START point to zeroth element and END pointing to
>> last element of the array.
>> 2) Calculate max1 as:
>> 2a) Compare arr[**START**] and arr[**END**].
>>If arr[**START**] < arr[**END**]
>>   {
>>  max1 = **END** - **START**;
>>  Jump to 3rd step
>>   }
>> 2b) If arr[**START**] >= arr[**END**]
>>{
>>  **END**-- ;
>>  jump to step 2a and repeat this procedure till *
>> *END** != **START*
>> *   }
>> 3) Reset **END** so that it points to last element of the array.
>> 4) Calculate max2 as:
>> 4a) Compare arr[**START**] and arr[**END**].
>>If arr[**START**] < arr[**END**]
>>   {
>>  max2 = **END** - **START**;
>>  Jump to 5th step
>>   }
>> 4b) If arr**[START**] >= arr[**END**]
>>{
>> **START**++ ;
>>  jump to step 4a and repeat this procedure till *
>> *START** != **END*
>> *}
>> 5) Return max( max1, max2)*
>>
>> Hope this algo is clear.
>> This algo makes two passes over the array. Thus it is O(2n) = O(n)..[?]
>> Let me know if this algo fails for any case you can think of..[?]
>>
>> --
>> 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.

<<363.gif>><<361.gif>><<33D.gif>><<322.gif>><<360.gif>>

Re: [algogeeks] Array problem

[Kunal Patil]

@Amit: Ohh..Your test case is correct but not my solution..[?]
It only works if it is guaranteed that one end will be at the extreme of the
array ! (UseLess ! [?])
Sorry folks...
So can anybody prove that O(n) solution does not exist for this problem? [?]

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

<<35F.gif>><<33A.gif>><<320.gif>>

Re: [algogeeks] [brain teaser ] Greater than God Riddle 18 may

[Kunal Patil]

Hahaha...Nice answer Piyush !

On Wed, May 18, 2011 at 12:44 PM, Piyush Sinha wrote:

> *NOTHING*.
>
> *Greater than GOD - NOTHING*
> *Worse than EVIL - NOTHING*
> *Poor have it and rich want it - NOTHING*
> *if you eat it, you die - NOTHING
> *
> On Wed, May 18, 2011 at 12:35 PM, Lavesh Rawat wrote:
>
>>Greater than God Riddle 18 MAY PUZZLE
>>
>> *What is Greater than God, worse than evil, the poor have it, the rich
>> require it, and if you eat it, you die?*
>> *
>> *
>>
>> *Update Your Answers at* : Click 
>> Here
>>
>>
>> Solution:
>> Will be updated after 1 day
>>
>>
>>
>>
>> --
>>
>> "Never explain yourself. Your friends don’t need it
>> and your enemies won’t believe it" .
>>
>> --
>> 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.
>>
>
>
>
> --
> *Piyush Sinha*
> *IIIT, Allahabad*
> *+91-8792136657*
> *+91-7483122727*
> *https://www.facebook.com/profile.php?id=10655377926 *
>
>  --
> 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] [brain teaser ] Greater than God Riddle 18 may

[Bhavesh agrawal]

nice answer...

-- 
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] Array problem

[Piyush Sinha]

I think it can be done in O(n) but the auxilliary space required will be
more... in the solution which i have got its in the order of 2n

On Wed, May 18, 2011 at 4:44 PM, Kunal Patil  wrote:

> @Amit: Ohh..Your test case is correct but not my solution..[?]
> It only works if it is guaranteed that one end will be at the extreme of
> the array ! (UseLess ! [?])
> Sorry folks...
> So can anybody prove that O(n) solution does not exist for this problem?
> [?]
>
> --
> 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.
>



-- 
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926 *

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

<<35F.gif>><<33A.gif>><<320.gif>>

Re: [algogeeks] Re: Google Q

[saurabh agrawal]

Dave,
u said:" a max-heap of the smallest
half of the elements"
but if the number are randomply generated, then how will you get to know
whether a number belongs to smallest half OR lager half..
i didnt got it...





On Sat, May 14, 2011 at 9:10 PM, Dave  wrote:

> @Ashish: The idea is to keep two heaps, a max-heap of the smallest
> half of the elements and a min-heap of the largest elements. You
> insert incoming elements into the appropriate heap. If the result is
> that the number of elements in the two heaps differs by more than 1,
> then you move the top element from the longer heap into the other one,
> thereby equalzing the number of elements. Thus, inserting an element
> is an O(log n) operation. To get the median, it is the top element of
> the longer heap, or, if the heaps are of equal length, it is the
> average of the two top elements. This is O(1).
>
> Dave
>
> On May 14, 8:34 am, Ashish Goel  wrote:
> > not clear, can u elaborate..
> >
> > Best Regards
> > Ashish Goel
> > "Think positive and find fuel in failure"
> > +919985813081
> > +919966006652
> >
> > On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal  >wrote:
> >
> >
> >
> > > This problem can be solved using 2 heaps and the median can always be
> > > accessed in O(1) time ,the first node.
> >
> > > --
> > > 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.- 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.
>
>

-- 
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: Google Q

[Dave]

@Saurabh: You look at the top elements in the two heaps. If the new
number is between the values of the top of the heaps, you add it to
the shorter of the two heaps, or to either heap if they are of equal
length. If the new number is larger than the min of the min-heap, you
add it to the min-heap. If it is smaller than the max of the max-heap,
you add it to the max heap. If the resulting two heaps differ in
length by more than one element, you move the top element from the
longer heap into the shorter heap. Since the heaps start off empty and
you add only one number at a time, the result of a step of the
algorithm is that the two heaps will differ in size by at most one
element. Thus, the smaller half of the numbers will be in the max-heap
and the larger half will be in the min-heap.

Dave

On May 18, 8:29 am, saurabh agrawal  wrote:
> Dave,
> u said:" a max-heap of the smallest
> half of the elements"
> but if the number are randomply generated, then how will you get to know
> whether a number belongs to smallest half OR lager half..
> i didnt got it...
>
>
>
> On Sat, May 14, 2011 at 9:10 PM, Dave  wrote:
> > @Ashish: The idea is to keep two heaps, a max-heap of the smallest
> > half of the elements and a min-heap of the largest elements. You
> > insert incoming elements into the appropriate heap. If the result is
> > that the number of elements in the two heaps differs by more than 1,
> > then you move the top element from the longer heap into the other one,
> > thereby equalzing the number of elements. Thus, inserting an element
> > is an O(log n) operation. To get the median, it is the top element of
> > the longer heap, or, if the heaps are of equal length, it is the
> > average of the two top elements. This is O(1).
>
> > Dave
>
> > On May 14, 8:34 am, Ashish Goel  wrote:
> > > not clear, can u elaborate..
>
> > > Best Regards
> > > Ashish Goel
> > > "Think positive and find fuel in failure"
> > > +919985813081
> > > +919966006652
>
> > > On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal  > >wrote:
>
> > > > This problem can be solved using 2 heaps and the median can always be
> > > > accessed in O(1) time ,the first node.
>
> > > > --
> > > > 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.-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.- 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.

[algogeeks] Re: how to find a smallest prime bigger than a given number

[Don]

Yes. Use a sieve.
Don

On May 17, 11:36 pm, wujin chen  wrote:
> @Dave， thanks for your reply.
> i know that, i can only check  from 6*n - 1 and 6*n + 1..
> assume that, n=1 , and  we begin from k=1667, the number needed to check
> is 10001,10003
> but to determin 10001 is prime or not costs a lot, right?
> when the n is huge, it will be not feasible.
>
> is there some math principle to solve this problem easily?
>
> 2011/5/18 Dave 
>
> > @Wujin: Well, obviously, you don't have to check _every_ number one-by-
> > one. If n > 1, you can ignore every even number. Furthermore, if n >
> > 3, you can ignore every odd multiple of 3. That means that you need to
> > check only numbers of the form 6*n - 1 and 6*n + 1.
>
> > Dave
>
> > On May 17, 9:09 pm, wujin chen  wrote:
> > > given a number n, compute the smallest prime that is bigger than n.
> > > for example, n=8, then the smallest prime that bigger than 8 is 11.
>
> > > i wonder whether there is an effective way, rather than check every
> > number
> > > bigger than n one by one.
>
> > > thanks.
>
> > --
> > 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] Array problem

[Piyush Sinha]

last night i was going through a similar kind of question and tried to
implement its algo in this question...If anyone finds any counter example
for it, please do comment..

Algo:-

*Let the array be A[].
We can keep two arrays B[] and C[] which will do the following work..
B[i] will store the minimum value in A[] till ith index
C[i] will store the maximum value (starting from the end) in A[i] till ith
index.*

*Lets say taking amit's example...*

*A[] = { 5 3 4 5 3 3 }*

*then B[] = {5,3,3,3,3,3}; //starting from the beginning.
and C[] = {5,5,5,5,3,3}; //starting from the end*

*the we can take two pointers i and j and a max_diff (all initialised to 0)
and run the following loop*
*while(j<(sizeof(A)/sizeof(A[0])))
{
while(B[i]=0;i--)
{
   C[i] = ((A[i]>B[i+1])?A[i]:B[i+1]);
}*

For the given example, answer is coming to be j = 4,i=1,max_diff = 4-1-1 = 2

I hope I am clear... [?]

On Wed, May 18, 2011 at 4:52 PM, Piyush Sinha wrote:

> I think it can be done in O(n) but the auxilliary space required will be
> more... in the solution which i have got its in the order of 2n
>
>
> On Wed, May 18, 2011 at 4:44 PM, Kunal Patil  wrote:
>
>> @Amit: Ohh..Your test case is correct but not my solution..[?]
>> It only works if it is guaranteed that one end will be at the extreme of
>> the array ! (UseLess ! [?])
>> Sorry folks...
>> So can anybody prove that O(n) solution does not exist for this problem?
>> [?]
>>
>> --
>> 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.
>>
>
>
>
> --
>   *Piyush Sinha*
> *IIIT, Allahabad*
> *+91-8792136657*
> *+91-7483122727*
> *https://www.facebook.com/profile.php?id=10655377926 *
>
>


-- 
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926 *

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

<<35F.gif>><<33A.gif>><<330.gif>><<320.gif>>