[algogeeks] [brain teaser ] Greater than God Riddle 18 may
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 Herehttp://dailybrainteaser.blogspot.com/2011/05/greater-than-god-riddle-18-may.html?lavesh=lavesh 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
*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 lavesh.ra...@gmail.comwrote: 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 Herehttp://dailybrainteaser.blogspot.com/2011/05/greater-than-god-riddle-18-may.html?lavesh=lavesh 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
@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 kp101...@gmail.com 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.gif361.gif33D.gif322.gif360.gif
Re: [algogeeks] Array problem
i dnt htink a o(n) soln exists for this problem.
On Wed, May 18, 2011 at 3:47 PM, amit kumar amitthecoo...@gmail.com 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 kp101...@gmail.com 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.gif361.gif33D.gif322.gif360.gif
Re: [algogeeks] Array problem
@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.gif33A.gif320.gif
Re: [algogeeks] [brain teaser ] Greater than God Riddle 18 may
Hahaha...Nice answer Piyush ! On Wed, May 18, 2011 at 12:44 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: *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 lavesh.ra...@gmail.comwrote: 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 Herehttp://dailybrainteaser.blogspot.com/2011/05/greater-than-god-riddle-18-may.html?lavesh=lavesh 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
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
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 kp101...@gmail.com 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.gif33A.gif320.gif
Re: [algogeeks] Re: Google Q
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 dave_and_da...@juno.com 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 ashg...@gmail.com 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 agr.bhav...@gmail.com 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
@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 saurabh...@gmail.com 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 dave_and_da...@juno.com 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 ashg...@gmail.com 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 agr.bhav...@gmail.com 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
Yes. Use a sieve. Don On May 17, 11:36 pm, wujin chen wujinchen...@gmail.com 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 dave_and_da...@juno.com @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 wujinchen...@gmail.com 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
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]C[j]) *
* j++;
if(max_diffj-i-1)
max_diff = j-i-1;
i++;
j++;
}
the code for creating B[] and C[] can be as follows...
let N = (sizeof(A)/sizeof(A[0]))
B[0] = A[0];
for(i=1;iN;i++)
{
B[i] = ((A[i]B[i-1])?A[i]:B[i-1]);
}
C[N-1] = A[N-1];
for(i=N-2;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 ecstasy.piy...@gmail.comwrote:
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 kp101...@gmail.com 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.gif33A.gif330.gif320.gif
