Re: [algogeeks] Maximize the Time to see TV
@ above ur code fails for following example channel 1 : prog1 8:00-9:00, prog 2 9:00-10:00 channel 2 : prog1 8:15-10:00 your code returns 8:15- 10 and the answer should be channel1/prog1 + channel1/prog2 On 21 January 2011 12:54, Anand anandut2...@gmail.com wrote: Sort all program with their starting time. Appy the below pseudo code to find max number of programs he can watch. for(i=i;ilen;i++) { /*Check for overlap */ if(p[i].start p[i-1].end) { end = i; } else { /*Index of the first program to be watch*/ if((p[i-1].end - p[i-1].start) (p[i].end - p[i].start)) { start = i; } } } return end - start; On Thu, Jan 20, 2011 at 10:11 PM, snehal jain learner@gmail.comwrote: There is a TV avid person. HE wants to spend his max time on TV. There are N channels with different program of different length and diff times. WAP so that the person cam spend his max time watching TV. Precondition: If that person watches a program, he watches it completely. Ex: Channel1: prog1 – 8:00- 8:30 prog2: 9:00 – 10:00 prog3: 10:15 – 12:00 channel2: prg1 – 8:15 – 10:00 prg2: 10:30 – 12:00 So in this case max time will be if he watches: ch2/prg1 + ch1/prg3 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?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%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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Adobe Question
if sorted then a tweak in merge sort will work On 20 January 2011 23:23, nishaanth nishaant...@gmail.com wrote: Ya as Ashish said hashing is the best solution :) On Fri, Jan 14, 2011 at 6:00 PM, Ashish Goel ashg...@gmail.com wrote: ideally, a hashMap would be preferred walk through one array and set the corresponding entry, and then through another array, if any entry found, then they are not disjoint. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Fri, Jan 14, 2011 at 3:35 PM, bittu shashank7andr...@gmail.comwrote: how to find if two arrays of size n are disjoint or not in O(n) time ?? You can use only O(n) space The elements are +ve in the range 0 to n power 100.. 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.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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?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%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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] merging 2 search trees
@ above height will not be balanced then On 21 January 2011 19:15, nishaanth nishaant...@gmail.com wrote: Find the node in T which is the maximum(which is either the root or the rightmost in the right subtree). After finding this node, just make the right child of this node point to the root of T'. Correct me if i am wrong On Fri, Jan 21, 2011 at 2:43 PM, snehal jain learner@gmail.comwrote: You are given two height balanced binary search trees T and T’, storing m and n elements respectively. Every element of tree T is smaller than every element of tree T’. Every node u also stores height of the subtree rooted at it. Using this extra information how can you merge the two trees in time O(log m + log n) (preserving both the height balance and the order)? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?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%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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Adobe Question
if both arrray are sorted. take two ptrs, one pointing to a[0] other to b[0]. if elements are same then nt disjoint. else increment ptr pointing to smaller element until it becomes equal or greater than the element pointed by other. repeat until either ptr reaches end of array.. On 21 January 2011 21:42, Manmeet Singh mans.aus...@gmail.com wrote: how merge sort ?/ On Thu, Jan 20, 2011 at 11:23 PM, nishaanth nishaant...@gmail.com wrote: Ya as Ashish said hashing is the best solution :) On Fri, Jan 14, 2011 at 6:00 PM, Ashish Goel ashg...@gmail.com wrote: ideally, a hashMap would be preferred walk through one array and set the corresponding entry, and then through another array, if any entry found, then they are not disjoint. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Fri, Jan 14, 2011 at 3:35 PM, bittu shashank7andr...@gmail.comwrote: how to find if two arrays of size n are disjoint or not in O(n) time ?? You can use only O(n) space The elements are +ve in the range 0 to n power 100.. 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.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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?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%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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: difference x
@ saurabh and i wanna ur solution to this prob i know O(nlogn) post ur O(n) solution,. i hv some idea bt i wanna knw ur ans b4 mine On 22 December 2010 22:32, Divya Jain sweetdivya@gmail.com wrote: its okk On 22 December 2010 22:28, Ankur Khurana ankur.kkhur...@gmail.com wrote: saurabh , asking for a better sol. is not a crime. rest everybody is intelligent. On Wed, Dec 22, 2010 at 10:27 PM, Saurabh Koar saurabhkoar...@gmail.com wrote: @Snehal: I hv no problem wid ur doubts.Bt sometimes u post probs which r very basic.As u solved the looping prob in other thread I think u r intelligent enough to solve this prob(difference x) easily and also some other probs posted by u(not all).Some problems posted by u are really very tricky and I loved them.I jst requested u while posting if u review the ques carefully it will be helpful.I dint want to hurt u.If u r I m sorry.Bt still I will request u to post carefully.Lets finish this.And sorry once again. -- 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] Re: difference x
its okk On 22 December 2010 22:28, Ankur Khurana ankur.kkhur...@gmail.com wrote: saurabh , asking for a better sol. is not a crime. rest everybody is intelligent. On Wed, Dec 22, 2010 at 10:27 PM, Saurabh Koar saurabhkoar...@gmail.com wrote: @Snehal: I hv no problem wid ur doubts.Bt sometimes u post probs which r very basic.As u solved the looping prob in other thread I think u r intelligent enough to solve this prob(difference x) easily and also some other probs posted by u(not all).Some problems posted by u are really very tricky and I loved them.I jst requested u while posting if u review the ques carefully it will be helpful.I dint want to hurt u.If u r I m sorry.Bt still I will request u to post carefully.Lets finish this.And sorry once again. -- 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] linkd list
no not sorted On 15 December 2010 11:37, Anand anandut2...@gmail.com wrote: @Divya, I think you ask this question before. Not sure of the answer though :) On Tue, Dec 14, 2010 at 9:06 PM, Soumya Prasad Ukil ukil.sou...@gmail.com wrote: Are the linked list sorted? On 14 December 2010 05:33, divya sweetdivya@gmail.com wrote: Given three lists: A, B and C of length n each. Write a function which returns true if any 3 three numbers (1 from each list), sum up to zero. Else return false, if there is no such combination. -- 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. -- regards, soumya prasad ukil -- 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] Re: how many bananas?
nice solution:) On 14 December 2010 20:54, Prims topcode...@gmail.com wrote: total bananas=3000 ...max capacity=1000 ==3 trips needed to transport all for traveling 1 km 1st trip 998[eats 1 banana while coming and 1 banana while going back] 2nd trip 998 3rd trip 999[no need to go back] ==5 banana for travelling 1 km since 3 trips involved v spend 5 banana per km v need to reduce it to 2 trips ==the point where total banana becomes 2000 ==3000-2000=1000 ==1000/5=200 km at 200 km v hav 2000 bananas now for travelling 1 km 1st trip 998 2nd trip 999 ==3 banana for travellin 1 km find the point where this becomes single trip dat is total banana becomes 1000 ==2000-1000=1000 ==1000/3=333.3km v hav reached 533.33 km with 1000 banana now make a single trip of remaining 466.66 to city B v reach city B with 533.3 banana dats the answer 533 1/3 banana On Dec 14, 5:47 pm, divya sweetdivya@gmail.com wrote: There is a desert of 1000kms long. A camel is there and 3000 bananas. At one go a camel can take 1000 bananas. For each one km to walk camel eats 1 banana. How many bananas can we cross to the other side of desert -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sorted array
@above can u plz explain hw did u apply this formula? On 13 October 2010 16:14, Shiyam code_for_life mailshyamh...@gmail.comwrote: Lets say 8 integers are 1 to 8 So first way array can be split is 1,7 1st array can have one among 8 integers so in 8 ways and 2nd array has just one arrangement of other integers in sorted manner and same goes on for other ways to split the array. Whats wrong here? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sorted array
ignore the above post of mine @ shiyam u r doing wrong. we hv been the size of both array b and c which is 5 n 3 respectively @ AlgoSAu can u please explain ur method? On 13 October 2010 17:23, Divya Jain sweetdivya@gmail.com wrote: @above can u plz explain hw did u apply this formula? On 13 October 2010 16:14, Shiyam code_for_life mailshyamh...@gmail.comwrote: Lets say 8 integers are 1 to 8 So first way array can be split is 1,7 1st array can have one among 8 integers so in 8 ways and 2nd array has just one arrangement of other integers in sorted manner and same goes on for other ways to split the array. Whats wrong here? -- 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] Maximum size binary search tree
@ above ur soln ll fail in situation like 10 / \ 15 18 /\ / \ 22 7 17 77 the inorder is 22 15 7 10 17 18 77 so the longest increasing sequence is 7-77 but this is not a bst as 10 n 7 r nt connected On 24 June 2010 22:36, gopinath sikha gopisi...@gmail.com wrote: We can find the solution in O(n) where n is number of nodes. Do an in-order traversal of the binary tree. then scan through the numbers and find the list and find the longest(increasing or decreasing) sequence. That is the size of maximum size of BST in the given binary tree. On Wed, Jun 23, 2010 at 11:40 AM, Raj N rajn...@gmail.com wrote: Find the maximum size Binary search tree in a binary tree?? -- 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. -- -- If u doubt your believes,u believe ur doubts If u fail to practise,u practises failure Thanks and Regards GopiNath -- 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] Array with 0 and 1
i think u need to visit every element atleast once to see if its 1 or 0, nd so update the count. so i dont think it will be possible in less than O(n2) On 5 July 2010 15:41, amit amitjaspal...@gmail.com wrote: For a given matrix NxN having 0 or 1’s only. You have to find the count of rows and columns where atleast one 1 occurs. e,g 0 0 0 0 1 0 0 1 1 0 0 1 1 1 0 1 Row count having 1 atleast once: 3 Col count having 1 atleast once: 3 Any Solution less than O(n^2) will do -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: isbst
@ above here u r comparing node value with min and max only for eg if ur tree is 45 / \ 65 85 / 25 ur code will say that this is bst. bt it is not plzz correct me if i m wrong.. On 1 July 2010 16:17, CM Saikanth Varma saikanthva...@gmail.com wrote: Hi, The idea is like this: Isbst(node *t){ if(t==NULL){ return true; } if ( Isbst(t-left) Isbst(t-right) (maxValue(t-left) =(t-data) ) (minValue(t-right) = (t-data) ) return true; else return false; } I hope it makes sense :D On Thu, Jul 1, 2010 at 3:37 PM, vicky mehta...@gmail.com wrote: just do one thing print inorder. if sorted it is a BST On Jun 19, 2:57 pm, divya sweetdivya@gmail.com wrote: i have found the following code on net to check if the binarytreeis bst or not /* Returns true if a binarytreeis a binary searchtree. */ int isBST(struct node* node) { if (node==NULL) return(true); // false if the min of the left is than us if (node-left!=NULL minValue(node-left) node-data) return(false); // false if the max of the right is = than us if (node-right!=NULL maxValue(node-right) = node-data) return(false); // false if, recursively, the left or right is not a BST if (!isBST(node-left) || !isBST(node-right)) return(false); // passing all that, it's a BST return(true); } int minValue(struct node* node) { struct node* current = node; // loop down to find the leftmost leaf while (current-left != NULL) { current = current-left;} return(current-data); } and maxvalue also similarly returns right most vaslue oftree.. now i have a doubt that here v r comparing the node-data with only the min node nd max node.. shd nt we compare the node data with its left node and right node only. as it can b a case that node value is greater than min but less than its left node.. nd here we r nt checking that... plzz correct me if i m wrong... and is there any other efficient method to find isbst? -- 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
ya it is giving error cz u r incrementing x. u cant increment x as it is const. but there is no prob with declaration. its valid. On 26 June 2010 11:09, sharad kumar aryansmit3...@gmail.com wrote: pls c thz On Sat, Jun 26, 2010 at 10:48 AM, sharad kumar aryansmit3...@gmail.comwrote: cos if u declare const u cant change na.but volatile changes na.so practically u cant declareU cant do mtech at IIT and MBA at IIM at same time rite??? On Sat, Jun 26, 2010 at 10:43 AM, sharad kumar aryansmit3...@gmail.comwrote: no its not cos u have declared const and volatile hw is it possible can u go to IIT and IIM at same time On Sat, Jun 26, 2010 at 9:22 AM, sharad kumar sharad20073...@gmail.com wrote: static const volatile int x; Is the declaration valid plzzz explain -- 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 -- yezhu malai vaasa venkataramana Govinda Govinda -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: There is an array of odd and even numbers. Now, sort them in such a way that the top portion of the array contains odd numbers, bottom portion contains even numbers
@ gurav vivek i think u r only exchanging odd and even.. only putting even to end and odd in front and not doing descending sorting on odds and ascending on even.. plz correct me if i hv missed something.. On 24 June 2010 22:49, Vivek Sundararajan s.vivek.ra...@gmail.com wrote: Hi, how about this - Do a merge sort, now, while merging two sorted list, give more priority to odd numbers :) I believe this falls into the right solutions :) Any breaking cases? On 24 June 2010 09:41, Gaurav Singh gogi.no...@gmail.com wrote: I think in this case, bubble sorting will be a better idea. just replace the condition of comparison with the condition that earlier number is even and later number is odd. I mean we can do sumthing lyk this : for i=1 to n-1 for j=1 to n-i-1 if iseven(ar[j]) AND (NOT iseven(ar[j+1])) then swap both of them. Please correct me if I am wrong somewhere. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Reduce, Reuse and Recycle Regards, Vivek.S -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] sum k in sub array
@amir ur algo works only for positive elements array.. correct me if m wrong On 23 June 2010 00:28, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: for each element find sum[i] which is the summation of all elements with index less than or equal to i ( note that this array is always sorted) this can be done in O(n) then sum[i]-sum[j] when ji is the sum of range [j,i] then for each sum[i] binary search for sum[i]-k in the array sum which yields the overall running time of O(nlogn) On Tue, Jun 22, 2010 at 7:48 PM, sharad kumar sharad20073...@gmail.comwrote: How will you find the subarray whose sum is k in an array of negative and positive numbers -- 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] linked list
if we dont want to change original list.. is there ny efficient method for that? On 23 June 2010 06:49, ANUJ KUMAR kumar.anuj...@gmail.com wrote: reverse one of the linked lists in O(n) time and then see if the resulting one is same as the other one On Wed, Jun 23, 2010 at 1:56 AM, divya sweetdivya@gmail.com wrote: Two link lists are given ...check if one is reverse of other. Do it without using extra space. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: no of bits
@ dave how did u come to this formula... m nt getting the logic.. @ sathaiah yes u r rite On 22 June 2010 19:32, chitta koushik koushik.infin...@gmail.com wrote: For more such problems and solns http://graphics.stanford.edu/~seander/bithacks.htmlhttp://graphics.stanford.edu/%7Eseander/bithacks.html for (c = 0; v; c++) { v = v - 1; // clear the least significant bit set } O(k) -- no. of bits set in the number --Koushik C On Tue, Jun 22, 2010 at 7:16 PM, Dave dave_and_da...@juno.com wrote: Assuming 32 bit integers: n = ((x 1) 0x) + (x 0x) n = ((n 2) 0x) + (n % 0x) n = ((n 4) 0x0F0F0F0F) + (n 0x0F0F0F0F) n = ((n 8) 0x00FF00FF) + (n 0x00FF00FF) n = ((n 16) 0x) + (n 0x) n now is the number of bits set in x. Time is O(1). Dave On Jun 22, 6:26 am, divya sweetdivya@gmail.com wrote: find the no. of bits set in a no. in logn time -- 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] queue
there is a linked list where each node of linked list points to queue.. for eg. 1st node points to queue 1 2nd to queue 2 nd so on.. hope m clear this time.. On 20 June 2010 18:30, Piyush Verma 114piy...@gmail.com wrote: @divya plzz explain little more. m not getting... -- 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] doubly linked list
u can xor linked list. such that every node link contains the xor of its prev nd next node address.. since for 1st node prev is null ( 0) so its link contains only next. now to calculate next of 2nd node xor its link with 1st node's link nd u ll get 3 rd node.s adddress nd so on.. u can also use sum. store in link the sum of prev node n next node address.. bt this cn result in overflow. so xor method is better On 16 June 2010 09:14, sharad kumar sharad20073...@gmail.com wrote: u have to use XOR linked list -- 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] sum to 0
sort array c only. now select every pair from array a nd b ( o(n2)) for every pair find the element from c which gives sum of the three element 0. ( search using binary search as c is sorted) so the algo is O (n^2 logn)) On 16 June 2010 13:47, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: @algoose chase: you're right thx for the test case On Wed, Jun 16, 2010 at 11:45 AM, Algoose Chase harishp...@gmail.comwrote: @ Amir: I think you cannot find two numbers in B and C such that their sum is -A[k] in O(n) in all cases with the logic that you mentioned. for instance you can try with : A : 2 7 8 10 B :-2, 0, 1, 9 C: -7 -2 1 3 On Wed, Jun 16, 2010 at 5:56 AM, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: sort all arrays for each number in A , A[k] find two numbers in B and C such that their sum is -A[k] this can be done in O(n) time: set i at the beginning of B and j at the end of C while in or j=0 if ( B[i] + C[j] == -A[k] ) return true if ( B[i] + C[j] -A[k] ) increase i else decrease j we have to do this for each element of A so the overall complexity is: O(n2) time O(1) space correct me if I'm wrong On 6/15/10, sharad kumar sharad20073...@gmail.com wrote: plzzz comment on this question -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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] doubly linked list
yes u need to start frm beg.. On 16 June 2010 17:15, Vivek Sundararajan s.vivek.ra...@gmail.com wrote: so, this means that i can traverse the list only from the beginning of the link list right? what if im given a pointer pointing to some node other than the head of the doubly linked list? will i be able to traverse in any direction now? please let me know if im missing something :) Thank you, Vivek On 16 June 2010 15:37, divya jain sweetdivya@gmail.com wrote: u can xor linked list. such that every node link contains the xor of its prev nd next node address.. since for 1st node prev is null ( 0) so its link contains only next. now to calculate next of 2nd node xor its link with 1st node's link nd u ll get 3 rd node.s adddress nd so on.. u can also use sum. store in link the sum of prev node n next node address.. bt this cn result in overflow. so xor method is better On 16 June 2010 09:14, sharad kumar sharad20073...@gmail.com wrote: u have to use XOR linked list -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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] Mirroring Binary Tree Pattern Problem
This C code will create a new mirror copy tree. mynode *copy(mynode *root) { mynode *temp; if(root==NULL)return(NULL); temp = (mynode *) malloc(sizeof(mynode)); temp-value = root-value; temp-left = copy(root-right); temp-right = copy(root-left); return(temp); } On 13 June 2010 17:07, BALARUKESH SIVARAMAN sbalarukesh1...@gmail.comwrote: try this one.. make a level order traversal and store the elements in array... on the other system reconstruct it using right element for the left and left element for the right... -- 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] trees
reverse in order traversal till u reach kth node. reverse inorder means first visit right child then print data nd then left. On 14 June 2010 08:34, Lekha lek...@gmail.com wrote: Inorder traversal till u reach the kth element(If it is sorted in descending order, otherwise go till (n-k)th element).. On Sun, Jun 13, 2010 at 9:24 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: Repeated q. Search in the group -- -- 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 -- 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. -- Lekha -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: file handing
why a.c gets closed. well comma operator has left to right associativity. for eg a=(2,3,4) ; here is a=4 after the statement is executed so similarly why not here. y c.c is not closed here? On 13 June 2010 22:16, souravsain souravs...@gmail.com wrote: For Problem 3 see section 4.2 Using feof() incorrectly in http://www.drpaulcarter.com/cs/common-c-errors.php On Jun 13, 8:36 pm, divya jain sweetdivya@gmail.com wrote: sorry i pasted wrong questn unser 2.. the real question is which file will get closed through fclose() #includestdio.h int main() { FILE *fp,*fs,*ft; fp=fopen(a.c,r); fs=fopen(b.c,r); ft=fopen(c.c,r); fclose(fp,fs,ft); return 0; } 3. yes it is feof..srry typed it wrong... nd fgets(str,80,fp) is perfectly fine.. now the ans to this questn is that last line of the file will be printed twice...( which i m unable to get why)...plzz explain... @ souravsain plzz ignore this mail..srry for the inconvenience.. On 13 June 2010 17:37, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: in question 1... ch gets the value of EOF... so first kicit 44-a gokulpeth\0 nagpur will get printed and then the value of EOF.. question number 2 .. seems to me as nrml ...i think myfile.c only gets closed in question number 3..it shld be fgets(str,79,fp) On Sun, Jun 13, 2010 at 2:49 PM, divya sweetdivya@gmail.com wrote: 1. wat ll be the o/p. plz explain y? // abc.c contains kicit 44-a gokulpeth\0 nagpur #includestdio.h #includestdlib.h int main() { unsigned char ch; FILE *fp; fp=fopen(abc.c,r); if(fp==NULL) { printf(unable to open the file \n); exit(1); } while((ch=getc(fp))!=EOF) printf(%c,ch); fclose(fp); printf(\n,ch); return 0; } 2.which file will get closed through fclose() in the following program and why? #includestdio.h int main() {FILE *fp; char ch; int i=1; fp=fopen(myfile.c,r); while((ch=getc(fp)!=EOF)) { if(ch=='\n') i++; } fclose(fp); return 0; } 3.point out the error if any in following #includestdio.h int main() { FILE *fp; char str[80]; fp=fopen(trial,r); while(!eof(fp)) { fgets(str,80,fp); puts(str); } fclose(fp); return 0; } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem
i meant make an array of indexes.. index[]={0,1...,n-1} now sort the original array and move the elements of index array accordingly.. now follow modelling expert's algo nd while taking largest-smallest check if the index of largest in index array index of smallest in index array. On 13 June 2010 08:38, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @Satya: I don't think what you have coded will work.. though i have not read the whole code. Don't you think a simple divide and conquer scheme would work...(almost like the mergesort) -- 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 Sat, Jun 12, 2010 at 9:06 PM, Satya satya...@gmail.com wrote: This problem seems to be finding the maxdiff in an array. int maxdiff ( int A[], int n ) { // write your code here int max_diff = A[1] - A[0]; int min_element = A[0]; int i; for(i = 1; i n; i++) { if(A[i] - min_element max_diff) max_diff = A[i] - min_element; if(A[i] min_element) min_element = A[i]; } if(max_diff 0) max_diff = 0; return max_diff; } . Satya On Sat, Jun 12, 2010 at 3:18 PM, divya jain sweetdivya@gmail.comwrote: i think we need to maintain an array of index as well such that while subtracting smallest element from largest element of sorted array we need to check if index of largest is greater than index of smallest. if no..then this is not the solution.. On 12 June 2010 14:20, Modeling Expert cs.modelingexp...@gmail.comwrote: Let's say array A , 1 till n s_index = 1; e_index = n ; start = A[s_index] ; end = A[e_index]; result = 0; //! j - i if ( *end *start ){ result = index(end) - index(start) ( only of its greater than previous value of result ) break ; }else{ end-- ; //! till you reach start } now increment start , and repeat the process but only from A[n] till A[++result] , going further down is not required now. Average time o(n^2) Worst case : let's say we have descending array of ints, theno(n^2) Please suggest improvements On Jun 12, 12:14 am, amit amitjaspal...@gmail.com wrote: given an array A of n elements. for indexes j , i such that ji maximize( j - i ) such that A[j] - A [ i ] 0 . Any Algorithm less than O(n^2) would do. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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- pointers
bt the ans that sharad gave is ryt.. acc to me 1st row n 1st col of o/p shd b 2 (if size of int is 2) bt it is 1... On 13 June 2010 12:10, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @divya: u r rite.. that * should not be there -- 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 11:07 AM, divya jain sweetdivya@gmail.comwrote: ptr is a pointer naaa...then why ptr-p=*((arr+1)-arr) ??? why not (arr+1)-arr ?? i knw m wrong somewhr...plz correct me On 13 June 2010 07:57, Mahesh_JNU mahesh.jnumc...@gmail.com wrote: agreed . On Sun, Jun 13, 2010 at 7:48 AM, sharad kumar aryansmit3...@gmail.comwrote: 111 222 333 344 ptr++ -u do posst increment hence it goes to 1 ptr-p=*((arr+1)-arr)=1 llrly for other cases when u do *ptr++ due to operator precedence ptr++ is done and then dereferenced. hence u get 222 next *++ptr the ptr is incremented after dereferencing hence u get 333 next ++*ptr here the value t ptr s incrementas it is treated as++(*ptr) hence u get 3 but others refer to location hence 44 On Sat, Jun 12, 2010 at 9:21 PM, divya sweetdivya@gmail.comwrote: #includestdio.h int main() { static int arr[]={0,1,2,3,4}; int *p[]={arr,arr+1,arr+2,arr+3,arr+4}; int **ptr=p; ptr++; printf(%d %d %d\n,ptr-p,*ptr-arr,**ptr); *ptr++; printf(%d %d %d\n,ptr-p,*ptr-arr,**ptr); *++ptr; printf(%d %d %d\n,ptr-p,*ptr-arr,**ptr); ++*ptr; printf(%d %d %d\n,ptr-p,*ptr-arr,**ptr); return 0; } wat shd b the o/p n why... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mahesh Giri MCA Final Sem JNU, New Delhi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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
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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] union- c
its an o/p questn.. conversion wen ur variable is long..nd u r printing using %f...i dont know how to perform conversion from float to int long nd vice versa.. pl help On 13 June 2010 12:12, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: what is this for... and which conversion are you talking abt? -- 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 Sat, Jun 12, 2010 at 11:20 PM, divya sweetdivya@gmail.com wrote: #include stdio.h main() { union { long l_e; float f_e; } u; long l_v; float f_v; l_v = u.l_e = 10; printf(%f , (float)l_v); printf(%f , u.f_e); f_v = u.f_e = 3.555; printf(%d , (long)f_v); printf(%d , u.l_e); } hw to do the conversion here.. -- 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- pointers
oh yes.. wen ll i stop making this stupid mistakes :( On 13 June 2010 15:03, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @jalaj: exactly... so you(@divya) are right. Sharad's ans was right but logic wasn't. -- 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 2:35 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: actually when you subtract two pointers ... its get divided by the size of the variable type its point two... for example.. if you do .. p+1... where let say p is 200 and points to an int type variable then p+1 is 202...(assuming int is of size 2) so (p+1)-p..i.e 202-200 is 1 and not 2 On Sun, Jun 13, 2010 at 1:46 PM, divya jain sweetdivya@gmail.comwrote: bt the ans that sharad gave is ryt.. acc to me 1st row n 1st col of o/p shd b 2 (if size of int is 2) bt it is 1... On 13 June 2010 12:10, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @divya: u r rite.. that * should not be there -- 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 11:07 AM, divya jain sweetdivya@gmail.comwrote: ptr is a pointer naaa...then why ptr-p=*((arr+1)-arr) ??? why not (arr+1)-arr ?? i knw m wrong somewhr...plz correct me On 13 June 2010 07:57, Mahesh_JNU mahesh.jnumc...@gmail.com wrote: agreed . On Sun, Jun 13, 2010 at 7:48 AM, sharad kumar aryansmit3...@gmail.com wrote: 111 222 333 344 ptr++ -u do posst increment hence it goes to 1 ptr-p=*((arr+1)-arr)=1 llrly for other cases when u do *ptr++ due to operator precedence ptr++ is done and then dereferenced. hence u get 222 next *++ptr the ptr is incremented after dereferencing hence u get 333 next ++*ptr here the value t ptr s incrementas it is treated as++(*ptr) hence u get 3 but others refer to location hence 44 On Sat, Jun 12, 2010 at 9:21 PM, divya sweetdivya@gmail.comwrote: #includestdio.h int main() { static int arr[]={0,1,2,3,4}; int *p[]={arr,arr+1,arr+2,arr+3,arr+4}; int **ptr=p; ptr++; printf(%d %d %d\n,ptr-p,*ptr-arr,**ptr); *ptr++; printf(%d %d %d\n,ptr-p,*ptr-arr,**ptr); *++ptr; printf(%d %d %d\n,ptr-p,*ptr-arr,**ptr); ++*ptr; printf(%d %d %d\n,ptr-p,*ptr-arr,**ptr); return 0; } wat shd b the o/p n why... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mahesh Giri MCA Final Sem JNU, New Delhi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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
Re: [algogeeks] union- c
wat i meant is the ans of this questn is 10.00 0.00 3 1080263967 now my questn is y u.f_e is printing 0.00 and similarly y u.l_e is giving this value... On 13 June 2010 15:08, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: If you are not able to print the long int and that's the prob, you can use %ld instead of %d -- 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 1:49 PM, divya jain sweetdivya@gmail.comwrote: its an o/p questn.. conversion wen ur variable is long..nd u r printing using %f...i dont know how to perform conversion from float to int long nd vice versa.. pl help On 13 June 2010 12:12, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: what is this for... and which conversion are you talking abt? -- 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 Sat, Jun 12, 2010 at 11:20 PM, divya sweetdivya@gmail.comwrote: #include stdio.h main() { union { long l_e; float f_e; } u; long l_v; float f_v; l_v = u.l_e = 10; printf(%f , (float)l_v); printf(%f , u.f_e); f_v = u.f_e = 3.555; printf(%d , (long)f_v); printf(%d , u.l_e); } hw to do the conversion here.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: bits
thanks to all :) @ souravsain sorry for the inconvenience On 13 June 2010 20:01, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @Souravsain : Is there any serious problem in this. Anyone can just add a [C++] in the subject and uninterested people can make filters in gmail :) -- 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 6:35 PM, souravsain souravs...@gmail.com wrote: @divya Lets keep discussions in t his group limited to Algos and problems neutral to any language. Request you to post these C++ / C language specific questions to those language specific groups. This will not only help this group remain confined to its core purpose but will help you get better insights to ur problem by language specific geeks there. For C++ I would recommend you to try the group http://groups.google.co.in/group/comp.lang.c++.moderated/topics?hl=en. Regards, Sourav On Jun 13, 2:29 pm, divya sweetdivya@gmail.com wrote: tell the o/p of following with explanations 1. #includestdio.h int main() { struct value { int bit1:1; int bit3:4; int bit4:4; }bit; printf(%d\n,sizeof(bit)); return 0; } 2. #includestdio.h int main() { struct value { int bit1: 1; int bit3: 4; int bit4: 4;} bit={1,2,2}; printf(%d %d %d\n,bit.bit1,bit.bit3,bit.bit4); return 0; } 3 can bit field be used in union?? -- 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] file handing
sorry i pasted wrong questn unser 2.. the real question is which file will get closed through fclose() #includestdio.h int main() { FILE *fp,*fs,*ft; fp=fopen(a.c,r); fs=fopen(b.c,r); ft=fopen(c.c,r); fclose(fp,fs,ft); return 0; } 3. yes it is feof..srry typed it wrong... nd fgets(str,80,fp) is perfectly fine.. now the ans to this questn is that last line of the file will be printed twice...( which i m unable to get why)...plzz explain... @ souravsain plzz ignore this mail..srry for the inconvenience.. On 13 June 2010 17:37, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: in question 1... ch gets the value of EOF... so first kicit 44-a gokulpeth\0 nagpur will get printed and then the value of EOF.. question number 2 .. seems to me as nrml ...i think myfile.c only gets closed in question number 3..it shld be fgets(str,79,fp) On Sun, Jun 13, 2010 at 2:49 PM, divya sweetdivya@gmail.com wrote: 1. wat ll be the o/p. plz explain y? // abc.c contains kicit 44-a gokulpeth\0 nagpur #includestdio.h #includestdlib.h int main() { unsigned char ch; FILE *fp; fp=fopen(abc.c,r); if(fp==NULL) { printf(unable to open the file \n); exit(1); } while((ch=getc(fp))!=EOF) printf(%c,ch); fclose(fp); printf(\n,ch); return 0; } 2.which file will get closed through fclose() in the following program and why? #includestdio.h int main() {FILE *fp; char ch; int i=1; fp=fopen(myfile.c,r); while((ch=getc(fp)!=EOF)) { if(ch=='\n') i++; } fclose(fp); return 0; } 3.point out the error if any in following #includestdio.h int main() { FILE *fp; char str[80]; fp=fopen(trial,r); while(!eof(fp)) { fgets(str,80,fp); puts(str); } fclose(fp); return 0; } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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] Re: Array Problem
i think we need to maintain an array of index as well such that while subtracting smallest element from largest element of sorted array we need to check if index of largest is greater than index of smallest. if no..then this is not the solution.. On 12 June 2010 14:20, Modeling Expert cs.modelingexp...@gmail.com wrote: Let's say array A , 1 till n s_index = 1; e_index = n ; start = A[s_index] ; end = A[e_index]; result = 0; //! j - i if ( *end *start ){ result = index(end) - index(start) ( only of its greater than previous value of result ) break ; }else{ end-- ; //! till you reach start } now increment start , and repeat the process but only from A[n] till A[++result] , going further down is not required now. Average time o(n^2) Worst case : let's say we have descending array of ints, theno(n^2) Please suggest improvements On Jun 12, 12:14 am, amit amitjaspal...@gmail.com wrote: given an array A of n elements. for indexes j , i such that ji maximize( j - i ) such that A[j] - A [ i ] 0 . Any Algorithm less than O(n^2) would do. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: identify the recurring part for a given decimal no
@anurag i dint get ur approach..which numerator n denominator u r talking about..plz explain.. thanks in advance On 11 June 2010 08:57, Anurag Sharma anuragvic...@gmail.com wrote: Please note that the fractional repeating part is recurring. and so that 4th temporary variable assignment will be this way- temp=x*1 - x= 233456.34563456... - 23.34563456 = 233433.0 ( mark the fractional part is 0 now since the infinitely repeating 3456... will get cancelled) In this case you can say that 4 places are repeating. But yes its according to the maths and in any programming language whenever you divide the numerator and denominator you wont get this infinitely recurring decimal places. @divya, also your approach wont work if the recurring fractional digits start after few places from the decimal like in the case of 23.123345634563456 (note here after the decimal place 123 is not repeating while 3456.. after this 123 is repeating.) What I suggest in this case is keep dividing the numerator by denominator and at every step keep inserting the tupple (remainder, quotient) of that division step in a set. and before inserting in the set check whether it already exists. If yes then the all the quotients following from that point (including the point) will be recurring. Regards, Anurag Sharma On Thu, Jun 10, 2010 at 8:25 AM, Veer Sharma thisisv...@rediffmail.comwrote: Seems it wont work... x=23.34563456 temp = x*100 -x = 233.4563456 - 23.34563456 = 210.11071104 temp = x*100 -x = 2334.563456 - 23.34563456 = 2311.21782144 temp = x*1000 -x = 23345.63456 - 23.34563456 = 23322.28892544 temp = x*1 -x = 233456.3456 - 23.34563456 = 233432.6544 temp = x*10 -x = 2334563.456 - 23.34563456 = 2334540.11036544 ... On Jun 9, 11:24 pm, Anurag Sharma anuragvic...@gmail.com wrote: multiply the original number x=23.34563456 Anurag Sharma On Wed, Jun 9, 2010 at 10:36 PM, Veer Sharma thisisv...@rediffmail.com wrote: One question: No x = 23.34563456 temp = x X 10 = 233.4563456 temp = temp - x = 210.11071104 decimal part zero? No. Now multiply the no. with 100. Which no? original x (= 23.34563456) or new no. temp (=210.11071104)? On Jun 9, 8:12 pm, divya jain sweetdivya@gmail.com wrote: multiply the no. with 10 nd store in temp. now subtract no from temp. check if the decimal part is zero if yes. then 1st digit after decimal is recurring. if no. multiply the no with 100 and repeat . if this time decimal part is zero then 2 digits after decimal r recurring nd so on.. On 8 June 2010 21:45, Veer Sharma thisisv...@rediffmail.com wrote: You have a Numerator and Denominator. After division you might get a recurring decimal points float as the answer. Problem is: You need to identify the recurring part for a given decimal no? For example 23.34563456 ... return 3456 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send
Re: [algogeeks] Re: c output
one of my frnd askd me this question... On 11 June 2010 21:34, Raj N rajn...@gmail.com wrote: @kirubakaran: How can it be 1,1 ? No of characters read in a is 5+ 1 for '\n' so its 6 and for the next one 1+1=2 On Fri, Jun 11, 2010 at 9:09 AM, kirubakaran kirubakaran1...@gmail.comwrote: Output will be 1,1 bcoz printf returns number of characters or integers printed On Jun 11, 12:26 am, divya sweetdivya@gmail.com wrote: #include stdio.h main() { int a = 1; char b='c'; int i,j; printf(%d,%d,printf(%d\n,a),printf(%c\n,b)); wat shd b the o/p of this..plzz explain y? -- 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] output
sorry for the silly question i got rhe point.. @ rohit compiler is doing rite..read mahesh's explanatn On 13 June 2010 08:27, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: This is very bad. Change your compiler if it compiles this stuff :) btw.. which compiler is it? Output for me : ro...@rohit-laptop:~/dump$ gcc c.c c.c: In function ‘main’: c.c:14: error: incompatible types when assigning to type ‘char[20]’ from type ‘char *’ c.c:15: error: incompatible types when assigning to type ‘char[20]’ from type ‘char *’ -- 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, Mahesh_JNU mahesh.jnumc...@gmail.comwrote: Well As we know for copying the string we can can copy it as a simple variable as in case of address copying. when u r doing names[3] = names[4] , it means u r trying to copy it directly bt in the case of char *names[] , as it is the array of pointers so u can copy the address from one pointer to another pointer Thanks On Sat, Jun 12, 2010 at 9:12 PM, divya sweetdivya@gmail.com wrote: #includestdio.h int main() { char names[][20]={ roshni, manish, sona, baiju, ritu }; int i; char *t; t=names[3]; names[3]=names[4]; names[4]=t; for(i=0;i=4;i++) printf(%s,names[i]); printf(\n); return 0; } here i get l value required as error and if i replace char names[][2] with char *names[].. then there is no error nd the names[3] n names[4] interchange pl explain why??? -- 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. -- Mahesh Giri MCA Final Sem JNU, New Delhi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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
hmm..the prob is here wid my compiler...!! anyways thanks to all On 13 June 2010 10:28, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: oh.. yes.. my mistake (strings\0).length=8 :P -- 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 10:24 AM, Rahul Kushwaha rahul.kushw...@gmail.com wrote: #includestdio.h int main() { char str[7]=strings; printf(%s\n,str); return 0; } it is showing error on code block and dev cpp also... this is an error no doubt. also mentioned in denis m ritchie -- 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- pointers
ptr is a pointer naaa...then why ptr-p=*((arr+1)-arr) ??? why not (arr+1)-arr ?? i knw m wrong somewhr...plz correct me On 13 June 2010 07:57, Mahesh_JNU mahesh.jnumc...@gmail.com wrote: agreed . On Sun, Jun 13, 2010 at 7:48 AM, sharad kumar aryansmit3...@gmail.comwrote: 111 222 333 344 ptr++ -u do posst increment hence it goes to 1 ptr-p=*((arr+1)-arr)=1 llrly for other cases when u do *ptr++ due to operator precedence ptr++ is done and then dereferenced. hence u get 222 next *++ptr the ptr is incremented after dereferencing hence u get 333 next ++*ptr here the value t ptr s incrementas it is treated as++(*ptr) hence u get 3 but others refer to location hence 44 On Sat, Jun 12, 2010 at 9:21 PM, divya sweetdivya@gmail.com wrote: #includestdio.h int main() { static int arr[]={0,1,2,3,4}; int *p[]={arr,arr+1,arr+2,arr+3,arr+4}; int **ptr=p; ptr++; printf(%d %d %d\n,ptr-p,*ptr-arr,**ptr); *ptr++; printf(%d %d %d\n,ptr-p,*ptr-arr,**ptr); *++ptr; printf(%d %d %d\n,ptr-p,*ptr-arr,**ptr); ++*ptr; printf(%d %d %d\n,ptr-p,*ptr-arr,**ptr); return 0; } wat shd b the o/p n why... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mahesh Giri MCA Final Sem JNU, New Delhi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: identify the recurring part for a given decimal no
thanks anurag :) On 12 June 2010 20:07, Anurag Sharma anuragvic...@gmail.com wrote: Since we are given numerator 'n' and denominator 'd' separately already. and considering n and d as integers and d!=0 we can safely assume n/d as either a terminating fraction or a non terminating but recurring fraction, in which case we have to find the recurring digits of the fraction. Now what I suggested was almost same as Ravi's approach. take a Set 'S' keeping tuples (R,Q) where R is the current remainder and Q is the factor such that d*Q is subtracted from the number to get R. In other words. if at an intermediate step of division we have 'a' as the divident left then Q=floor(a/d) and R=a%d Keep dividing 'n' by 'd' like it is done manually. After every division check- 1. If the current remainder is not present in 'S' then add current remainder 'R' and corresponding quotient 'Q' in the set 2. If R is found in the set S, then all the following entries in the set until end will constitute the recurring digits. taking Ravi's example:- Example: 7) 9 (1.*285714*28S=[] 7 -- 20 S=[(2,2)] 14 --- 60S=[(2,2), (6,8)] 56 --- 40 S=[(2,2), (6,8), (4,5)] 35 --- 50 S=[(2,2), (6,8), (4,5), (5,7)] 49 --- 10 S=[(2,2), (6,8), (4,5), (5,7), (1,1)] 7 30 S=[(2,2), (6,8), (4,5), (5,7), (1,1), (3,4)] 28 ^ | 20 2 is found in S here, so recurring digits are 285714 14 60 56 repeats hope its clear Anurag Sharma On Sat, Jun 12, 2010 at 4:02 PM, divya jain sweetdivya@gmail.comwrote: @anurag i dint get ur approach..which numerator n denominator u r talking about..plz explain.. thanks in advance On 11 June 2010 08:57, Anurag Sharma anuragvic...@gmail.com wrote: Please note that the fractional repeating part is recurring. and so that 4th temporary variable assignment will be this way- temp=x*1 - x= 233456.34563456... - 23.34563456 = 233433.0 ( mark the fractional part is 0 now since the infinitely repeating 3456... will get cancelled) In this case you can say that 4 places are repeating. But yes its according to the maths and in any programming language whenever you divide the numerator and denominator you wont get this infinitely recurring decimal places. @divya, also your approach wont work if the recurring fractional digits start after few places from the decimal like in the case of 23.123345634563456 (note here after the decimal place 123 is not repeating while 3456.. after this 123 is repeating.) What I suggest in this case is keep dividing the numerator by denominator and at every step keep inserting the tupple (remainder, quotient) of that division step in a set. and before inserting in the set check whether it already exists. If yes then the all the quotients following from that point (including the point) will be recurring. Regards, Anurag Sharma On Thu, Jun 10, 2010 at 8:25 AM, Veer Sharma thisisv...@rediffmail.comwrote: Seems it wont work... x=23.34563456 temp = x*100 -x = 233.4563456 - 23.34563456 = 210.11071104 temp = x*100 -x = 2334.563456 - 23.34563456 = 2311.21782144 temp = x*1000 -x = 23345.63456 - 23.34563456 = 23322.28892544 temp = x*1 -x = 233456.3456 - 23.34563456 = 233432.6544 temp = x*10 -x = 2334563.456 - 23.34563456 = 2334540.11036544 ... On Jun 9, 11:24 pm, Anurag Sharma anuragvic...@gmail.com wrote: multiply the original number x=23.34563456 Anurag Sharma On Wed, Jun 9, 2010 at 10:36 PM, Veer Sharma thisisv...@rediffmail.comwrote: One question: No x = 23.34563456 temp = x X 10 = 233.4563456 temp = temp - x = 210.11071104 decimal part zero? No. Now multiply the no. with 100. Which no? original x (= 23.34563456) or new no. temp (=210.11071104)? On Jun 9, 8:12 pm, divya jain sweetdivya@gmail.com wrote: multiply the no. with 10 nd store in temp. now subtract no from temp. check if the decimal part is zero if yes. then 1st digit after decimal is recurring. if no. multiply the no with 100 and repeat . if this time decimal part is zero then 2 digits after decimal r recurring nd so on.. On 8 June
Re: [algogeeks] Re: isomorphic trees
my solution *isomorphic* (struct node *head1,struct node *head2) { if (head1!=NULL head2!=NULL) { if (head1-data == head2-data) { if (head1-left-data == head2-left-data) { return (isomorphic(head1left,head2-left ) isomorphic(head1right,head2-right)); } else if (head-left-data == head2-right-data) { return (isomorphic**(head1left,head2-right) (isomorphichead1right,head2-left)); } else return (false); } } else if (head1 == NULL head2 == NULL) return (true); else return (false); } On 10 June 2010 00:00, souravsain souravs...@gmail.com wrote: As per @Algoose's explanation, this can be found using the algorithm to comapre if 2 binary trees are equal (quite often asked and found in net). In this we generally go recursive and say T1 is equal to T2 if T1=T2 and same holds for T1-Left, T2-Left (recursive call on left tree) and same holds for T1-Right, T2-Right (recursive call on right tree). We can use the same and change the calls as if T1=T2 and same holds for T1-Left, T2-Right (recursive call on left tree) and same holds for T1-Right, T2-Left (recursive call on right tree). Sain On Jun 9, 10:45 pm, saurabh gupta sgup...@gmail.com wrote: is-isomorphic(t1, t2) { t1ld = t1-left-data t2ld = t2-left-data //. //base case for null or replace by sentinels and check if( t1ld == t2ld t1rd == t2rd) return is-isomorphic(t1ld, t2ld) return is-isomorphic(t1rd, t2rd) if (t1ld == t2rd t1rd == t2ld) return is-isomorphic(t1ld, t2rd) return is-isomorphic(t1rd, t2ld) return false; } On Wed, Jun 9, 2010 at 8:29 PM, divya jain sweetdivya@gmail.com wrote: @vadivel and anand { 1,2,3 } is *isomorphic* to { 1,3,2 } { 1,2,3,4,5,6,7 } is *isomorphic* to { 1,3,2,7,6,4,5 } { 1,2,3,4,5,6,7 } is NOT *isomorphic* to { 1,3,2,4,5,6,7 } so its nt necessary that right and left will interchange. it may or may not. if all right and left are interchanged then it is mirror tree. i think ur code is for mirror tree and not isomorphic tree.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] identify the recurring part for a given decimal no
multiply the no. with 10 nd store in temp. now subtract no from temp. check if the decimal part is zero if yes. then 1st digit after decimal is recurring. if no. multiply the no with 100 and repeat . if this time decimal part is zero then 2 digits after decimal r recurring nd so on.. On 8 June 2010 21:45, Veer Sharma thisisv...@rediffmail.com wrote: You have a Numerator and Denominator. After division you might get a recurring decimal points float as the answer. Problem is: You need to identify the recurring part for a given decimal no? For example 23.34563456 ... return 3456 -- 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] isomorphic trees
@vadivel and anand { 1,2,3 } is *isomorphic* to { 1,3,2 } { 1,2,3,4,5,6,7 } is *isomorphic* to { 1,3,2,7,6,4,5 } { 1,2,3,4,5,6,7 } is NOT *isomorphic* to { 1,3,2,4,5,6,7 } so its nt necessary that right and left will interchange. it may or may not. if all right and left are interchanged then it is mirror tree. i think ur code is for mirror tree and not isomorphic tree.. -- 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] min no of policemen
@sharad.. sorry bt i dint get how to use bellman ford or topological sort here... can u plz explain... On 8 June 2010 05:53, sharad kumar aryansmit3...@gmail.com wrote: for placing police man we can use bellman ford bfs.or even make use of topological sort. On Mon, Jun 7, 2010 at 9:59 PM, divya sweetdivya@gmail.com wrote: consider a tree. policemen is to be placed such that for each edge of tree, there is a policeman on atleast one side of each edge. tell the min no. of policemen and their locatn in time O(n) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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] Puzzle:
yes even i dont think its possible as there is no n-1th state..ie there is no state from whr u can come to 2 8 5..so plz check On 7 June 2010 20:23, mohit ranjan shoonya.mo...@gmail.com wrote: is it possible ? if we say nth state is [2, 8, 5] I could not find possible (n-1)th state Mohit Ranjan On Mon, Jun 7, 2010 at 2:02 PM, sharad sharad20073...@gmail.com wrote: : Three containers are of 15,10 and 6 ltrs capacity. Initially its in configuration (15,0,0). Make it to configuration (2,8,5) -- 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] Pointer to a constant
i think both statements shd give error. as u r trying to change int to const int in 2 and const int to int in 1.. On 7 June 2010 19:59, mohit ranjan shoonya.mo...@gmail.com wrote: @Raj, no they are not same case 1: i is const case 2: ptr is const and whatever is const cann't be modified Mohit Ranjan On Mon, Jun 7, 2010 at 3:01 PM, Raj N rajn...@gmail.com wrote: Can someone tell me the difference between 1) const int i=5; 2) int i=5; int *ptr=i; const int *ptr=i; In the first case i can be modified via ptr i.e *ptr++ is valid. In the second case *ptr++ is illegal. Why is that so? Aren't they same? -- 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] Number of sequences of n binary digits that don't contain two 1's in a row
how do u come to this formula T(n)=fib(n+2).. plz explain On 7 June 2010 21:19, saurabh gupta sgup...@gmail.com wrote: it might be referring to no of sequences (say T(n) ) with no consecutive 1's for n = 3, ans would be 5 viz. 000, 001, 010, 100, 101 T(n) = fib(n+2) where fib = Fibonacci series which is interesting. On Sat, Jun 5, 2010 at 11:40 AM, Raj N rajn...@gmail.com wrote: @sharad: What about 101 even it doesn't have two 1's in a row On Sat, Jun 5, 2010 at 8:59 AM, sharad kumar aryansmit3...@gmail.comwrote: @rajn.can it be subsequence doesnt have one's too.hence 000,001,010,100 is required answer. On Sat, Jun 5, 2010 at 12:13 AM, Raj N rajn...@gmail.com wrote: Hi, I came across this question to find the number of sequences of n binary digits that don't contain 2 1's in a row. I wanted to know what exactly this means. Is it like if n=3 then compute all binary numbers having 3 digits which don't have consecutive 1's 110, 011, 111 ?? If not help me understanding it. Thanks!! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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. -- 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 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] Single ordered list
merging as in merge sort. On 8 June 2010 19:59, Raj N rajn...@gmail.com wrote: What is the most efficient way of combining 2 separate ordered list into a single ordered list ? -- 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] min no of policemen
edge is the link connecting two nodes of a tree On 8 June 2010 11:23, Anurag Sharma anuragvic...@gmail.com wrote: Can you expain edge of the tree. I could not get that. Anurag Sharma On Tue, Jun 8, 2010 at 5:53 AM, sharad kumar aryansmit3...@gmail.comwrote: for placing police man we can use bellman ford bfs.or even make use of topological sort. On Mon, Jun 7, 2010 at 9:59 PM, divya sweetdivya@gmail.com wrote: consider a tree. policemen is to be placed such that for each edge of tree, there is a policeman on atleast one side of each edge. tell the min no. of policemen and their locatn in time O(n) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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] matix flipping
let a[n][n] be the input array nd b[][] be the output for(i=0;in;i++) for(j=0;jn;j++) b[i][j]=a[n-j-1][n-i-1] On 7 June 2010 08:26, sharad sharad20073...@gmail.com wrote: write a c routine to flip an nXn matrix about its non major diagnol 3 4 5 6 7 9 1 2 8 Transpose is: 8 9 5 2 7 4 1 6 3 -- 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] array question
@sharad while storing each element in hash by your approach u ll check if its already there in hash. so the complexity here will be O(n2). correct me if i m wrong. isnt there ny better algo..? On 6 June 2010 06:28, sharad kumar aryansmit3...@gmail.com wrote: @dhivya:keep storing the first occurance element index in hash map and then start insertin eleement based on index position On Sun, Jun 6, 2010 at 12:31 AM, divya sweetdivya@gmail.com wrote: Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. So cant use a dictionary. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: array question
output willl be 12 12 5 6 6 On 6 June 2010 18:27, souravsain souravs...@gmail.com wrote: @divya: Does your problem require the output to be sorted also? What will be the output required if inout is 12,5,6,12,6? Will it be 12,12,6,6,5 or 12,12,5,6,6,? Sain On Jun 6, 12:01 am, divya sweetdivya@gmail.com wrote: Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. So cant use a dictionary -- 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] o/p
output on my compiler is 165535 as i=0 initialy ++i is true and so for loop condition is true and printf is executed. when i becomes 65535 then ++i is equal to 0 and so for loop condition becomes false. On 5 June 2010 13:44, sharad sharad20073...@gmail.com wrote: #includestdio.h int main() { short int i=0; for(i=5i=-1;++i;i0) printf(%u\n,i); return 0; } o/p coming is 1...4,294,967,295 short int is of 2 bytes can any one plzz explain the o/p -- 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] Largest even length palindrome in a string!!
1. first find two consecutive letters which are same. 2 point ptr1 to left character and ptr2 to right one 3. now increment ptr2 and decrement ptr1. compare if they are pointing to same characters. if yes repeat this step 4. if no then store in length ptr2-ptr1-2 5. go to step 1 untill all consecutive same letters have been scanned. if the new length found is greater then previous one. then discard previous one and store in length new length. 6. return the substring with largest length On 5 June 2010 15:04, Satya satya...@gmail.com wrote: Hi, How to find largest palindrome, which is even in length in a string. Complexity should be lessthan O(n^2). Ex;- abacbbcababac - Given string. 'abacbbcaba' - is the largest even length palindrome. Thanks, Satya -- 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] dynamic vs greedy aproach
how can we make out whether to apply greedy approach or dynamic programming to a problem?? -- 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] o/p
turbo c++ and my o/p is logical as well On 5 June 2010 17:58, sharad kumar sharad20073...@gmail.com wrote: @divya,which compiler u r using,i m getting this o/p on gcc compiler @mohit:loop stops at 4,294,967,295 in gcc -- 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] Quick short stack space reduction
if u sort the larger one first one then smaller one will be on stack for a long time on the other hand if u sort smaller one first then larger one will be in stack for long time. so more space is wasted is 2nd case so we shd sort larger first. correct me if i am wrong plzzz On 4 June 2010 18:08, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: if you short the larger one first, then the smaller one will be in the stack for a long time. Which is wasting stack space. Now stop shorting and start sorting ! :) -- 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 -- 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] Check if 2 linked lists are identical
construct bst from both list and check if the bst are equal by printing their inorder traversal. On 2 June 2010 22:47, Raj N rajn...@gmail.com wrote: @Antony: The 2 lists should have the same elements as well the number must be equal On Wed, Jun 2, 2010 at 5:38 PM, Antony Vincent Pandian.S. sant...@gmail.com wrote: @Raj What do you mean by identical? You are just concerned about the presence of one element in another LL or you are concerned about the equality of number of elements too? On 6/2/10, Raj N rajn...@gmail.com wrote: @sharad kumar: But don't you think this'll consume a lot of space. Merge sort will give O(nlogn) complexity when a separate LL is used to store the sorted elements but if we disbuild the same LL it'll be O(n2). And also wat do u mean by combining LL can u explain On Wed, Jun 2, 2010 at 6:48 AM, sharad kumar aryansmit3...@gmail.com wrote: @Raj:sorting can be done in O(nlogn)..sort both and compare both.or use a hash map to store all elements of one LL and then compare it with otheror combine both the LL perform merge sort and start deleting adjacent elements.if adjacent elements in equal count then LL are equal and at end of process we get an empty list. On Tue, Jun 1, 2010 at 11:55 PM, Raj N rajn...@gmail.com wrote: Hi all, Can someone suggest an efficient algorithm to check if 2 linked lists are identical. If 2 lists have to be sorted then there'll be a lot of space consumption for 2 separate linked lists. Can the whole process be done O(n2) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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. -- Sent from my mobile device Luv, S.Antony Vincent Pandian -- 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] Implementing 2 stacks within a single linear array
for three stacks u can use indices 0 3 6 etc for stack1. 1 4 7 for stack 2 and 2 5 8 etc for stack 3. now if any of the stack overflows but there is still space in array as other stacks have few element then now u can grow ur stack in reverse direction as shown below : indices of array : 0 1 2 3 4 5 6 7 8 9 10 11 12 contents 1 2 3 1 1 1 1 / \ \ top2top3 top1 here 1 represents element of stack1 2 for stack 2 and so on. now if u want to insert more element in stack 1 it will overflow while 2 and 3 have space so wat u can do now is grow stack 1 in reverse direction. ie now place elements for stack 1 in index 11 and so now top1 will point to 11 and so on. u can indicate this behaviour of stack1 by using some tag. i hope this will work.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: partion of array
u have not sorted the array . first sort the array nd then apply the approach. u ll get the ryt ans On 1 June 2010 21:32, Jitendra Kushwaha jitendra.th...@gmail.com wrote: Using subset sum method we can solve this. It actually DP check out Paybill question and its solution on topcoder website link : http://www.topcoder.com/stat?c=problem_statementpm=3114rd=5865 you will have a better understanding of subset sum problem after this -- Regards Jitendra Kushwaha Undergradute Student Computer Science Eng. 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Can you solve this?
same question as wat i asked in partioning of array such that the diff is min. On 31 May 2010 22:07, Senthilnathan Maadasamy senthilnathan.maadas...@gmail.com wrote: Same question with interesting answers in stackoverflow : http://stackoverflow.com/questions/890171/algorithm-to-divide-a-list-of-numbers-into-2-equal-sum-lists On Mon, May 31, 2010 at 5:54 PM, Anurag Sharma anuragvic...@gmail.comwrote: Well, in that case, then just forget the balancing the number of elements in the 2 teams portion of my solution above :) Anurag Sharma http://anuragsharma-sun.blogspot.com/ On Mon, May 31, 2010 at 10:38 AM, Nik_nitdgp nikhil.bhoja...@gmail.comwrote: This problem is like 2 processor job scheduling problem ,We may get an optimal solution for different instances using different algorithm apart from brute force.Whereas Brute force covers all possible subsets but may take years to complete if N is large. above algo fails in the following example. Eg. 2 2 2 3 3 above algo gives: T1: 2 2 3 =7 T2: 2 3 =5 But closest distribution is T1=2 2 2=6 T2 3 3=6 On May 31, 9:30 am, W Karas wka...@yahoo.com wrote: Is this the same problem as: http://groups.google.com/group/algogeeks/browse_frm/thread/26c31cc253. .. ? Or can the teams have different numbers of players? On May 30, 2:28 pm, Veer Sharma thisisv...@rediffmail.com wrote: Hi Friends, This is my first post to this forum. A Hi to all of you and here is my first problem... Giiven int n, the total number of players and their skill-point. Distribute the players on 2 evenly balanced teams. Lets see who gives the best solution (least space complexity / least time complexity or both...) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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] Removing extra parentheses in an infix string
1.calculte the postfix of given expression. 2.now remove a particular parenthesis from expression and check if the postfix of this expression is equal to the postfix of original expression. if yes then the parenthesis we have removed were extra. if no then the parenthesis were not exta. 3 now remove other parenthesis as step 2 and repeat till u have done this for all parenthesis On 1 June 2010 20:12, Raj N rajn...@gmail.com wrote: How to remove extra parentheses in an infix string. For example if it is A+(B*C) parentheses for * is not required as it has higher precedence. Can someone suggest a good routine for 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: partion of array
oh...okay... good example... On 3 June 2010 13:23, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @divya: but still haven't you seen Jagadish's example? It is a counterexample to your greedy approach. -- 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 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: partion of array
my algo on the array 1 200 500 2000 sort the array therefore we have now 2000 500 200 1 1st array will have largest element A= {2000} and B={500} sumA=2000 sumB=500 now abs((2000+200)-500)abs((2000)-(500+200)) so we ll put 200 in array B. now since B has n/2 elements rest of the element goes to array which is 1. so the ans is A={2000,1} b={500,200} On 15 May 2010 19:10, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: so what will ur algo give for array 1,200,500,2000 On 5/15/10, divya jain sweetdivya@gmail.com wrote: my approach: 1. sort the array 2. take a variable diff. intitialize it to 0. 3. take the 1st element from array nd place it in array A and 2nd element in array B. stoe in diff sum(A)-sum(B). 4. now place the next element in array A or B according to the condition if if sum(A+element)-sum(B) sum(a)-sum(B+element). store the element in B otherwise in A. also while storing the element in ny array maintain the count of element in that aaray. if any time the count reaches n/2 where n is the no. of elements in the given aaray. then store rest element in the other array. 5. repeat step 5 until both array A n B get n/2 elements.. hope my approach is clear and correct. comments are welcomed. On 15 May 2010 08:47, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Choosing a greedy strategy for this would be difficult. For a simple dp you can maintain A[i,total,present] using a recurrence i is the present index of array total is the number of elements reqd in first partition. present is the no of elements already there in first partition. the array stores difference between sums. GET the minimum of all these and backtrack. On 5/15/10, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: @karas: your solution is greedy and its wrong e.g. for {1,2,3,4,5,100} your diff would be 95 but the best result is 91 i think we can solve this problem by dynamic programming but not a simple one! since the size of the two subsets must be equal. so it's DP solution has at least 3 dimensions: tow dimensions representing the number of elements in each subset and another for the difference between their sums On Fri, May 14, 2010 at 10:11 PM, W Karas wka...@yahoo.com wrote: On May 14, 4:51 am, divya sweetdivya@gmail.com wrote: Algorithm to partition set of numbers into two s.t. diff bw their sum is min and they hav equal num of elements void part(const int a[], int n_a, int g1[], int g2[]) { int i, j, k; /* diff = sum(g1) - sum(g2) */ int diff; sort(a, n_a); diff = 0; for (i = 0, j = 1, k = 0; j n_a; ++k, i += 2, j += 2) { if ((a[i] a[j]) == (diff 0)) { g1[k] = a[j]; g2[k] = a[i]; } else { g1[k] = a[i]; g2[k] = a[j]; } diff += g1[k] - g2[k]; } } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%252bunsubscr...@googlegroups.comalgogeeks%25252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- 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 http://www.cse.iitb.ac.in/%7Erohitfeb14 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en
Re: [algogeeks] Re: string question
the output shd be epo.. hint to the problem : PROBLEM DO NOT READ IF U WANT TO SOLVE THE URSELF it involves the concept of finding window u hv to 1st search for the window which contains all characters of string. then u have to alter window so as to get minmum length window.. On 17 May 2010 16:44, Modeling Expert cs.modelingexp...@gmail.com wrote: @Divya BigS = Hellepo What's up SmallS = 'eo' o/p should be ? ellepo OR epo ? if its ellepo DP would work fine . If its eo probably need some modification in DP. -Manish On May 16, 8:36 pm, Navin Naidu navinmna...@gmail.com wrote: @Sharad: yup On Sun, May 16, 2010 at 8:36 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: @Navin: and that works ! :) @all : i am sure no heuristic/greedy strategy can be applied. @divya : did you check your array partitioning algorithm with my example ! -- 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 http://www.cse.iitb.ac.in/%7Erohitfeb14 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, - NMN -- 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 athttp:// 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] string question
output ll be : e's On 16 May 2010 20:17, sharad kumar aryansmit3...@gmail.com wrote: suppose if i give Ssmall:es Sbig:he's a algogeek and he's rocking wat will be o/p? On Sun, May 16, 2010 at 8:12 PM, divya sweetdivya@gmail.com wrote: You r given a large string of characters lets call it Sbig. Then there is a small set of characters lets call it Ssmall. You have to find smallest substring of Sbig which contains all characters in Ssmall. For example you are given Sbig = hello what are you doing Ssmall= eo answer is ello -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: question
Very simple N^2*logN solution: sort the input array, then go through all pairs Ai, Aj (N^2 time), and for each pair check whether (S - Ai - Aj) is in array (logN time). On 12 May 2010 23:08, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: @sateesh suppose after sorting the array is -99,-98,-97,-96,-95,-2,-1,0,4,5,99 the answer should be {-99,0,99}.. sum is closest to zero here so i dnt think the transition method works On Fri, May 7, 2010 at 9:58 PM, sateesh sateeshk...@gmail.com wrote: I think this can be solved in better way. 1) Store the copy of array to get the indexes for the elements at the end of algo 2) Sort the array time: O(nlogn), space: O(1) 3) If first element of array is -ve and last element of array is not - ve, find the element at which -ve to +ve transition happens ex: -a -b +c +d check the absolute minimum of following combinations and pick the correct pair -b+c+d -a+c+d -a-b+c -a-b+d here I assumed two +ve, two -ve. If only one -ve or one +v exists, we can pick the correct 3 elements straight away else if all are -ve numbers , pick last 3 elements else pick first 3 elements This total process takes O(n) time 4) Based on picked three elements, do linear search on copied array to get there indexes. time: O(n) Overall it takes O(nlogn) time complexity and O(n) space complexity. Do you guys find any flaw in it ? -Sateesh IIT Kanpur 2004 M.Tech CSE Batch. On May 4, 10:43 pm, Afroz Mohiuddin afrozena...@gmail.com wrote: Well if you want a sum of exactly 0 (or any constant) , there is an O(N^2) way Take your array, and hash it, note that it is always possible to hash a static set of keys so that the search/find in it is worst case O(1). This takes O(N) space, and time. Then over all the tuples of numbers in the original array (a,b) check if 0 - (a+b) is there in the hash set, time complexity O(N*N). For closest to 0 I guess the above solution is good. On Mon, May 3, 2010 at 2:18 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: given an array(unsorted) may contain negative numbers too find the index of three numbers whose sum is closest to zero in O(N2 log N) time and O(N) space. P.S -3 is more close to zero then -6 (number line ...) -- 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 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- We are here on earth to do good for others. What the others are here for, I don't know. Afroz Mohiuddin Final Year Masters Student Dept Computer Science and Engineering Indian Institute of Technology Kanpur Kanpur - 208016 INDIA -- 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 athttp:// 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] Re: partion of array
my approach: 1. sort the array 2. take a variable diff. intitialize it to 0. 3. take the 1st element from array nd place it in array A and 2nd element in array B. stoe in diff sum(A)-sum(B). 4. now place the next element in array A or B according to the condition if if sum(A+element)-sum(B) sum(a)-sum(B+element). store the element in B otherwise in A. also while storing the element in ny array maintain the count of element in that aaray. if any time the count reaches n/2 where n is the no. of elements in the given aaray. then store rest element in the other array. 5. repeat step 5 until both array A n B get n/2 elements.. hope my approach is clear and correct. comments are welcomed. On 15 May 2010 08:47, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Choosing a greedy strategy for this would be difficult. For a simple dp you can maintain A[i,total,present] using a recurrence i is the present index of array total is the number of elements reqd in first partition. present is the no of elements already there in first partition. the array stores difference between sums. GET the minimum of all these and backtrack. On 5/15/10, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: @karas: your solution is greedy and its wrong e.g. for {1,2,3,4,5,100} your diff would be 95 but the best result is 91 i think we can solve this problem by dynamic programming but not a simple one! since the size of the two subsets must be equal. so it's DP solution has at least 3 dimensions: tow dimensions representing the number of elements in each subset and another for the difference between their sums On Fri, May 14, 2010 at 10:11 PM, W Karas wka...@yahoo.com wrote: On May 14, 4:51 am, divya sweetdivya@gmail.com wrote: Algorithm to partition set of numbers into two s.t. diff bw their sum is min and they hav equal num of elements void part(const int a[], int n_a, int g1[], int g2[]) { int i, j, k; /* diff = sum(g1) - sum(g2) */ int diff; sort(a, n_a); diff = 0; for (i = 0, j = 1, k = 0; j n_a; ++k, i += 2, j += 2) { if ((a[i] a[j]) == (diff 0)) { g1[k] = a[j]; g2[k] = a[i]; } else { g1[k] = a[i]; g2[k] = a[j]; } diff += g1[k] - g2[k]; } } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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. -- -- 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 -- 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] frequency
use binary tree and insert in it every character u come across. if the character is already present then increment its count. use this approach if u r nt sure that characters will be only 26 or no. if u r sure there r 26 char then u cn use hash.. plz correct me if i m wrong. thanks On 14 May 2010 08:50, sharad kumar aryansmit3...@gmail.com wrote: cant u use a hash map of O(K) where K is distinct elements in string.. On Thu, May 13, 2010 at 8:13 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: input a character array from the user and output in the following way. example string is amazon.. then output should be a2m1z1o1n1 i did it taking a 26 size array... some better solution ?? -- 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. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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] compute kth smallest element from union of two lists
sorry bt i dint get the approach. can u please explain a bit more by taking examples...thanks a lot in advance On 14 May 2010 10:12, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: This was also asked in my Yahoo! Interview this year. :) -- 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 Fri, May 14, 2010 at 10:10 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: exactly .. -- 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 Fri, May 14, 2010 at 10:07 AM, vignesh radhakrishnan rvignesh1...@gmail.com wrote: This is for kth largest. Change it for kth smallest In fact, this problem is amenable to something very similar to binary search. Suppose my arrays are A and B. The idea is to keep track of two indices, a (for A) and b (for B), such that a + b = k - 1 (it's very important to maintain this invariant). It's easy to check whether A[a] or B[b] is the answer: A[a] is the answer if and only if B[b-1] = A[a] = B[b], and B[b] is the answer if and only if A[a-1] = B[b] = A[a], where we use the convention that A[-1] = B[-1] = negative infinity. (This can be determined in constant time.) Moreover, if neither of these is the case, you can divide the problem in half: if A[a] B[b-1], you restrict your attention to the portion of A above index a and the portion of B below index b, and otherwise (it must be the case that B[b] A[a-1]), you restrict your attention to the portion of A below index a and the portion of B above index b. (If you start with a and b in the middle of the arrays and always make the new indices be in the middle of the subarrays you're considering at that point, this step will always divide the problem in half.) Thanks to Lux Perpetua http://forums.devshed.com/member.php?u=74699 source: http://forums.devshed.com/software-design-43/finding-kth-largest-element-in-a-union-of-two-arrays-137322.html On 13 May 2010 19:34, divya sweetdivya@gmail.com wrote: You are given two sorted lists of size m and n. Give an O(log m+log n) time algorithm for computing the kth smallest element in the union of the two lists -- 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. -- There are two kinds of people. Those who care for others and The others -- 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] BST
form a sorted array from inorder traversal of tree. now take to pointers one to the beginning of array and other at the end. now check if the sum of element is greater than reqd sum then increment 1st ptr. if their sum is less than reqd sum then decrement 2nd ptr. if their sum is equal to the reqd sum then this is the ans.. hope it will work.. On 13 May 2010 20:11, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: given a bst... find two nodes whose sum is equal to a number k ... in O(n) time and constant space... -- 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] tree from linked list
the best approach to it is to build a balanced tree from bottom to up rather than top to bottom. On 12 May 2010 22:47, divya jain sweetdivya@gmail.com wrote: thanks a lot to all for their replies.. On 9 May 2010 11:23, rahul rai raikra...@gmail.com wrote: can anyone give me links to more educative and active groups like algogeeks On Sun, May 9, 2010 at 2:11 AM, Arun prasath aruntendulkar2...@gmail.com wrote: This does not create a balanced tree but ensures that every element in the tree is accessible by lg(n) time. Time : Complexity O(n) [a...@91blore-srv1 ~]$ cat recursion.c #include stdlib.h #includeunistd.h #include stdio.h #define TEST2 #ifdef TEST1 int arr[] = { 1,2,3,4,5,6,7}; int max_elems = sizeof(arr)/sizeof(arr[0]); #endif #ifdef TEST2 int arr[] = { 1,2,3,4,5}; int max_elems = sizeof(arr)/sizeof(arr[0]); #endif #ifdef TEST3 int arr[] = { 1,2,3,4,5,6,7,8}; int max_elems = sizeof(arr)/sizeof(arr[0]); #endif #define LIST_EMPTY -1 struct tree { int data; struct tree * left,* right; }; struct tree* function( int , int); void print_inorder( struct tree *); int return_next_from_list(void) { static int nxt_elem = 0; if(nxt_elem max_elems) return arr[nxt_elem++]; return LIST_EMPTY;// empty condition } int main() { unsigned int x = max_elems; struct tree* head; while( x (x - 1) ) { x = x (x - 1) ; } head = function(0, x); print_inorder(head); free(head); return 0; } struct tree* function(int mid, int i) { int val = mid + i ; if (val 1) { struct tree * leaf = malloc( sizeof(struct tree) ); leaf-left = leaf-right = NULL; leaf-data = return_next_from_list(); if(leaf-data == LIST_EMPTY) { free(leaf); return NULL; } return leaf; } struct tree *non_leaf = malloc( sizeof(struct tree) ) ; non_leaf-left = function( mid, i/2); non_leaf-data = return_next_from_list(); if (non_leaf-data == LIST_EMPTY) { struct tree *tmp = non_leaf-left; free(non_leaf); return tmp; } non_leaf-right = function( mid+i, i/2); return non_leaf; } void print_inorder( struct tree* root) { struct tree * trav = root; if (!trav) { return; } print_inorder(trav-left); if(trav-left) free(trav-left); printf({%d}, trav-data); print_inorder(trav-right); if(trav-right) free(trav-right); } [a...@91blore-srv1 ~]$ On Sun, May 2, 2010 at 6:38 PM, divya sweetdivya@gmail.com wrote: u are given a sorted lnked list construct a balanced binary search tree from it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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] tree from linked list
thanks a lot to all for their replies.. On 9 May 2010 11:23, rahul rai raikra...@gmail.com wrote: can anyone give me links to more educative and active groups like algogeeks On Sun, May 9, 2010 at 2:11 AM, Arun prasath aruntendulkar2...@gmail.com wrote: This does not create a balanced tree but ensures that every element in the tree is accessible by lg(n) time. Time : Complexity O(n) [a...@91blore-srv1 ~]$ cat recursion.c #include stdlib.h #includeunistd.h #include stdio.h #define TEST2 #ifdef TEST1 int arr[] = { 1,2,3,4,5,6,7}; int max_elems = sizeof(arr)/sizeof(arr[0]); #endif #ifdef TEST2 int arr[] = { 1,2,3,4,5}; int max_elems = sizeof(arr)/sizeof(arr[0]); #endif #ifdef TEST3 int arr[] = { 1,2,3,4,5,6,7,8}; int max_elems = sizeof(arr)/sizeof(arr[0]); #endif #define LIST_EMPTY -1 struct tree { int data; struct tree * left,* right; }; struct tree* function( int , int); void print_inorder( struct tree *); int return_next_from_list(void) { static int nxt_elem = 0; if(nxt_elem max_elems) return arr[nxt_elem++]; return LIST_EMPTY;// empty condition } int main() { unsigned int x = max_elems; struct tree* head; while( x (x - 1) ) { x = x (x - 1) ; } head = function(0, x); print_inorder(head); free(head); return 0; } struct tree* function(int mid, int i) { int val = mid + i ; if (val 1) { struct tree * leaf = malloc( sizeof(struct tree) ); leaf-left = leaf-right = NULL; leaf-data = return_next_from_list(); if(leaf-data == LIST_EMPTY) { free(leaf); return NULL; } return leaf; } struct tree *non_leaf = malloc( sizeof(struct tree) ) ; non_leaf-left = function( mid, i/2); non_leaf-data = return_next_from_list(); if (non_leaf-data == LIST_EMPTY) { struct tree *tmp = non_leaf-left; free(non_leaf); return tmp; } non_leaf-right = function( mid+i, i/2); return non_leaf; } void print_inorder( struct tree* root) { struct tree * trav = root; if (!trav) { return; } print_inorder(trav-left); if(trav-left) free(trav-left); printf({%d}, trav-data); print_inorder(trav-right); if(trav-right) free(trav-right); } [a...@91blore-srv1 ~]$ On Sun, May 2, 2010 at 6:38 PM, divya sweetdivya@gmail.com wrote: u are given a sorted lnked list construct a balanced binary search tree from it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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] 400!
thanx to all 4 the solutions.. On 3 May 2010 18:39, Varun Nagpal varun.nagp...@gmail.com wrote: @Rajesh gave a simple elegant solution. A look at a Linux calculator : you can even calculate 99! = 8.854887824e+5584950 in few seconds. I just looked at the code(its open source right!), which is not so easy to understand in few minutes. Here is the some part of code I extracted from source files: /* Size of the multiple precision values */ #define MP_SIZE 1000 /* Base for numbers */ #define MP_BASE 1 /* Object for a high precision floating point number representation * * x = sign * (MP_BASE^(exponent-1) + MP_BASE^(exponent-2) + ...) */ typedef struct { /* Sign (+1, -1) or 0 for the value zero */ int sign; //, im_sign; /* Exponent (to base MP_BASE) */ int exponent; //, im_exponent; /* Normalized fraction */ int fraction[MP_SIZE]; //, im_fraction[MP_SIZE]; } MPNumber; void mp_factorial(const MPNumber *x, MPNumber *z) { int i, value; /* 0! == 1 */ if (mp_is_zero(x)) { mp_set_from_integer(1, z); return; } if (!mp_is_natural(x)) { /* Translators: Error displayed when attempted take the factorial of a fractional number */ mperr(_(Factorial is only defined for natural numbers)); mp_set_from_integer(0, z); return; } /* Convert to integer - if couldn't be converted then the factorial would be too big anyway */ value = mp_cast_to_int(x); mp_set_from_mp(x, z); for (i = 2; i value; i++) mp_multiply_integer(z, i, z); } mp_multiply_integer(z, i, z) subroutine is too big too put in here, too see its code visit: http://live.gnome.org/Gcalctool http://live.gnome.org/Gcalctool On Mon, May 3, 2010 at 2:34 PM, Anil C R cr.a...@gmail.com wrote: @Jitendra but that's no fun [?] - Anil On Mon, May 3, 2010 at 5:12 PM, vignesh radhakrishnan rvignesh1...@gmail.com wrote: @siddharth and prasoon either design a very long integer library yourself, or use gmp library in cpp or BigInteger Class in java. Regards, vignesh On 3 May 2010 09:46, siddharth srivastava akssps...@gmail.com wrote: But is there any way to accomplish this without an array ? Even for 100!. On 2 May 2010 06:15, Prasoon Mishra prasoonbluel...@gmail.com wrote: I think challenge here is not the Execution time, but the storage. 300 ! or 400! should generally go beyond the storage capabilities of long long ints in cpp. @ Rohit Saraf: Hence, I don't know if even tail recursion will ultimately be able to store the output. I think Rajesh Patidar's answer fits the bill well, in terms of storage. On Sun, May 2, 2010 at 2:23 PM, vignesh radhakrishnan rvignesh1...@gmail.com wrote: I agree with abhijith. But given some very large x for which i would have to find factorial. I would either (i) use gmp in cpp or BigInteger or java if its not a lab exercise or an interview (ii) use simple brute multiplication algorithm. The second approach requires (a) The no. of digits in n! for making storage available (b) The calculation itself which I would brute force References: http://inder-gnu.blogspot.com/2009/08/find-number-of-digits-in-factorial-of.html http://stackoverflow.com/questions/1113167/can-one-know-how-large-a-factorial-would-be-before-calculating-it http://delphiforfun.org/programs/big_factorials.htm On 2 May 2010 13:59, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: google it... u will gt it i am on mobile... cannot explain now.. On 5/2/10, divya jain sweetdivya@gmail.com wrote: wat is tail recursion plz explan in detail On 2 May 2010 08:15, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @divya use tail recursion and rest should be fine.. -- -- 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 http://www.cse.iitb.ac.in/%7Erohitfeb14 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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
Re: [algogeeks] 400!
nice algo by rajesh. bt i think using linked list will be better.. On 3 May 2010 09:46, siddharth srivastava akssps...@gmail.com wrote: But is there any way to accomplish this without an array ? Even for 100!. On 2 May 2010 06:15, Prasoon Mishra prasoonbluel...@gmail.com wrote: I think challenge here is not the Execution time, but the storage. 300 ! or 400! should generally go beyond the storage capabilities of long long ints in cpp. @ Rohit Saraf: Hence, I don't know if even tail recursion will ultimately be able to store the output. I think Rajesh Patidar's answer fits the bill well, in terms of storage. On Sun, May 2, 2010 at 2:23 PM, vignesh radhakrishnan rvignesh1...@gmail.com wrote: I agree with abhijith. But given some very large x for which i would have to find factorial. I would either (i) use gmp in cpp or BigInteger or java if its not a lab exercise or an interview (ii) use simple brute multiplication algorithm. The second approach requires (a) The no. of digits in n! for making storage available (b) The calculation itself which I would brute force References: http://inder-gnu.blogspot.com/2009/08/find-number-of-digits-in-factorial-of.html http://stackoverflow.com/questions/1113167/can-one-know-how-large-a-factorial-would-be-before-calculating-it http://delphiforfun.org/programs/big_factorials.htm On 2 May 2010 13:59, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: google it... u will gt it i am on mobile... cannot explain now.. On 5/2/10, divya jain sweetdivya@gmail.com wrote: wat is tail recursion plz explan in detail On 2 May 2010 08:15, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @divya use tail recursion and rest should be fine.. -- -- 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 http://www.cse.iitb.ac.in/%7Erohitfeb14 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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. -- -- 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 -- 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. -- There are two kinds of people. Those who care for others and The others -- 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. -- Siddharth Srivastava Human Knowledge is for all -- 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
Re: [algogeeks] Re: a google question
@satish ur solution is of o(nlogn) complexty @ jitendra suppose p11 and p21 r pointing at index 0 and p12 at 4 and p22 at 1. now suppose at ths point d s greater than b and c. now u increment p11 and p21. but it can be a case that a[0] + b[2] is next greatest value bt t wont work for ur algo. On 3 May 2010 00:46, Shishir Mittal 1987.shis...@gmail.com wrote: @Algoose : No, it is not necessary that first n elements must contain A[0] or B[0]. For e.g. A = {40,30,15,10} B = {40,30,15,10} Required 4 largest values = {40+40, 40+30, 40+30, 30+30}. @Satish: A very nice algorithm provided by you. Complexity Analysis for the algorithm provided by you: Creation of max-heap of n elements = O(n). Time to add a new element to the heap after extracting the maximum - O(log n) Overall Complexity = O(n log n) Regards, Shishir On Sun, May 2, 2010 at 10:52 PM, Satish satish.mit...@gmail.com wrote: This problem can be simplified to a variation of merge part of merge sort algorithm. - Break the set S having n^2 values into n individual arrays of length n, say S1, S2,..Sn, where S1 = [a1+b1, a1+b2,...a1+bn]. - One can observe that each Si has entries which are themselves sorted within Si. - Perform merge of S1, S2,..Sn where take the largest values of each Si, and create a heap of these individual max values. - In each step, return the max value from heap and then add the next max value from the Si that had the current max value and add it in the max-heap. - Repeat this step n times and then exit. Time: O(n). Satish On May 2, 5:41 pm, Algoose Chase harishp...@gmail.com wrote: Hi will this work ? since we need Set S with n pairs of largest values , any such pair within the set would (always) contain A[0] or B[0] because they maximize the value of the pair. so // code snippet typedef std::vectorint,int Pairs; Pairs.push(A[0],B[0]) int i = 1; // index for ListA int j = 1; // index for list B count = 1; while( count = n) { if( A[0] + B[j] B[0] + A[i] ) { Pairs.push(A[0],B[j]) j++; } else { Pairs.Add(A[i],B[0]) i++; } count++; } since there are n items in both the lists, j and i wont go beyond n in the while loop -- 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] 400!
wat is tail recursion plz explan in detail On 2 May 2010 08:15, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @divya use tail recursion and rest should be fine.. -- -- 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 -- 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] a google question
i found this question on some site and it was mentioned there todo in o(n). i dont have the solution @ above ur solution doesnt include the case of ncluding a[i] b[j] it takes only a[i] b[0] or b[j] a[0] On 2 May 2010 18:11, Algoose Chase harishp...@gmail.com wrote: Hi will this work ? since we need Set S with n pairs of largest values , any such pair within the set would (always) contain A[0] or B[0] because they maximize the value of the pair. so // code snippet typedef std::vectorint,int Pairs; Pairs.push(A[0],B[0]) int i = 1; // index for ListA int j = 1; // index for list B count = 1; while( count = n) { if( A[0] + B[j] B[0] + A[i] ) { Pairs.push(A[0],B[j]) j++; } else { Pairs.Add(A[i],B[0]) i++; } count++; } since there are n items in both the lists, j and i wont go beyond n in the while loop On Sun, May 2, 2010 at 3:44 PM, Shishir Mittal 1987.shis...@gmail.comwrote: This problem has been discussed before @ http://groups.google.co.in/group/algogeeks/browse_thread/thread/9c1e1aa8cf1ed437/d451cd9468d985f7 I believe, the problem can't be solved in O(n) but only in O(nlog n). @Divya: Are you sure the interviewer explicitly asked for an O(n) time algorithm? On Sun, May 2, 2010 at 1:48 PM, vignesh radhakrishnan rvignesh1...@gmail.com wrote: @divya You're rite. Post a solution if you have one. -- Regards, Vignesh On 2 May 2010 13:14, divya jain sweetdivya@gmail.com wrote: @Mohit according to ur algo if a[1], b[0] has sum greater than a[0],b[1] then i is incremented i is now 2 so for next iteration u ll compare a[2] b[0] and a[1] b1]. but what about a[0] b[1] this pair s lost forever. think for ths case also. On 2 May 2010 11:22, mohit ranjan shoonya.mo...@gmail.com wrote: @Algoose Chase point taken Thanks Mohit Ranjan Samsung India Software Operations. On Sat, May 1, 2010 at 8:43 PM, Algoose Chase harishp...@gmail.comwrote: @mohit The idea of DP is fine. When you find the Max i dont think you need to include A[i+1]+B[j+1] because it can never be greater than both A[i+1]+B[j] and A[i]+B[j+1] since both the lists are sorted in decreasing order. On Fri, Apr 30, 2010 at 8:47 PM, mohit ranjan shoonya.mo...@gmail.com wrote: oops Sorry didn't read properly last algo was for array sorted in ascending order for this case, just reverse the process A[n] and B[n] are two array loop=n, i=0, j=0; while(loop0) // for n largest pairs { print A[i]+B[j]; // sum of first index from both array will be max foo = MAX ( A[i+1]+B[j], A[i+1]+B[j+1], A[i]+B[j+1] ) // using DP, moving forward if foo==A[i+1]+B[j]; i++ // only increment A if foo==A[i+1]+B[j+1]; i++; j++ // increment both A and B if foo==A[i]+B[j+1]; j++ // increment only B } Mohit Ranjan Samsung India Software Operations. On Fri, Apr 30, 2010 at 8:40 PM, mohit ranjan shoonya.mo...@gmail.com wrote: Hi Divya, A[n] and B[n] are two array loop=n, i=n-1, j=n-1; while(loop0) // for n largest pairs { print A[i]+B[j]; // sum of last index from both array will be max foo = MAX ( A[i-1]+B[j], A[i-1]+B[j-1], A[i]+B[j-1] ) // using DP moving backward if foo=A[i-1]+B[j]; i-- // only reduce A if foo=A[i-1]+B[j-1]; i--; j-- // reduce both A and B if foo=A[i]+B[j-1]; j-- // reduce only B } Time: O(n) Mohit Ranjan On Fri, Apr 30, 2010 at 5:35 PM, divya sweetdivya@gmail.comwrote: Given two sorted postive integer arrays A(n) and B(n) (W.L.O.G, let's say they are decreasingly sorted), we define a set S = {(a,b) | a \in A and b \in B}. Obviously there are n^2 elements in S. The value of such a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs from S with largest values. The tricky part is that we need an O(n) algorithm. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options