[algogeeks] Re: find output
A better place to put these types of questions would be www.stackoverflow.com On Jul 4, 10:45 pm, amit kumar amitthecoo...@gmail.com wrote: thanx guys... On Mon, Jul 4, 2011 at 5:11 PM, mahesh.jnumc...@gmail.com mahesh.jnumc...@gmail.com wrote: In while loop, the value of i will be used as 0 as it is post decrement so the value of i will decrement after the while loop is executed. so 0!=0 will fail and the value of i will get decrement and will be printed as -1. On Mon, Jul 4, 2011 at 3:54 PM, amit the cool amitthecoo...@gmail.comwrote: main() { int i=0; while(+(+i--)!=0) i-=i++; printf(%d,i); } output sud be 1 bt it is -1; why?? -- 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.
[algogeeks] Re: array size problem
due to constant folding On Jul 4, 6:54 am, Navneet Gupta navneetn...@gmail.com wrote: If you can, refer to Constants chapter in Bruce Eckel. He he smartly explained how const are different for C C++. The e-book is free to download from net. On Mon, Jul 4, 2011 at 2:50 AM, Gene gene.ress...@gmail.com wrote: Why do bicycles have 2 wheels and tricycles 3? The designers made them that way. So you're probably asking why they were designed that way. C++ came after C. In general C++ seeks to de-emphasize use of the pre- processor because macro substitution is generally considered to make maintenance more difficult. Consequently, in C you would say #define ArraySize 100 and this will work in C++, too. But C++ gives you the addtional preferred way. On Jul 3, 4:17 pm, Deoki Nandan deok...@gmail.com wrote: WHY? In C++, you can do something like const int ArraySize = 100; int Array[ArraySize]; while in ANSI C, this would be flagged as an error. -- **With Regards Deoki Nandan Vishwakarma * * -- 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 athttp://groups.google.com/group/algogeeks?hl=en. -- --Navneet -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Google Question
1,2,43,41,5 , 6 Start at a[3] and a[5] Swap them up . Reversing it , we get 1,2,43,5,6,41 This does not work . On Jun 23, 9:05 pm, Swathi chukka.swa...@gmail.com wrote: We just need to find the start and end of the decreasing sequence then we have to reverse the elements in that decreasing sequence by swapping the elements at both the edges... On Thu, Jun 23, 2011 at 2:13 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: @piyush Sinha How can you do it in O(1) space and O(n) time dude .The inplace merging of d sorted arrays take space O(log d) space at least i think .Plus even at every step , we have to do O(log n) comparisions to find the next larger or smaller element .How can this be O(n) ??? WAiting eagerly for a reply On Jun 22, 3:24 pm, Dumanshu duman...@gmail.com wrote: @Piyush: could u plz post the link to the same? On Jun 22, 2:15 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote: This question has been discussed over here once...It was concluded that this can be solved in O(n) if we know there is a fixed range up to which the elements keep on increasing and decreasing..for example in an array of 12 elements, we know 3 elements keep on increasing monotonically, then 3 elements keep on decreasing monotonically and so on On 6/22/11, chirag ahuja sparkle.chi...@gmail.com wrote: Given an array of size n wherein elements keep on increasing monotonically upto a certain location after which they keep on decreasing monotonically, then again keep on increasing, then decreasing again and so on. Sort the array in O(n) and O(1). I didn't understand the question, any array of n elements will be like this except when first there is a decrese from index 0 to a higher index. Any ideas about how to solve it in given constraints?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926*-Hidequoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: c code help
@ankit agarwal , it is giving zero because the region the pages are allocated for it in the .rodata section (With pointer to it pushed on the stack) is zeroed out .It can even give segmentation fault in many cases and the behaviour here in operating system and compiler dependent On Jun 23, 5:14 pm, Anika Jain anika.jai...@gmail.com wrote: oki.. thanx :) On Thu, Jun 23, 2011 at 5:39 PM, Ankit Agarwal ankitgeniu...@gmail.comwrote: 1) p1[-3] is an invalid address and thereby, it is giving 0. 2) p1[3]='e' having 101 as ASCII value, thus -p1[3]=-101 as integer. On Thu, Jun 23, 2011 at 5:36 PM, Anika Jain anika.jai...@gmail.comwrote: 1) int main() { char *p1=cquestionbank; printf(%d,p1[-3]); return 0; } why is it giving 0?? 2) int main() { char *p1=cquestionbank; printf(%d,-3[p1]); return 0; } why is this giving -101?? -- 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. -- Ankit Agarwal *Be the change that you want to see in the world... :)* *- Gandhiji* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Google Question
@piyush Sinha How can you do it in O(1) space and O(n) time dude .The inplace merging of d sorted arrays take space O(log d) space at least i think .Plus even at every step , we have to do O(log n) comparisions to find the next larger or smaller element .How can this be O(n) ??? WAiting eagerly for a reply On Jun 22, 3:24 pm, Dumanshu duman...@gmail.com wrote: @Piyush: could u plz post the link to the same? On Jun 22, 2:15 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote: This question has been discussed over here once...It was concluded that this can be solved in O(n) if we know there is a fixed range up to which the elements keep on increasing and decreasing..for example in an array of 12 elements, we know 3 elements keep on increasing monotonically, then 3 elements keep on decreasing monotonically and so on On 6/22/11, chirag ahuja sparkle.chi...@gmail.com wrote: Given an array of size n wherein elements keep on increasing monotonically upto a certain location after which they keep on decreasing monotonically, then again keep on increasing, then decreasing again and so on. Sort the array in O(n) and O(1). I didn't understand the question, any array of n elements will be like this except when first there is a decrese from index 0 to a higher index. Any ideas about how to solve it in given constraints?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926*-Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: sort the array
People should not just come over here , write one word and go .If you cannot explain you're logic with an example , means you haven't even tried the problem .You just want to boast you're adroit .In place merging of two sorted is not an easy problem . . On Jun 22, 9:48 pm, ankit mehta mehta.bond...@gmail.com wrote: Yes thats what I am saying that algorithm presented by Mr. Navneet wont work. On Jun 22, 9:40 pm, Apoorve Mohan apoorvemo...@gmail.com wrote: @ankit: we need an inplace algorithm :) -- 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: BST
If nothing is allowed , as in extra space etcetera We can use morris traversal to find the inorder of the tree . On Jun 19, 3:25 am, kumar vr kumarg...@gmail.com wrote: Balance the tree and return the Root. On Sun, Jun 19, 2011 at 12:10 AM, hary rathor harry.rat...@gmail.comwrote: then you can use iterative method instead of recursion ... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Building a Binary tree with XOR
you might want to explain what you want to do with an example ! On Apr 20, 11:09 am, sunil sunil@gmail.com wrote: Hi All, Before starting any binary tree problem I will be creating such kind of binary tree and will be solving that problem accordingly. From the last few days I am trying to code to build a binary tree with Exclusive Operators. Here I am trying to build the tree in the level order way like all the elements will be placed in the queue in the order of levels so that the final binary tree will be almost complete binary tree. In general the left node will contain the left side tree adress details and right node will contain the right tree details. But the XOR Binary trees will be holding the XOR values of parent and left child in the left node and in the same way the parent and right child will be in the right part. Here I am unable to track the parent of a particular node after the level 3. Does it possible to create a XOR binary tree with the level order mechanism. If possible, could you provide me clues in resolving this problem. My files looks like as below Header file: #includeiostream #includequeue using namespace std; typedef unsigned long pointer; struct BTXNode { int data; struct BTXNode* fleft; struct BTXNode* fright; }; class BTX { struct BTXNode *root; public: BTX() { root=NULL; } struct BTXNode* getNode(int data); int insertAtLeaf(struct BTXNode* node); }; -- CPP file --- #include btf_xor.h struct BTXNode* BTX::getNode(int data) { struct BTXNode* node=new BTXNode(); node-data=data; node-fleft=NULL; node-fright=NULL; return node; } int BTX::insertAtLeaf(struct BTXNode* nd) { coutinsertAtLeaf Data is nd-dataendl; bool set_ind=true; bool right_ind=false; struct BTXNode *parent=NULL; if(!root) { root=nd; return 1; } queueBTXNode* q; q.push(root); q.push(NULL); while(!q.empty() set_ind) { struct BTXNode *temp=q.front(); q.pop(); if(temp) { couttemp-data istemp-dataendl; if(temp-fleft != parent) { struct BTXNode* left=(struct BTXNode*) ((pointer)temp-fleft^(pointer)parent); q.push(left); right_ind=true; } else { nd-fleft=(struct BTXNode*) ((pointer)temp ^ (pointer)nd-fleft); nd-fright=(struct BTXNode*) ((pointer)temp ^ (pointer)nd-fright); //temp-fleft=(struct BTXNode*) ((pointer)nd ^ (pointer)parent); temp-fleft=(struct BTXNode*) ((pointer)nd ^ (pointer)temp-fleft); right_ind=false; set_ind=false; } if(right_ind) { if(temp-fright != parent) { struct BTXNode* right=(struct BTXNode*)((pointer)temp-fright^(pointer)parent); q.push(right); right_ind=true; } else { nd-fright=(struct BTXNode*) ((pointer)temp ^ (pointer)nd-fright); nd-fleft=(struct BTXNode*) ((pointer)temp ^ (pointer)nd-fleft); //temp-fright=(struct BTXNode*) ((pointer)nd ^ (pointer)parent); temp-fright=(struct BTXNode*) ((pointer)nd ^ (pointer)temp-fright); set_ind=false; } } parent=temp; } else { if(!q.empty()) { q.push(NULL); } } } } int main() { BTX btx; btx.insertAtLeaf(btx.getNode(10) ); btx.insertAtLeaf(btx.getNode(8)); btx.insertAtLeaf(btx.getNode(12)); btx.insertAtLeaf(btx.getNode(7)); btx.insertAtLeaf(btx.getNode(9)); btx.insertAtLeaf(btx.getNode(11)); btx.insertAtLeaf(btx.getNode(13)); return 0; }
[algogeeks] Re: Reading Huge input from the terminal in least time.
use this #includecstdio #includeiostream char ipos, opos, InpFile[2000], OutFile[2000], DIP[20]; inline int input(int flag=0) { while(*ipos = 32) ++ipos;//skips white spaces if ( flag ) return (*ipos++ - '0'); / For getting Boolean Characters */ int x=0, neg = 0;char c; while( true ) { c=*ipos++; if(c == '-') neg = 1; else { if (c=32) return neg?-x:x; x=(x1)+(x3)+c-'0'; } } } inline void output(int x,int flag) { int y,dig=0; if(x0){ *opos++='-'; x=-x;} while (x||!dig) { y=x/10;DIP[dig++]=x-((y 3) + (y 1))+'0';x=y;} while (dig--) *opos++=DIP[dig]; *opos++= flag ? '\n' : ' '; } inline void InitFASTIO() { ipos = InpFile; opos = OutFile; fread_unlocked(InpFile,2000,1,stdin); } inline void FlushFASTIO() { fwrite_unlocked(OutFile,opos-OutFile,1,stdout); } On Apr 20, 8:06 am, abhijith reddy abhijith200...@gmail.com wrote: You could read input character by character using getchar_unlocked() untill you hit a space or new line or EOF. Alternatively you read the whole input at once using fread_unlocked() and then process it as per your need. On Wed, Apr 20, 2011 at 7:41 AM, shubham shubh2...@gmail.com wrote: Hello Geeks, Suppose we have a 2-d array arr[1000][1000] capable of storing 10^6 elements in it. Input is supplied one row at a time. Then what is the best possible way to read this much data in the least amount of time as scanf() or cin takes a lot of time? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: 25february
19 (I'm driving ) Ironically I read this puzzle in chacha chaudhary comics :P On Feb 26, 8:31 pm, anuja verma kcrazy...@gmail.com wrote: 19(I m d driver and I m 19) On Feb 26, 12:35 pm, Lavesh Rawat lavesh.ra...@gmail.com wrote: *Bus Driver Problem Solution* ok let's say you're driving a bus and it's empty. At the first stop two(2) people get on. At the second stop five(5) people get on and one(1) person exits. At the third stop six(6) people get on and four(4) people exit. How old is the bus driver? Update Your Answers at : Click Herehttp://dailybrainteaser.blogspot.com/2011/02/25february.html Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe it . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Antipodal points
The points must satisfy the equation (x-x1)(x-x2)+(y-y1)(y-y2)=0 Circle centered at origin x2+y2=Some radius .With N points on the circle , we find out the radius In order to find if the two points are antipodal , we check the first equation putting the two points and checking for any other point on the circle if it satisfies the equation . Test for antinodality . This will do in O(1) . Given N points and we have to find if two points are antinodal On Feb 26, 11:15 am, Mohan Mangal mohan.mangal...@gmail.com wrote: Hi Vinay, Here the condition is Point lies on same circle.. hope you got it. On Sat, Feb 26, 2011 at 10:58 AM, vinay reddy gvina...@gmail.com wrote: Hi Dave, I don't think ur logic will cover all cases like (1,1)(-3,-3), (1,1) (2,2) a line connecting these points passes through origin, i think the solution is, we need to compute the slope of the point at index i with origin and build a binary tree with theses slopes. but worst cases of this algo is N*N , if we try balancing the tree while inserting I guess it can be done in NlogN Thanks Vinay On Fri, Feb 25, 2011 at 9:20 AM, Gene gene.ress...@gmail.com wrote: Dave's solution is best if numerical error is possible. If the points are precise, you can also do it in linear time. Just hash the points on abs(y/x). -- 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, Mohan Mangal Software Engineer, Bangalore Mob- 80952-03670 -- 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: Fwd: [algogeeks] Binary Tree Amazon
Why should we start traversing towards right ? root will be the ultimate parent anyways . May be I din get your approach .Can you elaborate with an example as given by the Thread starter ? For vertical level 1 . The node is 10 and hence the sum is 10 . For vertical line 2 (level 2) , going left and right gives a wrong from the test case given . -- 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:
First question mode switch time context switch time . t1t2 Second Question P intersection Q is always regular (proof is beyond the scope of mortals :P) . fourth Question :- D , it is not supported by plain html text . We can do this only by java script or something . Embed objects -- we have embed tag refresh - we have meta tag automatically redirect -- again meta tag Display client time -- javascript or ajax (Alert(some function )) Third :- It uses DP , also in a bottom up fashion . -- 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: Binary Tree Amazon
Just a slight addition , you would also like to keep a record for the maximum range of the levels (assuming the function is called as (root , 0)) On Feb 14, 5:25 pm, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: use hash take an array verticalsum[]={0}; the function will be like this void vertcal_sum(node *root, int level){ if(root!=NULL){ verticalsum[level]+=root-data; vertcal_sum(root-left,level-1); vertcal_sum(root-left,level+1); } } On Mon, Feb 14, 2011 at 5:04 PM, bittu shashank7andr...@gmail.com wrote: Given a binary tree with no size limitation, write a program to find the sum of each vertical level and store the result in an appropriate data structure (Note: You cannot use an array as the tree can be of any size). 4 / \ 7 8 / \ / \ 10 11 / 13 12 here 4(root) , 11(leftsubtree's right child ), 12 (rightsubtree's left child) are in same vertical Line so here vertical line 1 is fro 10 vertical line 2 sum is 7 vertical line 3 sum is 4+11+12=27 (May Have Some Doubt So i Have represented the figure in correct way) vertical line 4 is 8 vertical line 5 is 13 Hope its clear to every one Thanks Regards Shashank Mani -- 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. -- With Regards, *Jalaj Jaiswal* (+919019947895) Software developer, Cisco Systems B.Tech IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: amazon c questn
You can also free the memory of q , we don't need it anymore . but , the code is just fine . On Feb 13, 5:03 pm, dinesh bansal bansal...@gmail.com wrote: On Tue, Jan 11, 2011 at 10:14 PM, snehal jain learner@gmail.com wrote: what is the wrong in the program? main() { char *p,*q; p=(char *)malloc(25); Check for p against NULL. q=(char *)malloc(25); Check for p against NULL. strcpy(p,amazon); strcpy(q,hyd); strcat(p,q); compilation error printf(%sp); Free allocated memory. } -- 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. -- Dinesh Bansal The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- 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: Majority Element
What is a majority element ? If you are refering to your previous post , then , use hashing On Feb 13, 10:12 pm, Akshata Sharma akshatasharm...@gmail.com wrote: oops... ignore the post :-/ On Feb 13, 10:07 pm, Akshata Sharma akshatasharm...@gmail.com wrote: Given an element and an array, how will you find whether the element is the majority element of the array or not in linear time? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: SPOJ problem code:MAJOR
A few problems with your code : 1)Very Unclear (sorry !):- Either use a camelCase like java or use the c++ underscores style .Paste ur code on pastebin etc. 2)Too many loops :- It is O(n) , but perhaps O(4000*n) , much worse than O(n^2) in this case. 3)The problem is based on majority element concept :- No it's not ! It's a simple hashing problem . 4)Use scanf and printf , never ever use cin and cout , they are too slow .(Same holds for java , use printwriter , never scanner etc. ) 5)AC code :-http://pastebin.com/FkBiS6S3 PS:Nice practice problem , it's been 2 months since I opened spoj (Increased my points by .6 :D):P -- 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: codechef problem
Don't answer this problem , it's from codechef February challenge ! On Feb 2, 6:11 pm, tech rascal techrascal...@gmail.com wrote: In a plane given n points (x1,y1) (x2,y2)(xn,yn), find the the maximum number of collinear points. plz tell me the best way to do that. -- 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: Minimum positive-sum subarray
@above guy with cheers and all and snehal the best way to prove wrong is by a test case , so , -1 -2 3 4 Ricky's solution will give the answer as 4 , while the answer is 7 @snehal . [quote]if indices starting at 1 bothers you then take P[i]= A[0] + A[1] + + A[i] its one and the same thing.. [\Quote] I'm really not that stupid to bother about an off-by-one error :-) Your algo rephrased :- P[i] = A[1] + A[2] + … + A[i] so , P[1]=-1 P[2]=-3 P[3]=0 P[4]=4 Q[i].Value = P[i]. Q[i].Index = i So , Q[1]=-1 , 1 Q[2]=-3 , 2 Q[3]=0 , 3 Q[4]=4 , 4 Now , as u said , let's sort it new Q={{4 , 4} ,{0 , 3} ,{-1 , 1} ,{-3 , 3}} You din mention anything after this , so I dunnoe what you plan up from here . How are we going to get the answer {3 , 4 } from here ? Now , On Feb 2, 10:06 pm, Ricky rajeevpo...@gmail.com wrote: Hi you can try the following code snippet: int array[] = {11, -12, 15, -3, 8, -9, 1, 8, 10, -2}; int length = 10; int max = 0; int current = 0; for (int i = 0; i length; i++) { current += array[i]; max = max current ? max : current; } std::coutMax is : max; Cheers!! On Feb 2, 9:04 pm, snehal jain learner@gmail.com wrote: @ above didnt get you? why is the solution wrong? and if indices starting at 1 bothers you then take P[i]= A[0] + A[1] + + A[i] its one and the same thing.. On Wed, Feb 2, 2011 at 6:02 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: This solution is wrong , never has it been said that the indices will occur from 1.i (if that is the case , you don't need to sort , just return the maximum /minimum sum obtained as a result) The indices were b/w i..j such that 1=i=j=n O(n) solution does not exist .The state space tree will have n! leaf nodes(because there is some ordering on the input data , otherwise it would have 2^n leaf nodes) .Traversing the tree will take O(log n!) steps , or O(n log n) In fact a slight modification to this , the subset sum problem id NP- complete . But with the Q[i] array , you can get the answer with simple recursion ( or bfs or state space search or dp ) . On Feb 2, 1:33 pm, snehal jain learner@gmail.com wrote: @ above its nt any homework question.. i found it a good question... aftr spending a lot of time i came up with following solution Given Input Array A form the prefix sum array P of A. i.e P[i] = A[1] + A[2] + … + A[i] Now create another array Q of pairs (Value, Index) such that Q[i].Value = P[i]. Q[i].Index = i Now sort that array Q, considering only Q[i].Value for comparison. We get a new sorted array Q’ such that Q’[i].Value Q’[i].Index Time complexity o( nlogn) and my O(n) which i posted earlier is giving incorrect result in some case..so ignore that.. so does there exist O(n) solution for it also.. i had tried a lot but could not figure out. but i think it should exist as there is for the other variation.. On Tue, Feb 1, 2011 at 8:24 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: You should not post homework problems . 1)For divide and conquer :- Read about interval trees , binary indexed trees , segments trees . Solve this using interval tree (By the time you solve a few basic problems of interval tree , you would be able to figure out a solution) the function to calculate the parent will be 1) first check if the two are +ve 2) if yes , join both of them and also iterate on the sides left by both , to see if you can include them also (You only need to see the positive elements , no negative elements ) T(n)=2T(n/2)+O(n) I gan explain in detail , please correct me if im wrong Logic :- Basically in the subproblem , we would have founded the maximum subarray in that well , subarray (short of words ) .So , if we want to ,we can only increase the solution in the next subarray (the second subproblem ) So , there will be three cases Either the subarray , the most minimum sum in one of the subproblems will be the answer The answer will be from between the gap of the indices between the solutions of the two subproblems The answer will be any combination of the two All these three can be checked in O(n) itself . 2)Using DP(I don't know how many dp (pure dp i mean) algorithms are in O(nlog n) .Never heard of any with the pure dp approach and an n log n solution ) DP(classical for maximum positive sum array ) can be done by going through two loops dp[i]= minimum positive sum for an array with index (last index =i ) p[i]= start index corresponding to this dp[i] dp[i]= minimum sum condition ( for each ij ) update p[i] accordingly
[algogeeks] Re: top search queries
@guy above juver++ The solution , i don't think can get better than this , because you need to store the querries anyway (at least for the output ) -- 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: Minimum positive-sum subarray
You should not post homework problems . 1)For divide and conquer :- Read about interval trees , binary indexed trees , segments trees . Solve this using interval tree (By the time you solve a few basic problems of interval tree , you would be able to figure out a solution) the function to calculate the parent will be 1) first check if the two are +ve 2) if yes , join both of them and also iterate on the sides left by both , to see if you can include them also (You only need to see the positive elements , no negative elements ) T(n)=2T(n/2)+O(n) I gan explain in detail , please correct me if im wrong Logic :- Basically in the subproblem , we would have founded the maximum subarray in that well , subarray (short of words ) .So , if we want to ,we can only increase the solution in the next subarray (the second subproblem ) So , there will be three cases Either the subarray , the most minimum sum in one of the subproblems will be the answer The answer will be from between the gap of the indices between the solutions of the two subproblems The answer will be any combination of the two All these three can be checked in O(n) itself . 2)Using DP(I don't know how many dp (pure dp i mean) algorithms are in O(nlog n) .Never heard of any with the pure dp approach and an n log n solution ) DP(classical for maximum positive sum array ) can be done by going through two loops dp[i]= minimum positive sum for an array with index (last index =i ) p[i]= start index corresponding to this dp[i] dp[i]= minimum sum condition ( for each ij ) update p[i] accordingly .Then return the minimum amongst dp[i] and corresponding p[i] . This is a complete search , so I don't think it will get wrong . And i don't think it could be solved in O(n log n) (at least with dp) .Because the search space tree would be of height O(log n) (with no overlapping problems ) and dp lives upon overlapping subproblems . Or may be , if someone could provide with a O( n log n) solution Regards , Sankalp Srivastava I live the way I type , fast and full of errors -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: google questions
I think , as juver++ said , you should also try reading on the internet about these kinds of problems .This can be solved with an augmentation of a trie (keeping a count variable at the leaf ( maintaining a counter for all the word frequencies accordingly )) .Just print the top ten results in the end .time complexity will be O(n , log n ) .We can improve upon this solution a lot using other forms of tries and some augmentation PS:This will take some time if we do it for n characters , but since you explicitly asked for 10 characters , so be it ! For your second question , try seraching globbing (For the masochists , download the source code for glob library and go through the code ) -- 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: Amazon Written Tes Q1
+Correction to the above post This is not possible even with a counting sort because insertion still takes O(n*n) merge sort seems to be the best for it On Jan 31, 6:23 pm, sankalp srivastava richi.sankalp1...@gmail.com wrote: @manoj the great recursion problem has the time complexity as tn=2(T(n/2))+O(1) . It is not linear . ur algo is O(nlog n) This can be possible using a counting sort (again , use Bitsets to save ur space ) -- 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: Minimum positive-sum subarray
This solution is wrong , never has it been said that the indices will occur from 1.i (if that is the case , you don't need to sort , just return the maximum /minimum sum obtained as a result) The indices were b/w i..j such that 1=i=j=n O(n) solution does not exist .The state space tree will have n! leaf nodes(because there is some ordering on the input data , otherwise it would have 2^n leaf nodes) .Traversing the tree will take O(log n!) steps , or O(n log n) In fact a slight modification to this , the subset sum problem id NP- complete . But with the Q[i] array , you can get the answer with simple recursion ( or bfs or state space search or dp ) . On Feb 2, 1:33 pm, snehal jain learner@gmail.com wrote: @ above its nt any homework question.. i found it a good question... aftr spending a lot of time i came up with following solution Given Input Array A form the prefix sum array P of A. i.e P[i] = A[1] + A[2] + … + A[i] Now create another array Q of pairs (Value, Index) such that Q[i].Value = P[i]. Q[i].Index = i Now sort that array Q, considering only Q[i].Value for comparison. We get a new sorted array Q’ such that Q’[i].Value Q’[i].Index Time complexity o( nlogn) and my O(n) which i posted earlier is giving incorrect result in some case..so ignore that.. so does there exist O(n) solution for it also.. i had tried a lot but could not figure out. but i think it should exist as there is for the other variation.. On Tue, Feb 1, 2011 at 8:24 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: You should not post homework problems . 1)For divide and conquer :- Read about interval trees , binary indexed trees , segments trees . Solve this using interval tree (By the time you solve a few basic problems of interval tree , you would be able to figure out a solution) the function to calculate the parent will be 1) first check if the two are +ve 2) if yes , join both of them and also iterate on the sides left by both , to see if you can include them also (You only need to see the positive elements , no negative elements ) T(n)=2T(n/2)+O(n) I gan explain in detail , please correct me if im wrong Logic :- Basically in the subproblem , we would have founded the maximum subarray in that well , subarray (short of words ) .So , if we want to ,we can only increase the solution in the next subarray (the second subproblem ) So , there will be three cases Either the subarray , the most minimum sum in one of the subproblems will be the answer The answer will be from between the gap of the indices between the solutions of the two subproblems The answer will be any combination of the two All these three can be checked in O(n) itself . 2)Using DP(I don't know how many dp (pure dp i mean) algorithms are in O(nlog n) .Never heard of any with the pure dp approach and an n log n solution ) DP(classical for maximum positive sum array ) can be done by going through two loops dp[i]= minimum positive sum for an array with index (last index =i ) p[i]= start index corresponding to this dp[i] dp[i]= minimum sum condition ( for each ij ) update p[i] accordingly .Then return the minimum amongst dp[i] and corresponding p[i] . This is a complete search , so I don't think it will get wrong . And i don't think it could be solved in O(n log n) (at least with dp) .Because the search space tree would be of height O(log n) (with no overlapping problems ) and dp lives upon overlapping subproblems . Or may be , if someone could provide with a O( n log n) solution Regards , Sankalp Srivastava I live the way I type , fast and full of errors -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2Bunsubscribe@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Written Tes Q1
@manoj the great recursion problem has the time complexity as tn=2(T(n/2))+O(1) . It is not linear . ur algo is O(nlog n) This can be possible using a counting sort (again , use Bitsets to save ur space ) -- 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: first larger element in unsorted array...
Another approach would be to use a counting sort method (less space efficient though ) So , for space efficiency , we can use a bitset .element insertion will take O(n) time in the set (with a space complexity of O(log n) ) so , for the above elements , the bitset will look like (the p# shows the index corresponding to the array) 0p10p2p3p4p5p6p7 Now , start from the 1st element in the bitset , and find the next non- zero element print it ..continue the loop from this element . Not very space efficient I suppose , but it is still O(n) and time is O(n) too . @abhijit reddy Ur simple dp is wrong , you should also process the left part as pointed by juver++ -- 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: Divide the array into groups
@above Many ways to do this problem One will be to find the bfs (there will be many and this will lead to a forest ) This , in turn can be done in O(e+v) , using adjancy list or matrix . Whenever , we cannot go further , start from any new uncovered node , and keep exploring recursively .Keep a boolean flag array for the elements you have already covered . Also , this looks like a union find problem .So one can also do this using disjoint set data structure . http://www.topcoder.com/tc?module=Staticd1=tutorialsd2=disjointDataStructure -- 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: Amazon Again
@wei.qui On a second thought , if the petrol pumps have many petrol pumps connected to it , we cannot find the answer your way or the method suggested by me previously . Thus , the solution becomes one to find out the Eulerian Path (constraint based of course ) -- 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: design a data structure
Another approach will be to insert the elements in order and remove the first(or the second) half in operation 2 Another approach would be to use a bitset , just mark all the elements in the specific range as 0 . We are not supposed to retrieve the elements so , keep a bit corresponding to every element (has the number , find it's position and put it there , a simple one one mapping will do) Now , just mark all top elements as false on the second go . PS:Would come up with the proof for amortized complexity soon , but can be done something like this First operation O(1) , second operation O(n) .However , we can only insert or delete , from this sequence of n items , in O(n) time in the worst case . These operations can be completed in a sequence in O(n) time . So the amortized complexity should be O(n)/n or O(1) . On Jan 30, 3:44 pm, juver++ avpostni...@gmail.com wrote: 1. Add element to the end of the array. 2. Find median of the array, and partion the array into two sets, the second one (where element = median) is removed. At each operation 2, array's size decreasing by factor 0.5. -- 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: Frequently one of the Top Question Asked in Amazon
Spiral order .. means zigzag order for example 1 2 3 4 5 6 7 Then , you need to print it in the order 1-2-3-7-6-5-4 Two of my friends were asked this questions in the interview , so I will list both of the approaches . 1)Use 1 stack and 1 queue . push the elements of one level in stack 1 and the other in queue2 print both the stack and queue recursively. algo :- printZigZag(node * node , int level) { if(node==NULL) return ; if(level==0) { level=1; stack1.push(node-data); printZigZag(node-left , level); printZigZag(node-right , level); } else { level=0; stack2.push(node-data); printZigZag(node-left , level) printZigZag(node-right , level) } } After this recursion ends , the two stacks will have the contents as (1) (2) 4 2 5 3 6 7 1 Another approach would be to use two stacks . google it up . and like this , now just print it recursively On Jan 29, 10:17 pm, saurabh gupta sgup...@gmail.com wrote: what do you mean by spiral order ? On Sat, Jan 29, 2011 at 8:25 PM, bittu shashank7andr...@gmail.com wrote: Convert BT in to DLL such that DLL represents the Sprial order traversal of BT. Inplace its Written Test Question They wants Exact Working Code...Not Approach..Be Clear..Try to provide best solutions Thanks Regards Shashank The best way to escape from a problem is to solve it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2Bunsubscribe@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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: design a data structure
Also , there is a pretty nice theorem on the fact that , if an array's size is increased/decreased by a constant size (like in STL vector class), the sequence of these doubling operations always take place O(1) time . On Jan 30, 3:44 pm, juver++ avpostni...@gmail.com wrote: 1. Add element to the end of the array. 2. Find median of the array, and partion the array into two sets, the second one (where element = median) is removed. At each operation 2, array's size decreasing by factor 0.5. -- 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: Divide the array into groups
why have you divided it into three . I mean it can be divided into many groups of consecutive . Please write the statement properly ! On Jan 30, 11:13 am, snehal jain learner@gmail.com wrote: @nishanth divide into groups ( not necessarily 2) in as many group as possible.. such that elements in each group is consecutive another example to clearify A= { 9,7, 13, 11,6,12,8,10,3, 4, 2, 16,14,17,13,15) ans 9,7,13,11,6,12,8,10 3,4,2 16,14,17,13,15 On Sun, Jan 30, 2011 at 11:32 AM, nishaanth nishaant...@gmail.com wrote: @snehal..i guess you are missing something in the question...divide it into 2 groups such that (there should be some other condition or criterion). On Sun, Jan 30, 2011 at 11:29 AM, snehal jain learner@gmail.comwrote: my approach sort in nlogn and then while traversing the array put the elements in a group till they are consecutive . when a[i+1]!=a[i]+1 then put a[i+1] in different group.. now we need to rearrange elements in the group so that they are according to the given array.. but that will make it O(n^2) .. anyone with better ideas? On Fri, Jan 21, 2011 at 1:20 PM, snehal jain learner@gmail.comwrote: Divide a list of numbers into groups of consecutive numbers but their original order should be preserved. Example: 8,2,4,7,1,0,3,6 Two groups: 2,4,1,0,3 8,7,6 Better than O(n^2) is expected. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2Bunsubscribe@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.comalgogeeks%2Bunsubscribe@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2Bunsubscribe@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Google Question
Suppose I press As only throughout . We will have the number of As as A*(number of keystrokes) .This is the least we can get provided we play stupidly enough . On Jan 29, 9:16 pm, Saikat Debnath saikat@gmail.com wrote: @ Sankalp : plz explain this line of yours : No. of As=A*(total number of keystrokes) , gives us a bound . We should have a lower bound as this , we can always get this much As On Jan 29, 5:32 pm, sankalp srivastava richi.sankalp1...@gmail.com wrote: We can do it Using a binary search approach (The cost function is monotonic over here , so we can use binary search) No. of As=A*(total number of keystrokes) , gives us a bound . We should have a lower bound as this , we can always get this much As Take the initial value as high and low as possible say left=1 and right=10^9 mid=left+right/2; if(can_get(this much As)) then , left=mid+1; else if(cannot get this much As) then , right=mid Continue this search until leftright .. This binary search gives the maximum value which you can get using the given combinations -- 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: Amazon Again
[quote]We have a car and we need to find a petrol pump which can provide so much of petrol that we can take a full of the circle.[/quote] So , we just need to find a petrol pump which takes you just a full circle , not anything ahead , not anything behind . 1)Sort the petrol he can get from maximum stations .If the total distance is not given , calculate this while sorting . Binary search over this array for the required distance . complexity :-O(nlogn+k) 2)Hash it !! keep a hash for all the distance in some boolean array .now find out the one which can get you the full circle , O(n) complexity . Not space efficient . 3)Using dynamic programming . dp[i][j] :-The distance we still need to cover (j) .while , we are on the started at the ith station . dp[i][0]:- answer , we need to look at the all the dp pairs for the answer . dp[i][j]= min(dp[i+next[i][j-d[i][next[i]]]) Basically a BFS . O(n^2) . worst case . -- 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: zig zag
No , actually it's not ... it's O(n^2) , I misunderstood the subsequence thing , it could be discontinuous .. we , then need to find the maximum of dp[l] ... the second term makes sure that the sign of the two quantities is alternating i.e. positive or negative ! On Jan 29, 11:06 am, nishaanth nishaant...@gmail.com wrote: @above...can you please enlighten me about the second term in the dp expression And are you sure its O(n) ? On Fri, Jan 28, 2011 at 7:08 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: This can be done in O(n) very easily , similar to Longest increasing subsequence Solution :- dp[l]= maximum length of the zigzag sequence upto the length l //At any position , the particular number in the array can either extend the zigzag sequence containing the last element or it can start one of it's own . So the recurrance becomes dp[i]= max(dp[j]) ,and diff[A[p[j]]]^(A[i]-A[p[j]]31)!=0 , ji find out the maximum in this array , it will get you the answer . PS:- You can also check out the Topcoder tutorials . On Jan 27, 7:41 pm, bittu shashank7andr...@gmail.com wrote: well I found it as it Can be Done in O(n). but with additional space O(n) here program is written in Java public class ZigZag { public int longestZigZag(int[] sequence) { if (sequence.length==1) return 1; if (sequence.length==2) return 2; int[] diff = new int[sequence.length-1]; for (int i=1;isequence.length;i++) { diff[i-1]=sequence[i]-sequence[i-1]; } //90% Program is done here it self. by looking at the sign if alternative number in auxiliary array we can count longest zigzag array int sign=sign(diff[0]); int count=0; if (sign!=0) count=1; for (int i=1;idiff.length;i++) { int nextsign=sign(diff[i]); if (sign*nextsign==-1){ sign=nextsign; count++; } } return count+1; } public int sign(int a) { if (a==0) return 0; return a/Math.abs(a); } public static void main(String[] args) { ZigZag z = new ZigZag(); System.out.println(z.longestZigZag(new int[] { 1, 7, 4, 9, 2, 5 })); System.out.println(z.longestZigZag(new int[] { 1, 17, 5, 10, 13, 15, 10, 5, 16, 8 })); } } Try for Inplace Thanks Regards Shashank Mani The best way to escape from a problem is to solve it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2Bunsubscribe@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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: Good Maths Question
Yuo might wanna check out The latest codeforces beta round problem C . On Jan 28, 8:34 pm, nishaanth nishaant...@gmail.com wrote: @All... According to the constraints(SPOJ problem) wont this dp solution time out ? On Tue, Jan 25, 2011 at 12:23 AM, sankalp srivastava richi.sankalp1...@gmail.com wrote: Correct me if I'm wrong dp[i][j]=how many numbers of length i with the last digit j(int base 10) dp[0][j]=0 dp[i][0]=dp[i-1][0] , last digit can't be zero otherwise the number has i-1 digits , not j; now the recursion to pass from one state to the next dp[i][j]=dp[i-1][k]+1(for each value of k such that k is less than j , from 0 to k) That is to say , the number of numbers with length i and last digit j , will be equal to the number of numbers with the last digit k , for each k less than j .One is added because , we must not have included the 0 in the last case , but we will include the zero case here . this one corresponds to zero case . Finally , the answer will be dp[n][j] , 1=j=9 , sum up all these and u have the answer For example for 2 digits dp[1][1-9]=1 , as nothing preceeds them and as said in the problem , one digit numbers are always increasing/decreasing . next dp[2][1]=dp[1][1](As only 1 is less than , equal to 1 , the last digit in this state) dp[2][2]=dp[1][1]+dp[1][2] =2( 1,2 and 2,2) Continuing this way , we will get the answer , may be 50 , though i din code it . similarly , for 3 digits Correct me if not! On Jan 25, 12:06 am, juver++ avpostni...@gmail.com wrote: dp[i][j] - how many numbers of length i and with the last digit j. Apply the scheme to increasing and decreasing number, then find ratio. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2Bunsubscribe@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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: Prime Numbers
Okay I got it myself @OP This can be done in O(n*k*logn) where k is of order 10^3 at the very max , when u need a prime like 1 trillion On Jan 28, 6:44 pm, sankalp srivastava richi.sankalp1...@gmail.com wrote: Correct me if I'm wrong , but according to you , will this be the approach ? boolean array[10]; int primes[100]; void seive() { int index=0; for(int i=2;i*i10;i++) { if(isprime[i]) { primes[index++]=i; for(int j=i*2;j100;j+=i) { isprimes[i]= false; } } } int kindex=index; } /* But now , how should I find out the 1 millionth prime number ? It requires another seive , i know , but it requires still bigger range */ Can you give me a pseudocode ? */ On Jan 26, 8:20 pm, juver++ avpostni...@gmail.com wrote: @above One million is 10^6. Problem wants 1 million of prime numbers. Not the prime numbers in range 1..1000. So, you should use two sieves. -- 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: Amazon Again
I'm sure you have misstated the problem statement just find out the total path length and return the first petrol pump which gives you the required milage go greedy On Jan 28, 5:09 pm, bittu shashank7andr...@gmail.com wrote: There are N petrol pumps along a circular path. Every petrol pump gives some amount of fixed petrol. Need not to be unique and in no particular order means it is random. We have a car and we need to find a petrol pump which can provide so much of petrol that we can take a full of the circle. Mileage of car is fixed. Distance between adjacent petrol pumps are given. Thanks Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Google Question
We can do it Using a binary search approach (The cost function is monotonic over here , so we can use binary search) No. of As=A*(total number of keystrokes) , gives us a bound . We should have a lower bound as this , we can always get this much As Take the initial value as high and low as possible say left=1 and right=10^9 mid=left+right/2; if(can_get(this much As)) then , left=mid+1; else if(cannot get this much As) then , right=mid Continue this search until leftright .. This binary search gives the maximum value which you can get using the given combinations -- 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: Prime Numbers
Correct me if I'm wrong , but according to you , will this be the approach ? boolean array[10]; int primes[100]; void seive() { int index=0; for(int i=2;i*i10;i++) { if(isprime[i]) { primes[index++]=i; for(int j=i*2;j100;j+=i) { isprimes[i]= false; } } } int kindex=index; } /* But now , how should I find out the 1 millionth prime number ? It requires another seive , i know , but it requires still bigger range */ Can you give me a pseudocode ? */ On Jan 26, 8:20 pm, juver++ avpostni...@gmail.com wrote: @above One million is 10^6. Problem wants 1 million of prime numbers. Not the prime numbers in range 1..1000. So, you should use two sieves. -- 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: and or tree
I am not sure you mentioned the problem statement correctly , anyways here goes my solution . recurse(int valuerequired , node * n , int value_now , int steps) { if(node==NULL) return 0; else if(valuerequired== value_now) return steps; //we need to see the minimum number of gates to be flipped in order to achieve the desired answer . We can flip this gate , the gate , the gate left to it , and the gate right to it . // thus the answer is else return min(recurse(valuerequired , node-left , value_now , steps+1) , recurse(valuerequired , node-right , value_now , steps+1)) } /* I did not quite understand the question though , can you provide with an example ? */ -- 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: Amazon Question
I don't seem to understand ur solution . [quote] For every none leaf node , go to the last node in it's left subtree and mark the right child of that node as x [\quote]. How are we going to refer to the right child now ??We have removed it's reference now !! It is to be repeated for every node except the non leaf nodes . This will take O(n*n) time in worst case , say a leftist tree with only left pointers . root makes n-1 traversals , root's left subtree's root makes n-2 , and so on. Go to the largest node in the left subtree .This means go to the left subtree and keep on going to the right until it becomes null , in which case , you make y-right as x . This means effectively , that y is the predecessor of x , in the tree . Considering a very good code , it may take O(1) space , but you will still need additional pointers. Take the case below . 1 2 3 1 1.5 2.5 4 for node 2 , you will go to 1 , which is the successor of 2 , you make 2-right=1 but what about node 1.5 ??? same is the case with node 3 ... 3-right=2.5 . How will we refer to 4 now ?? Now using inorder traversal with a count , I will start at 1-left , 2- left = 1 , then 2 ... then 2-right = 1 again . then 1 , and then 1- right=3 ...clearly , this will not give us a solution . A reverse inorder looks just fine to me . On Jan 26, 3:14 pm, Ritu Garg ritugarg.c...@gmail.com wrote: @Algoose I said ..*.For every node x,go to the last node in its left subtree and mark the right child of that node as x.* it is to be repeated for all nodes except leaf nodes. to apply this approach ,you need to go down the tree.No parent pointers required. for every node say x whose left sub tree is not null ,go to the largest node in left sub-tree say y. Set y-right = x y is the last node to be processed in left sub-tree of x hence x is successor of y. On Wed, Jan 26, 2011 at 3:27 PM, Algoose chase harishp...@gmail.com wrote: @ritu how would you find a successor without extra space if you dont have a parent pointer ? for Instance from the right most node of left subtree to the parent of left subtree(root) ? @Juver++ Internal stack does count as extra space !! On Wed, Jan 26, 2011 at 3:02 PM, ritu ritugarg.c...@gmail.com wrote: No,no extra space is needed. Right children which are NULL pointers are replaced with pointer to successor. On Jan 26, 1:18 pm, nphard nphard nphard.nph...@gmail.com wrote: If you convert the given binary tree into right threaded binary tree, won't you be using extra space while doing so? Either the given tree should already be right-threaded (or with parent pointers at each node) or internal stack should be allowed for recursion but no extra space usage apart from that. On Wed, Jan 26, 2011 at 3:04 AM, ritu ritugarg.c...@gmail.com wrote: it can be done in O(n) time using right threaded binary tree. 1.Convert the tree to right threaded tree. right threaded tree means every node points to its successor in tree.if right child is not NULL,then it already contains a pointer to its successor Else it needs to filled up as following a. For every node x,go to the last node in its left subtree and mark the right child of that node as x. It Can be done in O(n) time if tree is a balanced tree. 2. Now,Traverse the tree with Inorder Traversal without using additional space(as successor of any node is available O(1) time) and keep track of 5th largest element. Regards, Ritu On Jan 26, 8:38 am, nphard nphard nphard.nph...@gmail.com wrote: Theoretically, the internal stack used by recursive functions must be considered for space complexity. On Mon, Jan 24, 2011 at 5:40 AM, juver++ avpostni...@gmail.com wrote: internal stack != extra space -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2Bunsubscribe@googlegroups .com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252Bunsubscribe@googleg roups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252Bunsubscribe@googleg roups.com algogeeks%252bunsubscr...@googlegroups.comalgogeeks%25252Bunsubscribe@goo glegroups.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.comalgogeeks%2Bunsubscribe@googlegroups .com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252Bunsubscribe@googleg roups.com .
[algogeeks] Re: 2 d matrix
@above person ur solution is O(n^3) in worst case !let's say the row[] and col[] arrays formed are col[]=123 124 125 126 row[]=127 , 128, 129,126 every element of row[] traverses through n elements of the array col[] and and makes O(n) comparisons in the worst case . Thus , each traversal requires O(n^2) time , and there can be O(n^3) traversals , so , time taken will be O(n^3). However sorting one of these arrays ,makes the time complexity as O(n^2log n) On Jan 26, 3:03 pm, bittu shashank7andr...@gmail.com wrote: As Navies it can be done in O(n^2) Make numbers by using every elements in the row in array row[]. Similarly convert column elements into numbers and put them in array col[]. Now compare both the arrays where the number matches print the index of both row[] and col[] array... eg:- 2, 3, 4 3, 4, 5 6, 5, 1 col[] contains 236, 345, and 451 and row[] contains 234, 345, and 651. On Comparison both has 345 as common total with index (1,1) and is the desired answer. use 2d matrix..makes it easy Time Complexity is at Most O(n^2) Thanks Regards Shashank Mani Best Way to Escape From the Problem is to Solve It -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: find a line
@dave , There is a proof for it . Let's say there is a point x0 , y0 .. and I claim that between any two points ... x1,y1 and x2,y2 assuming they are non-collinear having a line b/w them a line of some slope passes somewhere b/w them .This collinearity does not affect our result . Let's say a point x',y' divides this line into ratio m:n , this is the point where this line is intersected by the line from x0 , y0 .. as x1 ,y1 and x2,y2 are non-collinear , this point will always exist . The slope of this line can be determined from the points x0,y0 and x',y' , which is always real .hope this makes sense to u !! On Jan 26, 7:11 am, Dave dave_and_da...@juno.com wrote: @Sankalp: So what is your code? And what is the equation of the line? As I said, you can't always use a line through the origin. Dave On Jan 25, 5:49 am, sankalp srivastava richi.sankalp1...@gmail.com wrote: @dave In this case , I could just shift my origin to the lowermost point :) On Jan 25, 10:14 am, Dave dave_and_da...@juno.com wrote: @Sankalp: I wanted a point far enough outside the region that a line from any point in the region could not contain any other point in the region. There are several implications: 1) if the point is to the left of the region, it can't have an integer y coordinate between 0 and B. That is where the 0.5 comes from. Second, it seemed reasonable, but not necessary, to put Y near the middle of the range [0, B]. Then I just solved for an X that guaranteed that the slope of the line from any point in the region to the point (X, Y) had slope m satisfying -1/ A m 1/A. Then a line through any point (x1,y) could not intersect any point (x2,y-1) or (x3,y+1) within the region. Regarding your algorithm: What does it do with A = B = 5 and points {(1,1), (2,2), (3,3), (4,4), (1,4)}. This example shows that you can't always use a line through (0,0). Dave On Jan 24, 10:15 pm, sankalp srivastava richi.sankalp1...@gmail.com wrote: @ Dave How did you come up with this solution? Also Y=floor(B)/2+.5 , X=-A*(B-Y) or X=-AB +AY or Y=X/A+B . this is the equation of a line with slope 1/A and an intercept of B on Y axis .I don't quite get this.!!Please elaborate . Meanwhile , this is my approach . The slope of the line wil be between the maximum's of the two points i.e in the case of (10,0)..(10,10)...It will be between 0 and 90 degrees as all the points lie between them . Now we can just binary search over this slope checking for the slope values . The slope and set cardinality is also a monotonic function , so I guess binary search approach will work , but the time taken will be nlog n . Please correct me if I'm wrong . #includeiostream struct point { int x ; int y ;}; using namespace std ; // the given points point p[100]; int main() { int n; cinn;//number of points for(int i=0;in;i++) { cinp[i].xp[i].y; } int high=90; int low=0; int mid; //the line is supposed to start from 0,0 while(low=high) { mid=(high+low)/2; if(haspoints(mid)0) //upper has less points than below low=mid+1; else if(haspoints(mid)0) //lower has more points than upper high=mid-1; else {//we found our answer coutmidendl; return 0; } } return 0; } On Jan 24, 9:30 am, Dave dave_and_da...@juno.com wrote: Generalizing the problem, let there be n points (x_i, y_i), where x_i and y_i are integers with 1 = x_i = A and 1 = y_i = B. A line separating the points into two sets of equal cardinality can be found as follows: Let Y = floor(B/2) + 0.5, and let X = -A * (B - Y). Find the slopes of the lines from the point (X, Y) to each (x_i, y_i). The point (X, Y) is constructed so that each of these slopes will be distinct. Find the median M of these slopes. Then the line y = M(x - X) + Y will separate the points as desired. It will pass through exactly one of the points if n is odd, and will miss all of the points if n is even. This is O(n) in time and O(n) in space, where n is the number of points. Dave On Jan 21, 11:45 pm, Divya Jain sweetdivya@gmail.com wrote: assume the region to be (0,0) , (10,0), (0,10), (10,10) On 22 January 2011 08:33, Dave dave_and_da...@juno.com wrote: @Divya: The coordinates of the points are between 0 and 1 and are integers. That can't be right. Dave On Jan 21, 1:46 pm, divya
[algogeeks] Re: Prime Numbers
Use a seive . it's complexity is O(nlog n) 1 million is 1*10^7 , this will run within time limit ... assuming u optimize ur code enough !! On Jan 26, 5:48 pm, juver++ avpostni...@gmail.com wrote: Generate primes numbers for the range 1..10^7 using sieve. Than apply sieve bigger range using these prime numbers. -- 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: Good Maths Question
Correct me if I'm wrong dp[i][j]=how many numbers of length i with the last digit j(int base 10) dp[0][j]=0 dp[i][0]=dp[i-1][0] , last digit can't be zero otherwise the number has i-1 digits , not j; now the recursion to pass from one state to the next dp[i][j]=dp[i-1][k]+1(for each value of k such that k is less than j , from 0 to k) That is to say , the number of numbers with length i and last digit j , will be equal to the number of numbers with the last digit k , for each k less than j .One is added because , we must not have included the 0 in the last case , but we will include the zero case here . this one corresponds to zero case . Finally , the answer will be dp[n][j] , 1=j=9 , sum up all these and u have the answer For example for 2 digits dp[1][1-9]=1 , as nothing preceeds them and as said in the problem , one digit numbers are always increasing/decreasing . next dp[2][1]=dp[1][1](As only 1 is less than , equal to 1 , the last digit in this state) dp[2][2]=dp[1][1]+dp[1][2] =2( 1,2 and 2,2) Continuing this way , we will get the answer , may be 50 , though i din code it . similarly , for 3 digits Correct me if not! On Jan 25, 12:06 am, juver++ avpostni...@gmail.com wrote: dp[i][j] - how many numbers of length i and with the last digit j. Apply the scheme to increasing and decreasing number, then find ratio. -- 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: find a line
@dave In this case , I could just shift my origin to the lowermost point :) On Jan 25, 10:14 am, Dave dave_and_da...@juno.com wrote: @Sankalp: I wanted a point far enough outside the region that a line from any point in the region could not contain any other point in the region. There are several implications: 1) if the point is to the left of the region, it can't have an integer y coordinate between 0 and B. That is where the 0.5 comes from. Second, it seemed reasonable, but not necessary, to put Y near the middle of the range [0, B]. Then I just solved for an X that guaranteed that the slope of the line from any point in the region to the point (X, Y) had slope m satisfying -1/ A m 1/A. Then a line through any point (x1,y) could not intersect any point (x2,y-1) or (x3,y+1) within the region. Regarding your algorithm: What does it do with A = B = 5 and points {(1,1), (2,2), (3,3), (4,4), (1,4)}. This example shows that you can't always use a line through (0,0). Dave On Jan 24, 10:15 pm, sankalp srivastava richi.sankalp1...@gmail.com wrote: @ Dave How did you come up with this solution? Also Y=floor(B)/2+.5 , X=-A*(B-Y) or X=-AB +AY or Y=X/A+B . this is the equation of a line with slope 1/A and an intercept of B on Y axis .I don't quite get this.!!Please elaborate . Meanwhile , this is my approach . The slope of the line wil be between the maximum's of the two points i.e in the case of (10,0)..(10,10)...It will be between 0 and 90 degrees as all the points lie between them . Now we can just binary search over this slope checking for the slope values . The slope and set cardinality is also a monotonic function , so I guess binary search approach will work , but the time taken will be nlog n . Please correct me if I'm wrong . #includeiostream struct point { int x ; int y ;}; using namespace std ; // the given points point p[100]; int main() { int n; cinn;//number of points for(int i=0;in;i++) { cinp[i].xp[i].y; } int high=90; int low=0; int mid; //the line is supposed to start from 0,0 while(low=high) { mid=(high+low)/2; if(haspoints(mid)0) //upper has less points than below low=mid+1; else if(haspoints(mid)0) //lower has more points than upper high=mid-1; else {//we found our answer coutmidendl; return 0; } } return 0; } On Jan 24, 9:30 am, Dave dave_and_da...@juno.com wrote: Generalizing the problem, let there be n points (x_i, y_i), where x_i and y_i are integers with 1 = x_i = A and 1 = y_i = B. A line separating the points into two sets of equal cardinality can be found as follows: Let Y = floor(B/2) + 0.5, and let X = -A * (B - Y). Find the slopes of the lines from the point (X, Y) to each (x_i, y_i). The point (X, Y) is constructed so that each of these slopes will be distinct. Find the median M of these slopes. Then the line y = M(x - X) + Y will separate the points as desired. It will pass through exactly one of the points if n is odd, and will miss all of the points if n is even. This is O(n) in time and O(n) in space, where n is the number of points. Dave On Jan 21, 11:45 pm, Divya Jain sweetdivya@gmail.com wrote: assume the region to be (0,0) , (10,0), (0,10), (10,10) On 22 January 2011 08:33, Dave dave_and_da...@juno.com wrote: @Divya: The coordinates of the points are between 0 and 1 and are integers. That can't be right. Dave On Jan 21, 1:46 pm, divya sweetdivya@gmail.com wrote: Within a 2D space, there is a batch of points(no duplicate) in the region (0,0),(0,1),(1,0),(1,1), try to find a line which can divide the region to 2 parts with half points in each .the input will be an array of points and the length of the array. struct point{ int x; int y;}; input : struct point * points, int length -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2Bunsubscribe@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.-Hidequotedtext - - Show quoted text -- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks
[algogeeks] Re: find a line
@ Dave How did you come up with this solution? Also Y=floor(B)/2+.5 , X=-A*(B-Y) or X=-AB +AY or Y=X/A+B . this is the equation of a line with slope 1/A and an intercept of B on Y axis .I don't quite get this.!!Please elaborate . Meanwhile , this is my approach . The slope of the line wil be between the maximum's of the two points i.e in the case of (10,0)..(10,10)...It will be between 0 and 90 degrees as all the points lie between them . Now we can just binary search over this slope checking for the slope values . The slope and set cardinality is also a monotonic function , so I guess binary search approach will work , but the time taken will be nlog n . Please correct me if I'm wrong . #includeiostream struct point { int x ; int y ; }; using namespace std ; // the given points point p[100]; int main() { int n; cinn;//number of points for(int i=0;in;i++) { cinp[i].xp[i].y; } int high=90; int low=0; int mid; //the line is supposed to start from 0,0 while(low=high) { mid=(high+low)/2; if(haspoints(mid)0) //upper has less points than below low=mid+1; else if(haspoints(mid)0) //lower has more points than upper high=mid-1; else {//we found our answer coutmidendl; return 0; } } return 0; } On Jan 24, 9:30 am, Dave dave_and_da...@juno.com wrote: Generalizing the problem, let there be n points (x_i, y_i), where x_i and y_i are integers with 1 = x_i = A and 1 = y_i = B. A line separating the points into two sets of equal cardinality can be found as follows: Let Y = floor(B/2) + 0.5, and let X = -A * (B - Y). Find the slopes of the lines from the point (X, Y) to each (x_i, y_i). The point (X, Y) is constructed so that each of these slopes will be distinct. Find the median M of these slopes. Then the line y = M(x - X) + Y will separate the points as desired. It will pass through exactly one of the points if n is odd, and will miss all of the points if n is even. This is O(n) in time and O(n) in space, where n is the number of points. Dave On Jan 21, 11:45 pm, Divya Jain sweetdivya@gmail.com wrote: assume the region to be (0,0) , (10,0), (0,10), (10,10) On 22 January 2011 08:33, Dave dave_and_da...@juno.com wrote: @Divya: The coordinates of the points are between 0 and 1 and are integers. That can't be right. Dave On Jan 21, 1:46 pm, divya sweetdivya@gmail.com wrote: Within a 2D space, there is a batch of points(no duplicate) in the region (0,0),(0,1),(1,0),(1,1), try to find a line which can divide the region to 2 parts with half points in each .the input will be an array of points and the length of the array. struct point{ int x; int y;}; input : struct point * points, int length -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2Bunsubscribe@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: find a way
@ above In that case , it will be a simple dynamic programming based recursion assuming the total distance one has to cover is n ; d[i][j]=minimum number of fuel stations to stop at in order to cross i stations and with j miles still to go . dp[n][0]= minimum number of fuel stations to stop at in order cross n stations and with 0 miles still to go (Assuming the nth stop coincides with the destination B .In case it does not , we can answer something like dp[n][p] , where p is the distance to go from nth stop to A) The recursion dp[i][k]= min(dp[i+1][k- distance b/w the ith and (i+1)th fuel station] , dp[i+1][k- distance +lk]+1)(lk= distance we can cover on this stop) base case dp[0][j]=0;(for each j )// we have to cover no more stations therefore On Jan 22, 9:40 pm, Divya Jain sweetdivya@gmail.com wrote: if u can take only a certain amount of fuel from a particaular station ie station xi can provide li amoutn of fuel.. then wat? On 22 January 2011 13:46, Terence technic@gmail.com wrote: Greedy-Approach. Refueling only when you have to. On 2011-1-22 15:59, snehal jain wrote: Suppose you want to travel from city A to city B by car, following a fixed route. Your car can travel m miles on a full tank of gas, and you have a map of the n gas stations on the route between A and B that gives the number of miles between each station. Design an algorithm to find a way to get from A to B without running out of gas that minimizes the total number of refueling stops, in O(n) time. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2Bunsubscribe@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] Extracting random element from a bitset
How will one go about extracting a random number from a bitset ? let's say i have a bitset 1001101000100010001 where 1 denote what numbers are currently present in the set How can one extract these ones in a random manner .Generating a random number modulo size of the bitset won't work as it can land upon a zero value as well and this , in worst case can take O(size of bitset * genarating pseudo random number ) time which is very costly . Anybody knows how to do this ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] stack
@anurag I meant the sorting without using any auxiliary data structure .Also we have to put the element in the tree and carry out a traversal for every element we insert in the tree .This takes O(n*logn) time , If one can sort the elements using a stack in O(n) time , we better sort with this method , say Stack sort Moral:-No (comparison based )sorting method exists for which time complexity is less than O(n*log n) also , without using any auxialliary data structure , we cannot create all the permutations of the stack Refer Donald knuth's TAOCP for more details On Mon, Jun 14, 2010 at 9:18 AM, Anurag Sharma anuragvic...@gmail.comwrote: Why not just pop all elements from stack ( O(n) ) and insert it in a self balancing Binary Search Tree (like RB Tree) (O(log(n) ) and then do and inorder traversal ( O(n) )and push elements in stack again. Time = O(nlog(n) + n) Space=O(n) (for storing the tree) Anurag Sharma On Sun, Jun 13, 2010 at 9:25 PM, Jitendra Kushwaha jitendra.th...@gmail.com wrote: Stack can be sorted in O(n^2). @sankalp: Stack can always be sorted. Why do you think it cant be in some cases ? One can think like insertion sort algo : 1. for i in (1,n) 2. Pop up the top n-1 element and keep nth element in global variable say hold 3. while pushing get the position for hold and push it there for loop will take O(n) and step 2 will take take O(n) time. So overall O(n^2) complexity Program can be done with recursion using a variable (hence O(1) space). But it will use system stack :) Any comments OR better solution is welcomed?? -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] nibbles
this can be done using the same code as of Sharad above , the only difference being the mask bits , we mask four bits of a nibble by the anding with 0001 , 0010 , 0101 and 1000 .. now , we feed these into the given number .I mean all the bits as below .. Suppose we have a nibble as 1100 and we want it to be 0011 , so after masking , we have the four bits as 1000 , 0100 , and respectively .We feed the given bits in a reverse order into a nibble (or a character for that matter ) in a reverse order . So first bit(1000) is shifted right 3 times and added to result , second shifted 1 times and added , third shifted 1 time but to the left and fourth 3 times to the left . we add all of the to have the answer . On Sun, Jun 13, 2010 at 1:56 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: can any one explain it using an example... let say my nibble is 0100... i have to print 0010... in one go using bitwise operators... please explain through example @ sharad ... your code is to swap two nibbles in a character On Sun, Jun 13, 2010 at 1:39 PM, jaladhi dave jaladhi.k.d...@gmail.comwrote: Write a c-macro to use assembly swap opcode. On Sat, Jun 12, 2010 at 9:35 PM, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: write an algorithm to reverse a nibble in one pass...using bitwise operators -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] stack
it's not always possible to sort a stack in all the cases , consider the stack 2143 and one tries to sort it feeding the elements in order , we have now whatever popping technique we use , we cannot have a 1234 kind of stack in order .The maximum number of permutations we can have with a stack is 2nCn -2nCn-1 which does not necessarily include the permutated group . In general , we can pop the elements in a decreasing order in the same order as they are entered . Try sortin the stack with an input of 4132 .now possible On Sun, Jun 13, 2010 at 1:57 PM, jaladhi dave jaladhi.k.d...@gmail.comwrote: what do you mean by sorting elements in stack ? A stack is a data structure in which the relative position of elements depend on their order of insertion. If we sort elements in stack, how does it retain the property of a stack ? If we really want that property, we will have O(n) rather than O(1) insert and maintain two pointers. Stack next and sorted next. On Sun, Jun 13, 2010 at 1:05 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: how to sort elements of stack using constant space -- With Regards, +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] c array
don't ever use a TC compiler , the most obsolete and mad compiler of all . Every compiler tries to fix the bug in ur code by some way or the other using some .Even gcc has a lot of bugs , in the sense it will return an exit status even if returning a void , but this is on ubuntu and haven't tries mingW yet . Any On Sun, Jun 13, 2010 at 1:47 PM, divya jain sweetdivya@gmail.comwrote: i use tc On 13 June 2010 13:11, ram karthik.gin...@gmail.com wrote: @rohit bro http://www.mingw.org/ *MinGW*, a contraction of Minimalist GNU for Windows, is a port of the GNU Compiler Collection (GCC), and GNU Binutils, for use in the development of native Microsoft Windows applications. *From:* algogeeks@googlegroups.com [mailto:algoge...@googlegroups.com] *On Behalf Of *Rohit Saraf *Sent:* 13 June 2010 08:19 *To:* algogeeks@googlegroups.com *Subject:* Re: [algogeeks] c array @ram : i guess you have used some longer string and not strings btw.. what is Mingw ? gcc/g++ is not mingw, i guess -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Sun, Jun 13, 2010 at 8:13 AM, ram karthik.gin...@gmail.com wrote: D:\code\samplecode\main.cpp|5|error: initializer-string for array of chars is too long| I get this error on gcc (Mingw) . Though the array indexing starts from 0. The length specified in char str[7] is always straightforward . in this case char str[7] . the length of str is seven not eight ;hence the error -- ram *From:* algogeeks@googlegroups.com [mailto:algoge...@googlegroups.com] *On Behalf Of *sharad kumar *Sent:* 13 June 2010 07:59 *To:* algogeeks@googlegroups.com *Subject:* Re: [algogeeks] c array hey array indexing starts from 0 rite?? then y shld u get overflow in first place.. s t r i n g s \0 0 1 2 3 4 5 6 7 On Sat, Jun 12, 2010 at 9:14 PM, divya sweetdivya@gmail.com wrote: #includestdio.h int main() { char str[7]=strings; printf(%s\n,str); return 0; } here i m nt getting overflow error whereas if i write stringss instead of strings then there is overflow error.. isnt null stored after s in strings nd 1st case shd also give overflow??? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] The Mystery Spiral
all of these are with the unstandarized conio library ..use curses or ncurses instead or tput system call On Wed, Apr 28, 2010 at 8:45 AM, Chinmay S cvs...@gmail.com wrote: Yes there definitely is a fine distinctions between the two cases you mention. The program above fills the N*N numbers in spiral in decreasing order and then prints the matrix contents left to right , top to bottom. For the second program (that also prints in spiral order): http://2600hertz.wordpress.com/2010/03/20/the-mystery-spiral-part2/ GoodLUCK!! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] optimum algo for second largest
can anyone give me algorithm for finding the second largest element in array using tournament method requiring n+logn-2 comparisons --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---