Re: [algogeeks] 4Sum
@Hemesh : +1 @Jalaj : read Hemesh's solution again it is for 4sum. In short, make a new array having sum of each unique pair of given array. - O(n^2) sort it - O(n^2) for each number bi in new array, binary search (target - bi) in the same array - O(n^2) On Sunday, 17 June 2012 12:41:40 UTC+5:30, Jalaj wrote: The solution which hemesh gave was solution to 3SUM hard problem the best solution for which can be achieved in n^2 . And the original question is a kind of 4SUM hard problem for which best possible solution i think is again n^3 and Amol what you told is not n^3 , finding all triplets will itself take n^3 and doing a binary search again that sums upto n^3*logn. @shashank it is not a variation of 3SUM problem as in 3SUM problem a+b+c = some constant , but in your case it is b+c+d = s-a, where a can change again and again so if you do even apply 3SUM logic to it you will have to do it for every a which will make it n^2*n = n^3 On Sat, Jun 16, 2012 at 2:45 AM, sanjay pandey sanjaypandey...@gmail.comwrote: @hemesh cud u plz elaborate wat is b[k]=a[i]+a[j]...n also ur solution... -- 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/9jCCN5iHDB8J. 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] SPOJ Problems SCUBADIV
Hi, I am trying to solve this problem. http://www.spoj.pl/problems/SCUBADIV/ But I am getting a lot of WAs! Any good logic(Solution) to solve the problem? Thanks in advance for your reply. Rituraj 2nd year B.Tech(CSE) NIT-Patna -- 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/-/16lWxB_BhlsJ. 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] Analysis of Partial Sorting.
Thanks Hassan. But I was more interested in knowing the mathematic proof of Partial Quick Sort. -- Amitesh On Sun, Jun 17, 2012 at 7:54 PM, Hassan Monfared hmonfa...@gmail.comwrote: O(N*logM) On Sat, Jun 16, 2012 at 5:15 PM, Amitesh Singh singh.amit...@gmail.comwrote: Hi Guys, *Problem: *Rearrange a given array with n elements, so that m places contain the m smallest elements in ascending order. *Solution 2:* using QuickSort method approach. [image: n = r -p + 1] [image: \bold{PARTIAL-QUICKSORT(A,p,r,m)}: \newline if\; pr \newline q \leftarrow RANDOMIZED-PARTITION(A,p,r) \newline PARTIAL-QUICKSORT(A,p,q-1,m) \newline if \; qm-1 \newline PARTIAL-QUICKSORT(A,q+1,r,m)] http://amiteshsingh.wordpress.com/2012/06/16/partial-sorting/ I know if m = n, then complexity of Partial sorting is same as QuickSort. but what would be the *average case analysis* in terms of n and m? Any suggestion would be highly appreciated. -- Amitesh -- 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. -- 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] expectation values..
http://www.spoj.pl/problems/FAVDICE/ On Sun, Jun 17, 2012 at 8:43 PM, Doom duman...@gmail.com wrote: If we expand it.. E(t) = E(t1) + E(t2) + E(t3) + ... + E(tn); here I am able to derive E(t1) as N/1 using the expression E(t1) = 1/N + ((N-1)/N)(E(t1) + 1); but how do I proceed? How do I derive the E(t2) and so on?? What do these values mean?? Does it mean like E(t2) is the no. of expected throws to get value 2?? Any help on this? On Sunday, 17 June 2012 00:09:13 UTC+5:30, amitesh wrote: This problem is similar to Coupan collector problem. http://en.wikipedia.org/wiki/**Coupon_collector%27s_problemhttp://en.wikipedia.org/wiki/Coupon_collector%27s_problem In your case the answer is [image: For N-Dice ; \newline \sum_{i=1}^{N} N/i \newline for\; N =~2 ; \newline \sum_{i=1}^{2} 2/i = 2/1 + 2/2 = 3 \newline] Hope it helps! -- Amitesh On Sat, Jun 16, 2012 at 5:18 PM, Gaurav Popli gpgaurav.n...@gmail.comwrote: What is the expected number of throws of his die while it has N sides so that each number is rolled at least once? e.g for n=2 ans 3.00 n=12 ans is 37.24... i refrd to expectation tutuorial at http://www.codechef.com/wiki/**tutorial-expectationhttp://www.codechef.com/wiki/tutorial-expectationbut still couldnt get the logic... any help? -- 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- 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/-/xLsfC_Gc8z0J. 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] Find the Max from each sub-array of size k
We can also build a Balanced BST for the window elements and on each shift we need to have a delete operation and add oeration. O(n logk) Also we can add the Shashank algo where we check if the newly added element is greater than the current BST's max element. So we can discard the current BSt and start a new BST Thanks Ramindar Singh On Friday, 2 September 2011 09:04:26 UTC+5:30, Anup wrote: Given an unsorted Array A and any integer k where k = size of A Print the maximum of each sub-array of size k of A. eg: A = [ 3, 5, 1, 9, 0, 4, -1, 7 ] k = 4 Max: 9 9 9 9 7 -- Anup Ghatage -- 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/-/A1g3pH1GCgUJ. 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: Microsoft question
We can use Median of medians http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm On Sunday, 17 June 2012 08:13:18 UTC+5:30, Prem Nagarajan wrote: Give an array of unsorted elements, find the kth smallest element in the array. The expected time complexity is O(n) and no extra memory space should be used. Quickselect algorithm can be used to obtain the solution. Can anyone explain how quickselect works? -- 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/-/4lQsacmUPYUJ. 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] I need
This is typical knapsack problem. On Mon, Jun 18, 2012 at 10:33 AM, Rituraj worstcod...@gmail.com wrote: Hi, I am trying to solve this problem. http://www.spoj.pl/problems/SCUBADIV/ But I am getting a lot of WA! Any good logic(solution) to solve the problem? Thanks in advance for your reply. -- 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/-/WOiAgraJqi8J. 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: Microsoft question
Hi all, A variation of selection sort can be used which takes O(nk) time. for i 1 to k min_index = i for j i+1 to n if a[j] a[min_index] min_index = j swap(a[i],a[min_index]) required element : a[k] On Sunday, 17 June 2012 08:13:18 UTC+5:30, Prem Nagarajan wrote: Give an array of unsorted elements, find the kth smallest element in the array. The expected time complexity is O(n) and no extra memory space should be used. Quickselect algorithm can be used to obtain the solution. Can anyone explain how quickselect works? -- 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/-/FABBRabzVqMJ. 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] 4Sum
@hemesh,kk: let's take a test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array can u please elaborate how will you take care of such situation ? @jalaj: yes it's O( (n^3)*logn) @bhavesh: fyi.. log(n^3)=3*log(n)=O(log(n)) so it's same.. :P -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Mon, Jun 18, 2012 at 12:29 AM, KK kunalkapadi...@gmail.com wrote: @Hemesh : +1 @Jalaj : read Hemesh's solution again it is for 4sum. In short, make a new array having sum of each unique pair of given array. - O(n^2) sort it - O(n^2) for each number bi in new array, binary search (target - bi) in the same array - O(n^2) On Sunday, 17 June 2012 12:41:40 UTC+5:30, Jalaj wrote: The solution which hemesh gave was solution to 3SUM hard problem the best solution for which can be achieved in n^2 . And the original question is a kind of 4SUM hard problem for which best possible solution i think is again n^3 and Amol what you told is not n^3 , finding all triplets will itself take n^3 and doing a binary search again that sums upto n^3*logn. @shashank it is not a variation of 3SUM problem as in 3SUM problem a+b+c = some constant , but in your case it is b+c+d = s-a, where a can change again and again so if you do even apply 3SUM logic to it you will have to do it for every a which will make it n^2*n = n^3 On Sat, Jun 16, 2012 at 2:45 AM, sanjay pandey sanjaypandey...@gmail.com wrote: @hemesh cud u plz elaborate wat is b[k]=a[i]+a[j]...n also ur solution... -- 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- 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/-/9jCCN5iHDB8J. 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] spoj problem : POKER
here is my code: #includestdio.h #includestring.h #includestdlib.h int main() { int t,i,j,k1,k2,ans[40],sum,sum1; char str[40][20],str1[6],str2[6]; scanf(%d,t); for(i=0;i=t;i++) { gets(str[i]); } for(i=1;i=t;i++) { for(j=1,k1=0;j15,k15;j=j+3,k1++) { str1[k1] = str[i][j]; } str1[5] = '\0'; for(j=0,k1=0;j15,k15;j=j+3,k1++) { str2[k1] = str[i][j]; } str2[5] = '\0'; sum = 0; for(k1=0;k15;k1++) sum = sum+str2[k1]; if(strcmp(str1,H)==0 || strcmp(str1,C)==0 || strcmp(str1,S)==0 || strcmp(str1,D)==0) { if(sum=260 sum = 263 || sum == 271 || sum == 306 || sum == 326 || sum == 352 || sum == 371 || sum == 379) { if(sum == 379) ans[i] = 1; else ans[i] = 2; } else ans[i] = 3; } else { if(sum=260 sum = 263 || sum == 271 || sum == 306 || sum == 326 || sum == 352 || sum == 371 || sum == 379) ans[i] = 4; else { j = 0; for(k1=0;k15;k1++) { for(k2=k1+1;k25;k2++) //ASCII comparison of 4 of a kind gives 6 { sum = str2[k1]; sum1 = str2[k2]; if(sum == sum1) j++; } } switch(j) { case 1: ans[i] = 9; break; case 2: ans[i] = 8; break; case 3: ans[i] = 7; break; case 4: ans[i] = 6; break; case 6: ans[i] = 5; break; } } } } for(i=1;i=t;i++) { switch(ans[i]) { case 1: printf(royal flush\n); break; case 2: printf(straight flush\n); break; case 3: printf(flush\n); break; case 4: printf(straight\n); break; case 5: printf(four of a kind\n); break; case 6: printf(full house\n); break; case 7: printf(three of a kind\n); break; case 8: printf(two pairs\n); break; case 9: printf(pair\n); break; default: printf(high card\n); } } return 0; } it ran successfully but is giving WA in spoj.. plz help me -- 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: spoj problem : POKER
it also ran successfully on ideone.com plz help me i am classifying the card in two parts: one with same suit and other with different suit... plz let me know if futher explanation is needed abt the code help me regarding this.. thanx -- 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] Precedence or Associativity
Let us see what we have - we basically have an expression A || B C. We also know the following: 1. || and are both considered sequence points 2. The has precedence over the || operator 3. The C/C++ languages use minimal evaluation principle when evaluating the logical expressions (see the wiki article for this: http://en.wikipedia.org/wiki/Short-circuit_evaluation) Now, let us see how the A || B C will be evaluated given all the above. Since the has higher priority in the evaluation process, the B C will be given the priority. But, since the is a sequence point, it means that all the sub expressions on its left will have to be evaluated first and their artifacts are complete, i.e. the A || B. In our case, it is ++i || ++j. Here, the ++i evaluates to true and the ++j does not get evaluated at all due to the fact that we already have an expression that has already evaluated to true (minimal evaluation principle). And the same minimal evaluation principle will be applied when evaluating the initial expression B C, effectively skipping the evaluation at all. To recap, we can see that the only actual evaluation happens for the expression A || B, in our case - the ++i || ++j, which in its turn short circuits to evaluating the ++i only. Rgds, Ashot From: algogeeks@googlegroups.com [mailto:algogeeks@googlegroups.com] On Behalf Of enchantress Sent: Sunday, June 17, 2012 11:20 AM To: algogeeks@googlegroups.com Subject: [algogeeks] Precedence or Associativity Consider the following code: int i=0,j=0,k=0; int x = ++i || ++j ++k; O/P: x=1,i=1,j=0,k=0 Now, the logic operators are evaluated left to right and if the output is determined by left hand side expression right hand side is not evaluated. But the precedence of || hence ++j++k should be dealt with first.The output says once ++i evaluates to 1 further expression is not considered. Can anyone explain this anomaly? As of i know associativity is considered when precedence of operators is the same eg: x*y/z will be evaluated left to right. -- 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/-/rr41g1Q8q38J. 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: spoj problem : POKER
Your code fails on one of the test cases like 5H 6H 7H 8H 9H. it should give straight flush instead of flush, Think of all such cases are change accordingly .. On Mon, Jun 18, 2012 at 10:01 PM, Mayank Singh singh13490may...@gmail.com wrote: it also ran successfully on ideone.com plz help me i am classifying the card in two parts: one with same suit and other with different suit... plz let me know if futher explanation is needed abt the code help me regarding this.. thanx -- 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] 4Sum
@hemesh :- please explain your approach On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma amolsharm...@gmail.com wrote: @hemesh,kk: let's take a test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array can u please elaborate how will you take care of such situation ? @jalaj: yes it's O( (n^3)*logn) @bhavesh: fyi.. log(n^3)=3*log(n)=O(log(n)) so it's same.. :P -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Mon, Jun 18, 2012 at 12:29 AM, KK kunalkapadi...@gmail.com wrote: @Hemesh : +1 @Jalaj : read Hemesh's solution again it is for 4sum. In short, make a new array having sum of each unique pair of given array. - O(n^2) sort it - O(n^2) for each number bi in new array, binary search (target - bi) in the same array - O(n^2) On Sunday, 17 June 2012 12:41:40 UTC+5:30, Jalaj wrote: The solution which hemesh gave was solution to 3SUM hard problem the best solution for which can be achieved in n^2 . And the original question is a kind of 4SUM hard problem for which best possible solution i think is again n^3 and Amol what you told is not n^3 , finding all triplets will itself take n^3 and doing a binary search again that sums upto n^3*logn. @shashank it is not a variation of 3SUM problem as in 3SUM problem a+b+c = some constant , but in your case it is b+c+d = s-a, where a can change again and again so if you do even apply 3SUM logic to it you will have to do it for every a which will make it n^2*n = n^3 On Sat, Jun 16, 2012 at 2:45 AM, sanjay pandey sanjaypandey...@gmail.com wrote: @hemesh cud u plz elaborate wat is b[k]=a[i]+a[j]...n also ur solution... -- 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- 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/-/9jCCN5iHDB8J. 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. -- Utsav Sharma, NIT 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: MS Question: Reverse stack using push, pop without any auxiliary data structure
In a stack, you can't access any element directly, except the top one. On Mon, Jun 18, 2012 at 11:33 AM, Rituraj worstcod...@gmail.com wrote: My iterative approach /*code in c*/ #includestdio.h int main() { int stack[]={1,2,3,4,5,6,7,8},top=7;// int i,j,temp; for(i=1;i=top;i++) { temp=stack[i]; for(j=i;j0;j--) stack[j]=stack[j-1]; stack[0]=temp; } for(i=0;i=top;i++) printf(%d ,stack[i] ); return 0; } /* Rituraj 2nd Yr. B.tech CSE NIT -Trichy -- 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/-/n1OE58e8B7IJ. 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. -- Abhishek Sharma Under-Graduate Student, PEC University of Technology -- 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: MS Question: Reverse stack using push, pop without any auxiliary data structure
this is not a stack at all, u have just named it as a stack. for it to be a stack u should access only the top most element at any point of time!!! On Mon, Jun 18, 2012 at 11:33 AM, Rituraj worstcod...@gmail.com wrote: My iterative approach /*code in c*/ #includestdio.h int main() { int stack[]={1,2,3,4,5,6,7,8},top=7;// int i,j,temp; for(i=1;i=top;i++) { temp=stack[i]; for(j=i;j0;j--) stack[j]=stack[j-1]; stack[0]=temp; } for(i=0;i=top;i++) printf(%d ,stack[i] ); return 0; } /* Rituraj 2nd Yr. B.tech CSE NIT -Trichy -- 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/-/n1OE58e8B7IJ. 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. -- Aditya Gupta B.Tech III yr CSE IITR -- 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: MS Question: Reverse stack using push, pop without any auxiliary data structure
I think there is a problem in this solution. U r accessing stack elements from 1 to n in the outer loop. It is not possible. 1st element cannot be accessed without popping first n-1 elements out. On Mon, Jun 18, 2012 at 11:33 AM, Rituraj worstcod...@gmail.com wrote: My iterative approach /*code in c*/ #includestdio.h int main() { int stack[]={1,2,3,4,5,6,7,8},top=7;// int i,j,temp; for(i=1;i=top;i++) { temp=stack[i]; for(j=i;j0;j--) stack[j]=stack[j-1]; stack[0]=temp; } for(i=0;i=top;i++) printf(%d ,stack[i] ); return 0; } /* Rituraj 2nd Yr. B.tech CSE NIT -Trichy -- 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/-/n1OE58e8B7IJ. 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: Microsoft question
@enchantress : This problem can be solved using quicksort in O(nlogn). No need to go for selection sort. But O(n) solution is needed. On Mon, Jun 18, 2012 at 2:50 PM, enchantress elaenjoy...@gmail.com wrote: Hi all, A variation of selection sort can be used which takes O(nk) time. for i 1 to k min_index = i for j i+1 to n if a[j] a[min_index] min_index = j swap(a[i],a[min_index]) required element : a[k] On Sunday, 17 June 2012 08:13:18 UTC+5:30, Prem Nagarajan wrote: Give an array of unsorted elements, find the kth smallest element in the array. The expected time complexity is O(n) and no extra memory space should be used. Quickselect algorithm can be used to obtain the solution. Can anyone explain how quickselect works? -- 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/-/FABBRabzVqMJ. 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: Directi question-centre of the tree
I found it in some paper ;) Diameter and center De nition 4. The diameter of tree is the length of the longest path. De nition 5. A center is a vertex v such that the longest path from v to a leaf is minimal over all vertices in the tree.Tree center(s) can be found using simple algorithm. Algorithm 1. (Centers of tree) 1: Choose a random root r. 2: Find a vertex v1 | the farthest form r. 3: Find a vertex v2 | the farthest form v1. 4: Diameter is a length of path from v1 to v2. 5: Center is a median element(s) of path from v1 to v2. This is O(n) algorithm. It is clear that we can't determine tree isomorphism faster than O(n). So, if we nd a O(f(n)) algorithm for rooted trees isomorphism we can also obtain O(f(n)) algorithm for ordinary trees. On Saturday, June 16, 2012 12:04:32 PM UTC+5:30, achala sharma wrote: I think this algorithm is used for calculating poset in graph. On Sat, Jun 16, 2012 at 3:04 AM, Hemesh Singh hemesh.mn...@gmail.comwrote: + 1 for DK's solution. Is that a standard algorithm coz I feel like I have heard it somewhere ?? On Mon, Aug 8, 2011 at 1:37 AM, DK divyekap...@gmail.com wrote: @KK: DFS and BFS are O(N) and Floyd Warshall is O(N^3). Could you please state how you can use the traversals directly to get the center? (And prove your correctness too?) The solution given by Wladimir ( expanded upon by me) is O(N) and uses (somewhat) the inverse of a BFS as a traversal. -- DK http://twitter.com/divyekapoor http://gplus.to/divyekapoor http://www.divye.in -- 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/-/HnMOZtOrkqwJ. 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. -- Hemesh singh -- 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/BWplK7bCatMJ. 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.