Re: [algogeeks] Can you guys help me how to approach this problem !!!
You guy check this solution. It is expected to be run in O(n lg n) for random permutation in average time. For worst case, I think we can improve it for that. Let's do an example firstly. 7 3 4 1 2 6 5 8 For *1*, it self is a block. Let's count the blocks containing *1* firstly. If a block with size more than 1 contains *1*, it will contains *2*. Now check *2*, it is not beside *1*, so no block with size=2 contains *1*. Let's check *3*', the minimum position for (1,2,3) is 1 (with 0 based index), and maximum position for (1,2,3) is 4. Because 4-1+1 = 43, no block with sizeo=3 contains *1*. Let's check *4*, the minimum position for (1,2,3,4) is 1, and maximum position is 4. The window size is 4-1+1 = 4. We find a block with size=4 and it contains *1*. By continuing this process, we will get the number of blocks containing number *1* and more important is the time we need is linear time: O(n). Now, we have checked all blocks including number *1*. So from now on, we do not need number *1* anymore. It means we can split the list into two [7 3 4] and [2 6 5 8] and repeat the above process again again. If the permutation is really random, the above process is very similar as the QuickSort process and then we know the whole process cost O(n lg n) time. However, for worst case like [1 2 3 4 ... n], it performs very bad. The time complexity is linear with the number of blocks and so it is not good in worst case. I.e. the above algorithm need O(n^2) time for such worst case. Hope other guys can solve the worst case in O(n lg n) time. Thanks On Tue, Dec 1, 2009 at 2:33 PM, Vinoth Kumar vinoth.ratna.ku...@gmail.com wrote: Given an array A which holds a permutation of 1,2,...,n. A sub-block A [i..j] of an array A is called a valid block if all the numbers appearing in A[i..j] are consecutive numbers (may not be in order. Given an array A= [ 7 3 4 1 2 6 5 8] the valid blocks are [3 4], [1,2], [6,5], [3 4 1 2], [3 4 1 2 6 5], [7 3 4 1 2 6 5], [7 3 4 1 2 6 5 8] Give an O( n log n) algorithm to count the number of valid blocks. -- Vinod -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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 algoge...@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: Can you guys help me how to approach this problem !!!
These are the steps for the O(n^2) solution n=length of A for each subarray A[i,j] where ji min=min(A[i,j]) max=max(A[i,j]) if(max - min==size (A[i,j]) print A[i,j] min[A[i,j]]=min( A[j], min(A[i,j-1]) similar one for max Note: A[i,j] = A[i],A[i+1]A[j] I was wondering how to do the same problem in O(nlogn) -- Vinod On Wed, Dec 2, 2009 at 11:48 AM, ranjmis ranj...@gmail.com wrote: Vinod. Can you please mention steps for the O(n^2) solution that you have thought of. On Dec 2, 9:50 am, Vinoth Kumar vinoth.ratna.ku...@gmail.com wrote: No need for the code guys. Can u give me a algo or pseudo code for this problem. I can think of a soln of O(n^2) but i need a algo for O(nlogn) On Wed, Dec 2, 2009 at 2:06 AM, NickLarsen fodylar...@gmail.com wrote: That doesn't quite get it, try the input [ 7 3 4 2 1 6 5 8] and your idea would miss [3 4 2] On Dec 1, 10:10 am, sharad kumar aryansmit3...@gmail.com wrote: find out the subseq which are consecttive concatenate them at each level to get the entire set. On Tue, Dec 1, 2009 at 12:03 PM, Vinoth Kumar vinoth.ratna.ku...@gmail.comwrote: Given an array A which holds a permutation of 1,2,...,n. A sub-block A [i..j] of an array A is called a valid block if all the numbers appearing in A[i..j] are consecutive numbers (may not be in order. Given an array A= [ 7 3 4 1 2 6 5 8] the valid blocks are [3 4], [1,2], [6,5], [3 4 1 2], [3 4 1 2 6 5], [7 3 4 1 2 6 5], [7 3 4 1 2 6 5 8] Give an O( n log n) algorithm to count the number of valid blocks. -- Vinod -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Cheers, Vinod -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: Can you guys help me how to approach this problem !!!
check this if How To Install Dreamweaver CS3 In Ubuntu Hardyhttp://eaziweb.blogspot.com/2009/12/how-to-install-dreamweaver-cs3-in.html Regards Shahzeb Farooq Chohan Software Engineer Cogilent Solutions Get your new Email address! Grab the Email name you've always wanted before someone else does! http://mail.promotions.yahoo.com/newdomains/aa/ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Can you guys help me how to approach this problem !!!
check this if How To Install Dreamweaver CS3 In Ubuntu Hardyhttp://eaziweb.blogspot.com/2009/12/how-to-install-dreamweaver-cs3-in.html Regards Shahzeb Farooq Chohan Software Engineer Cogilent Solutions Get your new Email address! Grab the Email name you've always wanted before someone else does! http://mail.promotions.yahoo.com/newdomains/aa/ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Recaman's sequence
Hi, Well Recaman's sequence is defined by: a(0) = 0 a(k) = a(k-1) - k, k0, a(k) new term in series or else a(k-1) + k So sequence is 0, 1, 3,6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, My approach used memoization using map in c++ (giving O(n) time and memory for generating sequence), but I somehow feel that there can be a better approach to check if a term already exists in the sequence. Any suggestion would be gratefully acknowledged. Regards, Tushar -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: Can you guys help me how to approach this problem !!!
On Dec 2, 6:45 am, Vinoth Kumar vinoth.ratna.ku...@gmail.com wrote: These are the steps for the O(n^2) solution n=length of A for each subarray A[i,j] where ji min=min(A[i,j]) max=max(A[i,j]) if(max - min==size (A[i,j]) print A[i,j] min[A[i,j]]=min( A[j], min(A[i,j-1]) similar one for max Note: A[i,j] = A[i],A[i+1]A[j] I was wondering how to do the same problem in O(nlogn) It's a binary tree, [ 7 3 4 1 2 6 5 8] has children [ 7 3 4 1 2 6 5] and [ 3 4 1 2 6 5 8], all the way down to [ 7 3] [3 4] [4 1] ... If you start at the bottom keeping track of min and max for each node, if max-min == node length - 1 the node if conseq. then it's just a matter of combining node together and working up the tree -- Geoff -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: Can you guys help me how to approach this problem !!!
On Dec 2, 10:42 am, Geoffrey Summerhayes sumr...@gmail.com wrote: It's a binary tree, [ 7 3 4 1 2 6 5 8] has children [ 7 3 4 1 2 6 5] and [ 3 4 1 2 6 5 8], all the way down to [ 7 3] [3 4] [4 1] ... If you start at the bottom keeping track of min and max for each node, if max-min == node length - 1 the node if conseq. then it's just a matter of combining node together and working up the tree Darn! Total steps= n*n/2 - n/2 Anybody have a math trick? -- Geoff -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
