Re: [algogeeks]Numbers search in an array
take one pointer to start n another to the end say a n b now if a +b X shift b towards left n so on On Fri, Jun 18, 2010 at 9:03 AM, sharad kumar aryansmit3...@gmail.comwrote: @arun:find out the difference x-arr[i] for all i=0..n hash it ...next search for a number with difference .u can get it in O(n) On Fri, Jun 18, 2010 at 8:05 AM, Arunkumar Sreenivasan thegame.a...@gmail.com wrote: Hi, You are given a set of numbers and another number 'x'. You have to find if there exists any two numbers, whose sum is equal to 'x'. I have done this is o(n)log n. Need a more optimized solution. regards, Arun kumar S -- 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. -- yezhu malai vaasa venkataramana Govinda Govinda -- 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. -- Thanking You Ashish Mishra -- 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] MXN matrix
@amit nice sit didn't know about that :) thanks On Thu, Apr 29, 2010 at 3:59 PM, amit kumar loveami...@gmail.com wrote: Answer for question 1: http://geeksforgeeks.org/?p=6257 And, I think the same solution can be extended/manipulated for rectangular matrix with largest number of 1's. Regards, Amit On Wed, Apr 28, 2010 at 10:23 PM, Vivek S s.vivek.ra...@gmail.com wrote: Let Memo[i][j] be the sum of elements in the (sub) rectangle from (0,0) to (i,j) Then use principle of inclusion and exclusion to find the sum of elements from (a, b) to (c, d) in O(1) for N*N matrix, Complexity is O(N^4) On 28 April 2010 13:36, Ashish Mishra amishra@gmail.com wrote: you are given a M x N matrix with 0's and 1's find the matrix with largest number of 1, 1. find the largest square matrix with 1's 2. Find the largest rectangular matrix with 1's -- 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. -- Reduce, Reuse and Recycle Regards, Vivek.S -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Ashish Mishra http://ashishmishra.weebly.com/ -- 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] infy color balls
One of my friend ask me this n i am bad in P C (will love if smone can provide me a link to learn it though) nyways prob is: there are infy color balls of k different color you are allowed to pick n balls out of those infy(infinite) balls cond is : you must have all k color balls with u obviously kn Question is how many possibilities for selection you have ? Thanks Ashish -- 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] MXN matrix
you are given a M x N matrix with 0's and 1's find the matrix with largest number of 1, 1. find the largest square matrix with 1's 2. Find the largest rectangular matrix with 1's -- 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] Build BST from binary tree without extra space
@rajesh can u explain your soln how u r doing inorder, pre or whatever (without using stack) and at same time build BST On Wed, Apr 28, 2010 at 3:30 PM, Rajesh Patidar patidarc...@gmail.comwrote: pickup node in any order no matter(pre,post,inorder) and just one by one. start adding the node into bst no need to use extra space u have to just ditach the node from binary tree and attach it in bst. On Wed, Apr 28, 2010 at 1:18 AM, Ashish Mishra amishra@gmail.com wrote: How to build BST from binary tree in place i.e without extra space ?? -- 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. -- BL/\CK_D!AMOND -- 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. -- Ashish Mishra http://ashishmishra.weebly.com/ -- 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] Build BST from binary tree without extra space
How to build BST from binary tree in place i.e without extra space ?? -- 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] Finding all prime less than 10^8
The Sieve of Eratosthenes is best for finding prime On Mon, Apr 12, 2010 at 10:58 AM, BlackdiamonD patidarc...@gmail.comwrote: thank kartik thanks but it was with lot of optimized code i was unable to understand though i have changed my code more know it is taking around 8 to 8.5 seconds in my computer but still i am getting TLE on server #includestdio.h #define ten8 (1) const int mod=32; unsigned int M[ten8/mod]; int main() { int half=1, i,j,x=1; int y=ten8/mod; freopen(output.txt,wt,stdout); for ( i = 0;i y;i++) M[i] = 0; printf(2\n); for ( i = 3;i ten8;i+=2) { int a=i/mod,b=i%mod; if (((M[a]b)1)==0) { x++; if(x%100==1) printf(%d\n,i); if(ihalf) continue; for (int j = i * i;j ten8;j += i) { M[j/mod] =M[j/mod]|(1(j%mod)); } } } } On Sun, Apr 11, 2010 at 7:20 AM, Karthik Reddy karthik.gin...@gmail.comwrote: http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html take a look at this link . The running time is less than 2 sec for 10^8. On Sun, Apr 11, 2010 at 2:38 AM, Black Diamond patidarc...@gmail.comwrote: i have an problem on SPOJ to find all the prime less than 10^8 https://www.spoj.pl/problems/TDPRIMES/ i am using sieve of erastosthenes algorithm to find primes my code is taking in my machine around 10.9 to 11.2 seconds and time limit is 10 second how i can change my code or any diff logic..??? //-// #includecstdio using namespace std; #define ten8 (1) bool M[ten8]; int main() { int half=1, i,j,x=0; for ( i = 0;i ten8;i++) M[i] = false; for ( i = 2;i ten8;i++) { if (M[i] == false) { x++; if(x%100==1) printf(%d\n,i); if(ihalf) continue; for (int j = i * i;j ten8;j += i) { M[j] = true; } } } } -- 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. -- Ram Karthik Reddy Ginuga karthik.ginuga[at]gmail.com CCNA,MCP Mozilla Campus Ambassador SPOJ world rank #1088 http://www.spoj.pl/users/karthu/ (91)40 27425999 (91)9247818845 -- 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. -- BL/\CK_D!AMOND -- 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. -- Ashish Mishra http://ashishmishra.weebly.com/ -- 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. My+Sign.JPG
Re: [algogeeks] Re: Implement a queue using a stack
...@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.com algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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.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.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.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 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.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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Ashish Mishra http://ashishmishra.weebly.com/ -- 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] efficient backtracking algorithm for the coin changing problem
y u need backtracking i think it can be done with DP On Sat, Apr 10, 2010 at 9:12 AM, «« ÄÑÜJ »» anujlove...@gmail.com wrote: Need help in designing efficient backtracking algorithm for the coin changing problem. where a1, a2, an are the set of distinct coins types, where each ai is an integer. and each type is unlimited quantity. the problem to make up the exact amount C using minimum total number of coins. use backtracking template with a bounding function.. help appreciated.. -- 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. -- How soon 'not now' becomes 'never'... -- 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] Finding youngest common ancestor of two nodes in a binary tree
i think u mean lowest commen ancestor? On Wed, Apr 7, 2010 at 10:34 PM, Himanshu Aggarwal lkml.himan...@gmail.comwrote: For a given binary tree, given the root and two node pointers, how can we find their youngest common ancestor. Say the node is like: struct node{ int data; struct node*left, *right; }; i.e the father field is not there. Please note that it is not a binary search tree, but just a binary tree. Thanks, Himanshu -- 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. -- How soon 'not now' becomes 'never'... -- 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] Finding youngest common ancestor of two nodes in a binary tree
yup atul algo is correct (cur_data - node-right) * ( cur_data- node-left) -1 for ancestors On Thu, Apr 8, 2010 at 10:19 AM, atul verma atul.ii...@gmail.com wrote: Its very simple to solve this. Start from root. Compare the value of current node data value to both nodes. 1. if both are greater than current node then traverse node-right 2. if both are lesser than current node then traverse node-left 3. else return current node pointer. Any comments, Atul On Thu, Apr 8, 2010 at 10:15 AM, Pramod Negi negi.1...@gmail.com wrote: could you please elucidate more?? On Wed, Apr 7, 2010 at 10:34 PM, Himanshu Aggarwal lkml.himan...@gmail.com wrote: For a given binary tree, given the root and two node pointers, how can we find their youngest common ancestor. Say the node is like: struct node{ int data; struct node*left, *right; }; i.e the father field is not there. Please note that it is not a binary search tree, but just a binary tree. Thanks, Himanshu -- 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.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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- How soon 'not now' becomes 'never'... -- 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: Largest span of Increasing Pair in an array
@ankur how u can solve it in o(n) i suppose u need atleast o(n lgn) On Sun, Sep 6, 2009 at 2:52 PM, ankur aggarwal ankur.mast@gmail.comwrote: o(n) is the best sol known to me.. On Sun, Sep 6, 2009 at 1:54 PM, Pramod Negi negi.1...@gmail.com wrote: i guess sorting will do the work. any other constraint?? On Sun, Sep 6, 2009 at 9:52 AM, p0r$h 1987.shis...@gmail.com wrote: Given an array of integers A[N], find the maximum value of (j-k) such that A[k] = A[j] jk. I am looking for a solution with time complexity better than O(N^2). --~--~-~--~~~---~--~~ 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.comalgogeeks%2bunsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~--- -- 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.