[algogeeks] Tree Center Problem
hi, given a tree with N nodes find the node such that its average total distance from each other node is smallest i.e. if nodes are labeled 0N-1 then find i such that[ SUM d(i, j ){0=jN}] /N is minimum NOTE: This is different from the classic problem of finding tree center where tree center is the node such that its maximum distance to other nodes is minmum this must be done is O(n) time and O(n) space sample input : an integer array Tree with N elements where each element T[a]=b represents an edge (a,b) when a!=b Tree[]={14,9,11,16,14,0,11,6,14,11,3 ,16,13,17,12, 1, 5,17} correct answer is 16. My solution was to find (SUM(i,j) {0=jN})/N for any one value of i using dfs then find it for other is value of i's by the fact that if there is an edge in tree (a,b) and average total distance for node a is X and then average total distance for node be can be found in constant time as follows if we remove the edge (a,b) from the tree then there will be two connected components in the tree one that contains node a and other that contains node b. Let number of nodes in first be Na and number of nodes in second be Nb then average total distance of node b is = X + Na - Nb. Na, and Nb can be found in linear time again using dfs for each node. Somehow this solution gives wrong answer , 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+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Tree Center Problem
anyone? -- 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] Syllogism
Thus above statement is true if and only it is given that there are some girls who are not Beautiful. On Tue, Aug 23, 2011 at 7:50 PM, Bharat Kul Ratan bharat.kra...@gmail.comwrote: Statement: Some girls are beautiful IMO , this means you a set of all girls and after that comes statement about some otherwise statement would be for all girls. There is something left in the set after statement which is nothing but complement of beautiful i.e. not beautiful so, the conclusion must be true. -- 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/-/oEx7FBp6V7IJ. 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] convert a vector containing octal representation of a number to decimal number
int num = 0; for(int i=0;iA.size();i++){ num=num||(A[i]3*i); } printf(%d,num); I think this will do. On Sun, Aug 21, 2011 at 2:25 PM, sarvesh saran aquarian.thun...@gmail.comwrote: Hi, I have a vectorint A or an array (for C guys) that contains the octal representation of a number. So the array can be something like: [1,5,7] or [7,7,5,6,3,4,2] etc i.e no number in the array can be = 8. Now given this array, I need to convert it its decimal representation. The naive way to do it would be to scan array from left to right, take each digit, multiply by 8 pow (x) where x is from 0 to ...n and compute sum. i.e something like: int oct = 1; int num = 0; for(array length){ num+= oct * A[i]; oct = oct * 8; } is there a faster way to do this? maybe using some STL container or algorithm. ? thanks, sarvesh -- 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] convert a vector containing octal representation of a number to decimal number
int num = 0; for(int i=0;iA.size();i++){ num=num||(A[i]3*i); } printf(%d,num); I think this will do. Given the number is with in the range of integer. On Sun, Aug 21, 2011 at 3:40 PM, Nitin Nizhawan nitin.nizha...@gmail.comwrote: int num = 0; for(int i=0;iA.size();i++){ num=num||(A[i]3*i); } printf(%d,num); I think this will do. On Sun, Aug 21, 2011 at 2:25 PM, sarvesh saran aquarian.thun...@gmail.com wrote: Hi, I have a vectorint A or an array (for C guys) that contains the octal representation of a number. So the array can be something like: [1,5,7] or [7,7,5,6,3,4,2] etc i.e no number in the array can be = 8. Now given this array, I need to convert it its decimal representation. The naive way to do it would be to scan array from left to right, take each digit, multiply by 8 pow (x) where x is from 0 to ...n and compute sum. i.e something like: int oct = 1; int num = 0; for(array length){ num+= oct * A[i]; oct = oct * 8; } is there a faster way to do this? maybe using some STL container or algorithm. ? thanks, sarvesh -- 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] convert a vector containing octal representation of a number to decimal number
@sanjay, oops, my intention was bitwise OR On Sun, Aug 21, 2011 at 4:25 PM, sarvesh saran aquarian.thun...@gmail.comwrote: Hi Prakash, I'll paste the exact description of the problem: A non-empty array A of N elements contains octal representation of a non-negative integer K, i.e. each element of A belongs to the interval [0; 7] (both ends included). Write a function that returns the number of bits set to 1 in the binary representation of K. thanks, Sarvesh i.e take any decimal number, convert to base 8 and then store each digit of base 8 representation in an array. So the question is, given such an array get back the original number. thanks, Sarvesh On Sun, Aug 21, 2011 at 4:13 PM, Prakash D cegprak...@gmail.com wrote: A[i]3*i why is it needed to convert from base 8 to base 10?? On Sun, Aug 21, 2011 at 4:07 PM, Sanjay Rajpal srn...@gmail.com wrote: Hi your intention was logical OR or BITWISE OR ? u did Logical. Sanju :) On Sun, Aug 21, 2011 at 3:30 AM, sarvesh saran aquarian.thun...@gmail.com wrote: Hi Nitin, thanks that makes sense. I will try that out. I have another question. Is there a really fast way of converting a hexadecimal string say 02F9A to its decimal representation in C++? thanks, Sarvesh thanks, Sarvesh On Sun, Aug 21, 2011 at 3:41 PM, Nitin Nizhawan nitin.nizha...@gmail.com wrote: int num = 0; for(int i=0;iA.size();i++){ num=num||(A[i]3*i); } printf(%d,num); I think this will do. Given the number is with in the range of integer. On Sun, Aug 21, 2011 at 3:40 PM, Nitin Nizhawan nitin.nizha...@gmail.com wrote: int num = 0; for(int i=0;iA.size();i++){ num=num||(A[i]3*i); } printf(%d,num); I think this will do. On Sun, Aug 21, 2011 at 2:25 PM, sarvesh saran aquarian.thun...@gmail.com wrote: Hi, I have a vectorint A or an array (for C guys) that contains the octal representation of a number. So the array can be something like: [1,5,7] or [7,7,5,6,3,4,2] etc i.e no number in the array can be = 8. Now given this array, I need to convert it its decimal representation. The naive way to do it would be to scan array from left to right, take each digit, multiply by 8 pow (x) where x is from 0 to ...n and compute sum. i.e something like: int oct = 1; int num = 0; for(array length){ num+= oct * A[i]; oct = oct * 8; } is there a faster way to do this? maybe using some STL container or algorithm. ? thanks, sarvesh -- 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. -- 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. -- 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] convert a vector containing octal representation of a number to decimal number
I guess, earlier sarvan simply wanted to calculate result = SUM {0=i N } A[i]*(8^i) in which 8^i = 2^(3*i) which is equivalent to right shifting 3*i since each A[i] is octal it is just 3bits long , we need not add we can simply shift and do OR. On Sun, Aug 21, 2011 at 10:16 PM, Sanjay Rajpal srn...@gmail.com wrote: @Nitin : could u explain ur logic ? Sanju :) On Sun, Aug 21, 2011 at 9:24 AM, Nitin Nizhawan nitin.nizha...@gmail.comwrote: @sanjay, oops, my intention was bitwise OR On Sun, Aug 21, 2011 at 4:25 PM, sarvesh saran aquarian.thun...@gmail.com wrote: Hi Prakash, I'll paste the exact description of the problem: A non-empty array A of N elements contains octal representation of a non-negative integer K, i.e. each element of A belongs to the interval [0; 7] (both ends included). Write a function that returns the number of bits set to 1 in the binary representation of K. thanks, Sarvesh i.e take any decimal number, convert to base 8 and then store each digit of base 8 representation in an array. So the question is, given such an array get back the original number. thanks, Sarvesh On Sun, Aug 21, 2011 at 4:13 PM, Prakash D cegprak...@gmail.com wrote: A[i]3*i why is it needed to convert from base 8 to base 10?? On Sun, Aug 21, 2011 at 4:07 PM, Sanjay Rajpal srn...@gmail.comwrote: Hi your intention was logical OR or BITWISE OR ? u did Logical. Sanju :) On Sun, Aug 21, 2011 at 3:30 AM, sarvesh saran aquarian.thun...@gmail.com wrote: Hi Nitin, thanks that makes sense. I will try that out. I have another question. Is there a really fast way of converting a hexadecimal string say 02F9A to its decimal representation in C++? thanks, Sarvesh thanks, Sarvesh On Sun, Aug 21, 2011 at 3:41 PM, Nitin Nizhawan nitin.nizha...@gmail.com wrote: int num = 0; for(int i=0;iA.size();i++){ num=num||(A[i]3*i); } printf(%d,num); I think this will do. Given the number is with in the range of integer. On Sun, Aug 21, 2011 at 3:40 PM, Nitin Nizhawan nitin.nizha...@gmail.com wrote: int num = 0; for(int i=0;iA.size();i++){ num=num||(A[i]3*i); } printf(%d,num); I think this will do. On Sun, Aug 21, 2011 at 2:25 PM, sarvesh saran aquarian.thun...@gmail.com wrote: Hi, I have a vectorint A or an array (for C guys) that contains the octal representation of a number. So the array can be something like: [1,5,7] or [7,7,5,6,3,4,2] etc i.e no number in the array can be = 8. Now given this array, I need to convert it its decimal representation. The naive way to do it would be to scan array from left to right, take each digit, multiply by 8 pow (x) where x is from 0 to ...n and compute sum. i.e something like: int oct = 1; int num = 0; for(array length){ num+= oct * A[i]; oct = oct * 8; } is there a faster way to do this? maybe using some STL container or algorithm. ? thanks, sarvesh -- 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. -- 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
Re: [algogeeks] Syllogism
Statement: Some girls are beautiful' Ex B(x) , there exist at least one girl who is beautiful Some girls are not beautiful Ex !B(x), there exist at least one girl who is beautiful I do not think first implies the second. On Sat, Aug 20, 2011 at 3:13 PM, vikas singh shyguy1...@gmail.com wrote: On Sat, Aug 20, 2011 at 10:26 AM, geek_one abhishekgupta.it...@gmail.comwrote: Statement: Some girls are beautiful. Conclusion: Some girls are not beautiful. is the conclusion is true on the basis of Statement? I think there is a doubt in this statement. you can't say ,some girls are not beautiful. Because, it may so happen that All girls are beautiful. ( All is a particular case of some, you must be knowing it.) and here lies the conflict, so, some girls are not beautiful is not the answer. -- 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/-/SGSGlmwYFBAJ. 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. -- Thanks and Regards VIKAS SINGH MCA- final year NIT DURGAPUR email: vikas.singh1...@gmail.com shyguy1...@gmail.com http://smrit.wordpress.com -- 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] Syllogism
there was a small typo in my last mail, corrected here Statement: Some girls are beautiful' Ex B(x) , there exist at least one girl who is beautiful Some girls are not beautiful Ex !B(x), there exist at least one girl who is NOT beautiful I do not think first implies the second. On Sat, Aug 20, 2011 at 6:49 PM, Nitin Nizhawan nitin.nizha...@gmail.comwrote: Statement: Some girls are beautiful' Ex B(x) , there exist at least one girl who is beautiful Some girls are not beautiful Ex !B(x), there exist at least one girl who is beautiful I do not think first implies the second. On Sat, Aug 20, 2011 at 3:13 PM, vikas singh shyguy1...@gmail.com wrote: On Sat, Aug 20, 2011 at 10:26 AM, geek_one abhishekgupta.it...@gmail.com wrote: Statement: Some girls are beautiful. Conclusion: Some girls are not beautiful. is the conclusion is true on the basis of Statement? I think there is a doubt in this statement. you can't say ,some girls are not beautiful. Because, it may so happen that All girls are beautiful. ( All is a particular case of some, you must be knowing it.) and here lies the conflict, so, some girls are not beautiful is not the answer. -- 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/-/SGSGlmwYFBAJ. 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. -- Thanks and Regards VIKAS SINGH MCA- final year NIT DURGAPUR email: vikas.singh1...@gmail.com shyguy1...@gmail.com http://smrit.wordpress.com -- 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] Syllogism
@geek_one, its false, some girls are beautiful does not imply that some girls are not beautiful On Sat, Aug 20, 2011 at 10:36 PM, Yogesh Bhati ybha...@gmail.com wrote: conclusion : Is at least some girls are beautiful dnt knw abt rest bt some are -- 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] Prime numbers
Hi Dod, Could you pls expalin what this algorithm is doing and from where you got it. Thanks Nitin On Wed, Aug 17, 2011 at 2:56 AM, Don dondod...@gmail.com wrote: I wrote a program to print prime numbers, but it is not very fast. Can someone help me figure out why? #include stdio.h /* This program implements a blindingly fast algorithm to find prime numbers, using an elegant recursive method. */ int _(int n, int m, int d, int t=0) { int r; if (t) return d?1+_(n,m,d-1,d):n?_(n-1,m,m,n):0; for(r=m!=n; d*(tn); ++t) r = _(n,_(t,m,0,1),d-1)|!_(t,1,t); return r*n; } /*-- Print primes up to the requested value */ int main(int argc, char* argv[]) { for(int n = 2; n = 1000; n++) printf(%d is%s prime\n,n, _(n,1,n,0)?: not); return 0; } -- 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] Re: Number theory
@Puneet, you are right but we can have only n-1 dividers. On Wed, Aug 17, 2011 at 4:15 PM, Puneet Goyal puneetgoya...@gmail.comwrote: I think it should be 2^n -1 Explanation We can visualize it as n balls are placed and we have to place some dividers (max=n) in betweek to divide them into groups. If we choose no divider its nC0 , but we dont have to include it With 1 divider its nC1 and so on.. So the total no. of ways will be (nC0+nC1+nC2..nCn)-nC0= 2^n-1 Regards, Puneet On Wed, Aug 17, 2011 at 4:05 PM, Rohit Srivastava access2ro...@gmail.comwrote: +1 to nitin On Wed, Aug 17, 2011 at 2:48 PM, Vijay Kansal vijaykans...@gmail.comwrote: my bad 2^(n-1)... On Aug 17, 2:17 pm, Vijay Kansal vijaykans...@gmail.com wrote: @nitin it must be 2^n i think On Aug 17, 3:48 am, Bharat Kul Ratan bharat.kra...@gmail.com wrote: It might be useful: http://www.artofproblemsolving.com/Wiki/index.php/Partition_%28combin... -- 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. -- --- Puneet Goyal Student of B. Tech. III Year (Software Engineering) Delhi Technological University, Delhi --- -- 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] Factorial Algorithms
@Gaurav , if you are able to find any resource that explains the logic of these algos, please let me know. On Sat, Aug 13, 2011 at 9:50 AM, Gaurav Menghani gaurav.mengh...@gmail.comwrote: Thanks for the link. I was unaware of such algorithms. These would come handy in programming contests. On Fri, Aug 12, 2011 at 3:00 PM, Nitin Nizhawan nitin.nizha...@gmail.com wrote: http://www.luschny.de/math/factorial/FastFactorialFunctions.htm Does anyone know of resource for good/detailed explanation of factorial algorithms on this site? -- 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. -- Gaurav Menghani -- 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] GS apti ques!
a = (1-0.2) b = (1-0.3) c = (1- 0.4) a*b*(1-c) + a*(1-b)*c + (1-a)*b*c + a*b*c = 0.788 On Wed, Aug 17, 2011 at 5:08 PM, Romil ... vamosro...@gmail.com wrote: @Priya: A mistake from my side. The answer should be 1-0.212 i.e. 0.788 Sorry for this mistake. @Kumar: Yours is wrong. Check it again. On Wed, Aug 17, 2011 at 4:42 PM, Romil ... vamosro...@gmail.comwrote: Kumar's approach would not do perhaps. I simply eliminated the undesired cases. Those include the one when none of them is active and when only one of them is active. @Kumar: You should have also added the term abc. On Wed, Aug 17, 2011 at 4:39 PM, priya ramesh love.for.programm...@gmail.com wrote: @romil: how did you solve this?? -- 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. -- Romil -- Romil -- 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] What is the reason??
I think this happens because EOF on stream is set when fscanf actually tries to read beyond EOF but reads 0 characters and therefore printf prints the previous value in s. On Wed, Aug 17, 2011 at 5:11 PM, kumar raja rajkumar.cs...@gmail.comwrote: while(!feof(fp)) { fscanf(fp,%s,s); printf(%s,s); } The last word in the file is printing twice .What is the reason for this to happen??? -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- 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] What is the reason??
It seems this is the way it is designed to work, some operation has to read the EOF to acually set the EOF flag on the stream. In this case its fscanf. feof() function does not try to read next to see if EOF is reached it just check a flag on the stream which is set when some operation encounters EOF. On Wed, Aug 17, 2011 at 5:45 PM, kumar raja rajkumar.cs...@gmail.comwrote: Actually when all the words are over then it should reach end of file marker which is typically some ascii character ,not on reading it again using fscanf... Why it will set only after fscanf is failed to read from it?? On 17 August 2011 17:19, Nitin Nizhawan nitin.nizha...@gmail.com wrote: I think this happens because EOF on stream is set when fscanf actually tries to read beyond EOF but reads 0 characters and therefore printf prints the previous value in s. On Wed, Aug 17, 2011 at 5:11 PM, kumar raja rajkumar.cs...@gmail.comwrote: while(!feof(fp)) { fscanf(fp,%s,s); printf(%s,s); } The last word in the file is printing twice .What is the reason for this to happen??? -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- 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] De shaw ques!
N = 935*q + 69 N%38 = 31, 16, 1, 24, 9, 32, 17, 2 for { q = 0,1,2,3,4,5,6,7. } On Wed, Aug 17, 2011 at 5:54 PM, aditya kumar aditya.kumar130...@gmail.comwrote: @priya . i have shown you my method . write your method and we shall discuss it . On Wed, Aug 17, 2011 at 5:52 PM, sukran dhawan sukrandha...@gmail.comwrote: On Wed, Aug 17, 2011 at 5:39 PM, priya ramesh love.for.programm...@gmail.com wrote: if a number is divided by 935 remainder is 69. if same no. is divided by 38, what will be the remainder? -- answer is 16.t 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. -- 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: Algorithms For Interviews
http://www.fileflyer.com/view/XyBZGA8 On Tue, Aug 16, 2011 at 8:07 PM, Yasir yasir@gmail.com wrote: Typo: achieves -- archives -- 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/-/ccCkVtfs3y4J. 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: Algorithms For Interviews
sent to you ravi On Tue, Aug 16, 2011 at 8:16 PM, ravi kumar ravikumar...@gmail.com wrote: heyy nitin.. it says da file izz locked .. can u mail me da buk.. thanx in advance -- 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] Number theory
I think 2^(n-1) - 1 On Tue, Aug 16, 2011 at 8:36 PM, sameer gupta gupta.sameer...@gmail.comwrote: no. of ways you can write a no. as sum of other non-zero positive integers like 3 can be written in 3 ways: 1+1+1, 1+2 2+1 imp. 2+1 and 1+2 are different find the answer and give and prove formula for any value 'n' -- 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] Prime numbers
Can someone pls explain what dod's algorithm is doing? Dod, from where did you get this recursive algo? On Wed, Aug 17, 2011 at 8:45 AM, Dipankar Patro dip10c...@gmail.com wrote: Sieve's is the fastest in generating prime numbers. +1 to Sandeep and Sanjay On 17 August 2011 08:21, Sanjay Rajpal sanjay.raj...@live.in wrote: Agree with Sandeep :) Try this link http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes. Hope it helps :) Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India On Tue, Aug 16, 2011 at 2:28 PM, sandeep pandey sandeep.masum4...@gmail.com wrote: try to implement sieve. it,s a well known algorithm to find out d prime frequently. -- 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. -- ___ Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees -- 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] an array question
radix sort the digits wrong way (left most digit first), and then concatenate On Fri, Aug 12, 2011 at 6:12 PM, Yasir yasir@gmail.com wrote: Kindly check it with both the examples. It won't work. -- 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/-/VlT1DNH-vPkJ. 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] Factorial Algorithms
http://www.luschny.de/math/factorial/FastFactorialFunctions.htm Does anyone know of resource for good/detailed explanation of factorial algorithms on this site? -- 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] Trees
i guess answer is c. 4 n*i+1 On Thu, Aug 11, 2011 at 8:01 PM, rShetty rajeevr...@gmail.com wrote: A complete n- array tree in which each node has n children or no children, let i be the number of internal nodes and L be the number of leaves in a complete n- array tree. If L=41 and i=10 what is the value of n. a. 3b. 6 c. 4 How to solve such problems?? -- 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] Re: Trees
I am also getting , 5 as answer now. here is what I did. In any n-ary tree we can add one internal node by adding n-children to any one of its leaf nodes. This operation creates one internal node and at the cost one leaf node and adds n new leaf nodes. L(i) be leaf nodes in a tree with i internal nodes, then L(i+1) = L(i) + n - 1 L(0) = 1 , since tree with root node has 0 internal nodes and one leave node L(i) = L(0) + i*(n-1) or L(i) = i*(n-1) + 1 On Thu, Aug 11, 2011 at 11:34 PM, Raman raman.u...@gmail.com wrote: How is this formula obtained? -- 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/-/zBQSNmP4ITQJ. 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] Design .. how to attack ???
I feel such questions are asked to test OO skills so try to identify all the entities and verbs in the system. Also describing key interfaces in detail should help. On Fri, Aug 12, 2011 at 11:20 AM, MAC macatad...@gmail.com wrote: Hi guys , Can anyone help me in understanding what is expected when some some one asks you design a car rental system . Exactly what all is required to be told to the interviewer . -- thanks --mac -- 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] Re: SPOJ CENCRY
3 eee cjpvbhntzgm aeiouaeiouae vfghjklwerf eouaeioicou On Wed, Aug 10, 2011 at 12:06 PM, kartik sachan kartik.sac...@gmail.comwrote: any body tell the test cases?? -- 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] Re: SPOJ CENCRY
inp: 3 eee vfghjklwerf out: cjpvbhntzgm aeiouaeiouae eouaeioicou On Wed, Aug 10, 2011 at 12:40 PM, Nitin Nizhawan nitin.nizha...@gmail.comwrote: 3 eee cjpvbhntzgm aeiouaeiouae vfghjklwerf eouaeioicou On Wed, Aug 10, 2011 at 12:06 PM, kartik sachan kartik.sac...@gmail.comwrote: any body tell the test cases?? -- 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] STL sort
what is comp in your code? On Wed, Aug 10, 2011 at 6:19 PM, aanchal goyal goyal.aanch...@gmail.comwrote: I have a vector of stuct, how to sort this vector? problem is I can't overload the '' operator in struct definition, as i want to sort by 'x' one time, and then by 'y'. I tried to write the comparator function separatley but its no working. How to do it? #includeiostream #includealgorithm #includevector using namespace std; typedef struct { int x; int y; }point; struct comp_x { bool operator()(point a, point b) return a.xb.x; } struct comp_y { bool operator()(point a, point b) return a.yb.y; } int main() { vectorpoint vc; int n; cinn; point a; for(int i=0;in;i++) { cina.x; cina.y; vc.push_back(a); } coutendl; sort(vc.begin(), vc.end(), comp); for(int i=0;in;i++) { coutvc[i].x vc[i].yendl; } system(pause); return 0; } -- Regards,* Aanchal Goyal*. -- 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] STL sort
bool operator()(point a, point b){ return a.xb.x; } remove references it should work. following is working code. #includeiostream #includealgorithm #includevector using namespace std; typedef struct { int x; int y; }point; struct comp_x { bool operator()(point a, point b){ return a.xb.x; } } compx; struct comp_y { bool operator()(point a, point b){ return a.yb.y; } } compy; int main() { vectorpoint vc; int n; cinn; point a; for(int i=0;in;i++) { cina.x; cina.y; vc.push_back(a); } coutendl; sort(vc.begin(), vc.end(), compx); coutBy X\n; for(int i=0;in;i++) { coutvc[i].x vc[i].yendl; } sort(vc.begin(), vc.end(), compy); coutBy Y\n; for(int i=0;in;i++) { coutvc[i].x vc[i].yendl; } return 0; } On Wed, Aug 10, 2011 at 6:31 PM, aanchal goyal goyal.aanch...@gmail.comwrote: sorry, comp is either comp_x or comp_y On Wed, Aug 10, 2011 at 6:24 PM, Nitin Nizhawan nitin.nizha...@gmail.comwrote: what is comp in your code? On Wed, Aug 10, 2011 at 6:19 PM, aanchal goyal goyal.aanch...@gmail.comwrote: I have a vector of stuct, how to sort this vector? problem is I can't overload the '' operator in struct definition, as i want to sort by 'x' one time, and then by 'y'. I tried to write the comparator function separatley but its no working. How to do it? #includeiostream #includealgorithm #includevector using namespace std; typedef struct { int x; int y; }point; struct comp_x { bool operator()(point a, point b) return a.xb.x; } struct comp_y { bool operator()(point a, point b) return a.yb.y; } int main() { vectorpoint vc; int n; cinn; point a; for(int i=0;in;i++) { cina.x; cina.y; vc.push_back(a); } coutendl; sort(vc.begin(), vc.end(), comp); for(int i=0;in;i++) { coutvc[i].x vc[i].yendl; } system(pause); return 0; } -- Regards,* Aanchal Goyal*. -- 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. -- Regards,* Aanchal Goyal*. -- 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] m'th max element
Selection algorithm, http://en.wikipedia.org/wiki/Selection_algorithm On Mon, Aug 8, 2011 at 3:59 PM, nick tarunguptaa...@gmail.com wrote: how will you find the m'th maximum element in an unsorted array of integers? -- 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/-/aYU_PfGHiNkJ. 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] Random number
following solution should work but it uses an array so its ST is O(N) #include stdio.h #include time.h #define MAX 500 /** copied from wikipedia * */ unsigned m_w = time(NULL);/* must not be zero */ unsigned m_z = 300;/* must not be zero */ unsigned long get_random() { m_z = 36969 * (m_z 65535) + (m_z 16); m_w = 18000 * (m_w 65535) + (m_w 16); return (m_z 16) + m_w; /* 32-bit result */ } // CLRS void randomize(int list[],int size){ for(int i=0;isize;i++){ int rand = i+get_random()%(size-i); // swap int tmp = list[i]; list[i] = list[rand]; list[rand] = tmp; } } int main(){ int A[MAX]; int N,M; // assuming NMAX , MN scanf(%d,N); scanf(%d,M); for(int i=0;iN;i++){ A[i]=i; } randomize(A,N); for(int i=0;iM;i++){ printf(%d ,A[i]); } } On Mon, Aug 8, 2011 at 6:02 PM, Gaurav Menghani gaurav.mengh...@gmail.comwrote: The space complexity is O(1) I know about hash-tables. Can you implement with O(1) space complexity? On Mon, Aug 8, 2011 at 10:56 AM, 석문기 smgs2...@gmail.com wrote: Box-muller method is the good solution without a lot of computation overhead 2011/8/8 Puneet Gautam puneet.nsi...@gmail.com You may be right..we cant remove collisions in O(1) time... But hey, hash table is still an effective way.. On 8/8/11, Puneet Gautam puneet.nsi...@gmail.com wrote: Hey avoiding collisions using hash table can be real easy : eg: if 192 is the no generated let it hash to say index 7 of hash table...so when it is again generated, it hashes to the same 7th index of hash table, but we have a non zero value already present at that index , 192 so we can reject this generated no. and proceed to the next one.. Whereas in an array , avoiding collision is a really hectic way...u need to scan all the previously generated no.s for duplicacy...well that aint gonna run in O(1) time.. So implementing hash table reduces that overhead and runs it in O(1) time..(it just has to check one if condition)with a bigger constant. And moreover, we may even dont want an ordered sequence...just put the generated no.s in hash table as soon as they are generated...dats it.. then afterwards display that hash table.. Did u get me...? On 8/7/11, Gaurav Menghani gaurav.mengh...@gmail.com wrote: We can have a sorted sequence and display them in random order, but that is the same problem. How do we display them in random order? We need to have a sequence of random indices, that is the same problem as having random numbers, isn't it. Moreover, I don't think collisions can be avoided in less than O(n). We can have an efficient hash-table, but I am not sure how it can be done in O(1) or better. On Sat, Aug 6, 2011 at 12:37 PM, Puneet Gautam puneet.nsi...@gmail.com wrote: I rhink to avoid collisions altogether we should generate an ordered sequence , in a dec. or inc. order and display them randomly, i mean: Let say a[10] contains all the random no.s , map all the 10 indexes to a hash table and then display the arrays with the hashed index... I think it may work... what say..? On 8/5/11, Gaurav Menghani gaurav.mengh...@gmail.com wrote: 1. Get a good seed. 2. Increase the degree of the polynomial. This is no fixed algorithm, if you find that more than T steps have passed and a new number has not been generated, you can always change the polynomial. And, please remember it is a 'pseudo-random number generator'. You can read the theory about PRNGs and LFSRs, all of them repeat. On Fri, Aug 5, 2011 at 7:14 PM, payel roy smithpa...@gmail.com wrote: How do you guarantee termination of your algorithm if duplication occurs ?? On 5 August 2011 18:25, Gaurav Menghani gaurav.mengh...@gmail.com wrote: You might want to read the theory on Pseudo-Random Number Generators [0] and Linear Feedback Shift Register [1] The basic way of generating a random number is taking up a polynomial, f(x) = ax^n + bx^(n-1) + .. + yx + z, and finding f(i + seed) % N, where i is the ith random number you want, and seed can be anything random available, for example, you can find the current millisecond using time.h functions. A simple implementation, without the time thing is below: #includeiostream using namespace std; int poly[10],pn,N,M; int get(int seed) { int t=0; for(int i=0;ipn;i++) { int res=poly[i]; for(int j=1;j=(i+1);j++) { res = (res*seed); if(res=N) res%=N; } t+=res; if(t=N) t%=N; } t=(t+seed); t%=N; return t; } void setup_prng() { pn=5; poly[0]=2; poly[1]=3; poly[2]=5; poly[3]=7; poly[4]=11; N=200;
Re: [algogeeks] suggest simple code for
I think this should work void finddepth(Node *node,int depth){ if(node!=NULL){ depth = max( finddepth(node-left,depth+1), finddepth(node-right,depth+1) ); } return depth; } On Mon, Aug 8, 2011 at 6:33 PM, jagrati verma jagrativermamn...@gmail.comwrote: finding the depth or height of a tree. -- 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] Re: nlogn, in-place, iterative mergesort?
Thanks everyone, Achieving nlogn, interative, and in-place separately is easy. But I did not know of algo that achieves all these simultaneously for merge sort. Thanks DK for pointing to that paper I wonder if algorithm presented in paper is also stable. --Nitin On Sun, Aug 7, 2011 at 5:10 PM, immanuel kingston kingston.imman...@gmail.com wrote: @DK and Amit, thanks for correcting my understanding. On Sun, Aug 7, 2011 at 3:51 PM, amit karmakar amit.codenam...@gmail.comwrote: @DK Hmm, i do understand what you said. Maybe, i should make it clear that i just wanted to tell that implementing a non-recursive merge-sort will not require explicit stacks and is actually easier to implement. This was because someone mentioned using stacks to remove recursion. I didn't mean to tell anything more than that. :) On Aug 7, 3:07 pm, DK divyekap...@gmail.com wrote: @Amit and @Immanuel: You're not getting the point. Merge sort is not in-place because it requires an extra O(N) array during the merge step. The problem asks not to remove the recursive nature of the merge-sort but to remove the non-in-place nature of merge sort by removing the need for that extra array. This is a research problem that has been solved and there have been multiple papers on the topic. I've posted the earliest one that forms the basis of this field. -- DK http://gplus.to/divyekapoorhttp://twitter.com/divyekapoorhttp://www.divye.in -- 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] Re: nlogn, in-place, iterative mergesort?
good Joke :) On Mon, Aug 8, 2011 at 1:43 AM, DK divyekap...@gmail.com wrote: @Nitin: In-place merge sorts are not stable (atleast I haven't come across a stable one - you might want to create one as research? ;) ). -- 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/-/8r0X6w8Z3eIJ. 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: adobe
http://trickofmind.com/?p=1080 i think this will help, we need to find Carmichael number or somthing related to ETF for the input number. On Sat, Aug 6, 2011 at 12:24 PM, Nikhil Gupta nikhilgupta2...@gmail.comwrote: @sumit, these numbers containing all ones are not in binary representation. They are in decimal system. On Sat, Aug 6, 2011 at 9:51 AM, sahil gujral gujralsa...@gmail.comwrote: yes u r wrong.. 1 is nt divisible by 23 On Sat, Aug 6, 2011 at 9:15 AM, sumit sumitispar...@gmail.com wrote: This looks quite simple. Every number ending in 3 follows a pattern.eg- 3 - 111 13 - 11 23 - 1 etc we can find the reauired no. by : suppose input no. is 33 In every case leave the no at 1's place(least significant) i.e. 3, In 33 you will be left with 3(after removal of 3 at first place). Now ,3 *(rest of nos +1 ) is your answer (in case of 33 it is 3*(3+1) = 12 i.e ). for 103 it is 3*(10+1) = 33 1's. Correct if I am wrong. On Aug 5, 4:33 pm, Manee mani.ma...@gmail.com wrote: ADOBE asks the very basic C/C++ questions one of their toughest however was : every number ending in 3 has a multiple of the form 111...111 e.g 3 has 111 13 has 11 so on.. find the algo for finding the number for an input number ending in 3. On Aug 5, 2:33 pm, Agyat jalsa.n.sa...@gmail.com wrote: hey, guys adobe is visiting our campus. So those who know questions that adobe asked in written or interview, please post here as it will be of great help (as adobe has visited some colleges already). Thank you in advance. -- 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. -- Nikhil Gupta Senior Co-ordinator, Publicity CSI, NSIT Students' Branch NSIT, New Delhi, India -- 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] nlogn, in-place, iterative mergesort?
inplace? On Sat, Aug 6, 2011 at 10:27 PM, immanuel kingston kingston.imman...@gmail.com wrote: Yes. just remove the recursive part using 2 stacks. Thanks, Immanuel On Fri, Aug 5, 2011 at 6:51 PM, Nitin Nizhawan nitin.nizha...@gmail.comwrote: does anyone know of any in-place, iterative mergesort algorithm with nlogN worst case complexity? It would be good if it is stable also. TIA Nitin -- 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] pls help
Or one could just simulate a counting from 0 to (numchars^N)-1 in base numchars. ... code: void printit(int N,char chars[],int index[]){ for(int i=0;iN;i++){ printf(%c,chars[index[i]]); } printf(\n); } void generate(int numchars,char chars[],int N){ int index[100]={0}; int allmax=0; int maxdigit=numchars-1; printit(N,chars,index); while(!allmax){ // add one; index[0]++; allmax=0; for(int i=0;iN;i++){ if(index[i]=numchars){ index[i]=0; index[i+1]++; } if(i==0index[i]==maxdigit){ allmax=1; } allmax = (index[i]==maxdigit)?allmax1:0; } printit(N,chars,index); } } int main(){ char chars [] ={'p','o'}; int numchars =sizeof(chars)/sizeof(char); int N=3; generate(numchars,chars,N); } On Fri, Aug 5, 2011 at 12:58 PM, Gaurav Menghani gaurav.mengh...@gmail.comwrote: An Implementation: #includeiostream #includestring using namespace std; string alphabet; int maxlen; void backtrack(string s,int l) { if(l==maxlen) { coutsendl; return; } s.push_back('-'); for(int i=0;ialphabet.size();i++) { s[l]=alphabet[i]; backtrack(s,l+1); } } int main() { maxlen=3; alphabet=op; backtrack(,0); return 0; } On Fri, Aug 5, 2011 at 12:42 PM, Kamakshii Aggarwal kamakshi...@gmail.com wrote: @gaurav:i could not understand ur sol.can u explain it again.. On Fri, Aug 5, 2011 at 12:32 PM, Gaurav Menghani gaurav.mengh...@gmail.com wrote: On Fri, Aug 5, 2011 at 12:20 PM, Kamakshii Aggarwal kamakshi...@gmail.com wrote: given a set of letters and a length N, produce all possible output.(Not permutation). For example, give the letter (p,o) and length of 3, produce the following output(in any order you want, not just my example order) ppp ppo poo pop opp opo oop ooo another example would be given (a,b) and length 2 answer: ab aa bb ba -- Regards, Kamakshi kamakshi...@gmail.com This can be done easily by backtracking void backtrack(string s, int l) { if(l == maxlen) { coutsendl; return; } s.push_back('-'); for(int i=0;ialphabet.size();i++) { s[l]=alphabet[i]; backtrack(s,l+1); } } -- Gaurav Menghani -- 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. -- Regards, Kamakshi kamakshi...@gmail.com -- 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. -- Gaurav Menghani -- 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] pls help
Ok, Thanks On Fri, Aug 5, 2011 at 2:53 PM, Gaurav Menghani gaurav.mengh...@gmail.comwrote: Even if the number of elements is more than two, it is possible with bitwise operations, but it gets clumsy. Suppose your alphabet has 4 characters. You can either: - Count from 0 to (14*n)-1 and use four bits to denote the selection of the alphabet. Also, only one bit amongst those four should be set. It is highly inefficient. - Keep n nested loops and inside each loop you iterate from 0 to (14)-1 and use the standard bitwise operations. The con here is that you have to hardcode the number of nested loops. On Fri, Aug 5, 2011 at 2:44 PM, Nitin Nizhawan nitin.nizha...@gmail.com wrote: @Varun I think it can be done using bits, if input character set has only two elements. Or could u plz explain? On Fri, Aug 5, 2011 at 2:29 PM, Varun Jakhoria varunjakho...@gmail.com wrote: I think it can be done using bitwise ANDing with a mask On Fri, Aug 5, 2011 at 12:58 PM, Gaurav Menghani gaurav.mengh...@gmail.com wrote: An Implementation: #includeiostream #includestring using namespace std; string alphabet; int maxlen; void backtrack(string s,int l) { if(l==maxlen) { coutsendl; return; } s.push_back('-'); for(int i=0;ialphabet.size();i++) { s[l]=alphabet[i]; backtrack(s,l+1); } } int main() { maxlen=3; alphabet=op; backtrack(,0); return 0; } On Fri, Aug 5, 2011 at 12:42 PM, Kamakshii Aggarwal kamakshi...@gmail.com wrote: @gaurav:i could not understand ur sol.can u explain it again.. On Fri, Aug 5, 2011 at 12:32 PM, Gaurav Menghani gaurav.mengh...@gmail.com wrote: On Fri, Aug 5, 2011 at 12:20 PM, Kamakshii Aggarwal kamakshi...@gmail.com wrote: given a set of letters and a length N, produce all possible output.(Not permutation). For example, give the letter (p,o) and length of 3, produce the following output(in any order you want, not just my example order) ppp ppo poo pop opp opo oop ooo another example would be given (a,b) and length 2 answer: ab aa bb ba -- Regards, Kamakshi kamakshi...@gmail.com This can be done easily by backtracking void backtrack(string s, int l) { if(l == maxlen) { coutsendl; return; } s.push_back('-'); for(int i=0;ialphabet.size();i++) { s[l]=alphabet[i]; backtrack(s,l+1); } } -- Gaurav Menghani -- 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. -- Regards, Kamakshi kamakshi...@gmail.com -- 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. -- Gaurav Menghani -- 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. -- Varun Jakhoria ...it's only about 0's 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 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. -- Gaurav Menghani -- 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
Re: [algogeeks] probabilty
1/8 On Fri, Aug 5, 2011 at 4:19 PM, nethaji guru nethaji.1...@gmail.com wrote: 3 /4 -- With regards, Nethaji Guru -- 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] probabilty
yes it cant be 1/8 I was wrong. On Fri, Aug 5, 2011 at 4:23 PM, coder dumca coder.du...@gmail.com wrote: i think it should be 3/4 On Fri, Aug 5, 2011 at 4:20 PM, aditi garg aditi.garg.6...@gmail.comwrote: 1/8 On Fri, Aug 5, 2011 at 4:14 PM, coder dumca coder.du...@gmail.comwrote: A man speaks truth 3 out of 4 times. He throws a die and reports it to be a 6. What is the probability of it being a 6? 1 /2 3 /4 5 /8 1 /8 -- 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. -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- 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] probabilty
A dice is 6 B reports 6 P(A) = 1/6 P(!A) = 5/6 P(B|!A) =(1/4)*(1/5) P(B|A) = (3/4) P(A|B) = P(B|A)*P(A)/( P(B|A)*P(A) + P(B|!A)*P(!A)) =((3/4)*(1/6))/( (3/4)*(1/6) + (1/4)*(1/5)*(5/6)) = 3/4 On Fri, Aug 5, 2011 at 4:50 PM, tarang dawer tarrang1...@gmail.com wrote: 1/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.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] Reverse Bits
x = x16 | (0xx)16 this line exchanges ls 16bits with ms 16bits, i.e. 1 pair of 16bit this logic of exchanging bits is the used for 2 pairs of 8bits each, then for 4 pairs of 4bit, then for 8 pairs of 2 bit and finally 16 pairs of 1bit. On Fri, Aug 5, 2011 at 6:04 PM, rShetty rajeevr...@gmail.com wrote: This is the code to reverse the bits in an unsigned integer . Could anyone please explain the logic of this approach ? Thank You !! #define reverse(x) \ (x=x16|(0xx)16, \ x=(0xff00ff00x)8|(0x00ff00ffx)8, \ x=(0xf0f0f0f0x)4|(0x0f0f0f0fx)4, \ x=(0xx)2|(0xx)2, \ x=(0xx)1|(0xx)1) -- 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] My senior's Interview Experience at Microsoft who got selected and offered a 16lacks package
if input starts with one or more characters from the string A telephone girl then it will give SEG FAULT because it scanf will try to write to CS, else initial value junk will be printed On Fri, Aug 5, 2011 at 6:28 PM, Lakshmi Prasad prasadlakshmi...@gmail.comwrote: for some inputs its giving junk as the answer and for others its giving segmentation fault could u plese explain why -- 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/-/E1TOuF3IY2EJ. 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] nlogn, in-place, iterative mergesort?
does anyone know of any in-place, iterative mergesort algorithm with nlogN worst case complexity? It would be good if it is stable also. TIA Nitin -- 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: remove duplicate words in a string
@deepika this is a different question, your solution is great for removing duplicate characters. original question is about removing duplicate words. On Fri, Aug 5, 2011 at 7:06 PM, deepikaanand swinyanand...@gmail.comwrote: ya an array of 256 is surely a wastage of space but this was i couls think in my microsoft interview as the result should have also been i place that is i/p : AAA BBB CCC o/p:A BC//space should also be removed ::explanantion s[0] is alwayz unique therfor array[s[0]] = 1 = this char has already occured if the encountered s[i] has corresponding array[s[i]]==0 =this char has not occured yet else delete dat particular char at pos 'i' n decrement i -- 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] Circle
I think this will do. http://en.wikipedia.org/wiki/Midpoint_circle_algorithm On Fri, Aug 5, 2011 at 7:08 PM, rShetty rajeevr...@gmail.com wrote: Write a routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without making use of any floating point computations at all. -- 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] My senior's Interview Experience at Microsoft who got selected and offered a 16lacks package
its a regex. scanf will only accept characters in square brackets. On Thu, Aug 4, 2011 at 12:45 PM, muthu raj muthura...@gmail.com wrote: Can any one explain the working of %[A telephonnic girl] *Muthuraj R IV th Year , ISE PESIT , Bangalore* On Thu, Aug 4, 2011 at 12:25 PM, Nitish Garg nitishgarg1...@gmail.comwrote: The input for the above code was hello world. So the output would be hello. As the input will stop on reading 'w'. -- 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/-/oX1YmZcDR2MJ. 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] Re: Amazon Aptitude questions
find ./ -name *.java On Thu, Aug 4, 2011 at 8:17 PM, kashish jain kashish.jain.n...@gmail.comwrote: answer to shell command is grep -r *.java i wanted to ask , am i right ? On Thu, Aug 4, 2011 at 2:16 PM, Shashank Jain shashan...@gmail.comwrote: whats the priority of ^ symbol? Shashank Jain IIIrd year Computer Engineering Delhi College of Engineering On Thu, Aug 4, 2011 at 1:52 PM, Arun Vishwanathan aaron.nar...@gmail.com wrote: there are 12 black and 12 white socks p(bb)+p(ww) is what we want... p(bb)=12/24*11/23 p(ww)=12/24*11/23 so it is just 2*12/24*11/23=11/23 On Wed, Aug 3, 2011 at 9:08 PM, Prakash D cegprak...@gmail.com wrote: no.. it's really easy to find it out there are 12 black and 12 white pieces. let black =1 and white =0 the possible results are 11, 00, 10, 01 number of ways of 11 solutions= 12 * 11 = 132 number of ways of 00 solutions = 12 * 11 = 132 number of ways of 10 solutions = 12 * 12 = 144 number of ways of 01 solutions = 12 * 12 = 144 we need the prob of 10 + prob 01 == (144+144)/(132+ 132 + 144 + 144) =288/552 = 36/69 = 12/23 I think 11/23 is wrong -- 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. -- 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] Amazon Question
why not first sort the lists first? (we could if we do not want to modify original list) it will give O(nLogn) solution -Nitin On Wed, Aug 3, 2011 at 4:44 PM, veera reddy veeracool...@gmail.com wrote: sry... misunderstood the question On Wed, Aug 3, 2011 at 4:43 PM, veera reddy veeracool...@gmail.comwrote: there is o(m+n) solution . http://geeksforgeeks.org/?p=2405 in this link see method no 4 On Wed, Aug 3, 2011 at 4:41 PM, ankit sambyal ankitsamb...@gmail.comwrote: ya, I also can't think anything better than O(m*n) -- 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. -- Regards , P Veera Reddy Devagiri Senior Under Graduate Computer Science and Engineering IIIT Hyderabad Mobile no-+91-9492024783 -- Regards , P Veera Reddy Devagiri Senior Under Graduate Computer Science and Engineering IIIT Hyderabad Mobile no-+91-9492024783 -- 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] Amazon Question
EDIT: why not first sort the lists first? (we can create copy if we do not want to modify original list) it will give O(nLogn) solution -Nitin On Wed, Aug 3, 2011 at 4:59 PM, Nitin Nizhawan nitin.nizha...@gmail.comwrote: why not first sort the lists first? (we could if we do not want to modify original list) it will give O(nLogn) solution -Nitin On Wed, Aug 3, 2011 at 4:44 PM, veera reddy veeracool...@gmail.comwrote: sry... misunderstood the question On Wed, Aug 3, 2011 at 4:43 PM, veera reddy veeracool...@gmail.comwrote: there is o(m+n) solution . http://geeksforgeeks.org/?p=2405 in this link see method no 4 On Wed, Aug 3, 2011 at 4:41 PM, ankit sambyal ankitsamb...@gmail.comwrote: ya, I also can't think anything better than O(m*n) -- 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. -- Regards , P Veera Reddy Devagiri Senior Under Graduate Computer Science and Engineering IIIT Hyderabad Mobile no-+91-9492024783 -- Regards , P Veera Reddy Devagiri Senior Under Graduate Computer Science and Engineering IIIT Hyderabad Mobile no-+91-9492024783 -- 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] Complexity Help..
Running time can be found by solving this recursion. T(sz,target) = SUM {1=i=sz} T(i,target-1) T(sz,0) = c I think it is around O(sz^target) Thanks Nitin On Wed, Aug 3, 2011 at 10:40 AM, aanchal goyal goyal.aanch...@gmail.comwrote: sorry, *target=45*, not sum. sum=0 when we call the function the first time. On Wed, Aug 3, 2011 at 10:39 AM, aanchal goyal goyal.aanch...@gmail.comwrote: @ Ankit Sambyal, please explain me why is it O(n^2) taking into account what the number of times solve is called (in my example above.) On Wed, Aug 3, 2011 at 10:36 AM, aanchal goyal goyal.aanch...@gmail.comwrote: let sum=45 int arr[]={1,2,3,4,5}; /*43545 times the function solve is called*/ /*2611 ways of achieving the sum (2611 ways will be printed)*/ if, int arr[]={1,3,10,30,75}; /*2931 times the function solve is called*/ /*53 ways of achieving the sum*/ So, ho here n=5, but see how many times the solve function is called! if it was n^2, then it would have been called just 25 times On Wed, Aug 3, 2011 at 9:55 AM, ankit sambyal ankitsamb...@gmail.comwrote: @Ravinder : Its not a DP problem.. If it was, where are the sub problems reused or in other words, where is memoization ?? @Anchal : Its complexity is O(n^2). Look at the following segment in ur code : for(int i=index[n];isz;i++) { index[n+1]=i; solve(index,arr,target,cursum+arr[i],n+1,sz); } Here sz is the number of elements in the array i.e. n for complexity. There is a recursive call to solve .. I hope its clear now . -- 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. -- Regards,* Aanchal Goyal*. -- Regards,* Aanchal Goyal*. -- Regards,* Aanchal Goyal*. -- 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] sorting in O(n) time
counting sort http://en.wikipedia.org/wiki/Counting_sort Thanks NItin On Wed, Aug 3, 2011 at 10:58 AM, AMAN AGARWAL mnnit.a...@gmail.com wrote: Hi, How can we sort one unsorted int array with O(n). Unsorted : {4,2,6,1,5,5,1,2,45,444,44,45,4,1} Sorted : {1,1,1,2,2,4,4,5,5,6,44,45,45,444} Is there any sorting method which gives us O(n) time complexity??? Please tell the algo if anybody knows it. -- AMAN AGARWAL Success is not final, Failure is not fatal: It is the courage to continue that counts! -- 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.