[algogeeks] Re: printing without loop
Using GOTO and loops it the same, cause loops are expanded to GOTO/JMP statements. Doing it just with recursion is interesting. Try sorting number without using loops or goto. Here is the complete problem. Take in n numbers as input and sort them, without using dowhile, while, for or goto. No hash defines either. Try to write the shortest such code. short in character count. You can get a very nice solution.. will post the answer in 24 hrs.. try till then \o/ On Mar 1, 4:47 pm, gaurav gupta 1989.gau...@googlemail.com wrote: @bittu please read the thread carefully. It was mentioned not to use GOTO statement. On Tue, Mar 1, 2011 at 5:13 PM, bittu shashank7andr...@gmail.com wrote: here we go void main() { int i; i=1; loop: printf(%d, i) (i100)? i++: return 0; go to loop; } Thanks Regards Shashank Mani The Best Way to Escape From The Problem is to Solve it -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, Gaurav Gupta 7676-999-350 Quality is never an accident. It is always result of intelligent effort - John Ruskin -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: how would you find the integer pairs which sum to m in o(n) time complexity
On Nov 14, 10:58 pm, bittu shashank7andr...@gmail.com wrote: ya much works is done by above candidate. i would like to say..use 2 ptrs one from beginning another from end take sum=a[start]+a[end]; find if sumnum end-- else if sumnum start++; else //sum==num found; time compexcity O(n) sizeof array space compexcity O(1) This only works when we have sorted arrays. The state of array is not known. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: tree Samsung Question
Since its a data structure, we need to root the tree. Plus my suggestion will only work for directed trees. all children point to their parents. for a node i, if its parent is j a[i]=j a[root] = -1 this can store a tree pretty fast. else normally we can use a linked list etc. On Nov 14, 11:53 pm, bittu shashank7andr...@gmail.com wrote: which data structure is best used to implmets the tree Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: how would you find the integer pairs which sum to m in o(n) time complexity
On Oct 27, 8:21 am, MOHIT mohit...@gmail.com wrote: @ruturaj : but for that hash table you have to know range?? Nope we dont need the range. #includemap map int, int hash; for(int i=0;in;i++) if(hash[m-a[i]] 0)count++;hash[a[i]]++; does the trick. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: modified divide and conquer
Yes, its a quite an interesting problem and solved using parallel programming many times. I think the idea , as Ercan thought of, is to do a binary search. Consider 2 arrays A and B. Divide both arrays into logn sizes blocks. For each block let the first element be the head element. Now cross find the location of one head into another. that is find the position of a head at i in array A in array b, if this position is j, then we can say that the net position is i+j. So in an array of size |a| + |b| we can have these heads stored. This takes logn*logn time. now the matter remains of merging the values inbetween these heads. there are logn such elements between each two consecutive heads. It can be proved that there are atmost 2logn elements in between 2 heads and if we can merge them parallel, we will take 2logn time totally. Actually we can find the exact location of an element i of A in B as j, and this j acts as an additional marker. I hope you got the idea, things can be worked out a little more clearly. On Nov 9, 12:34 am, Gönenç Ercan gon...@gmail.com wrote: Ok I see your point, I thought that it asked to provide an algorithm with overall complexity O(logn), which is not possible. why not use a binary search like procedure to fix the worst case. Choose the array lets say list L with the bigger number, then instead of checking each element of smaller list S one by one, execute binary search in S for the number in L_1. This will find the index of items smaller than L_1, insert them to the merged array, and L_1. repeat this untill all elements are processed. While this involves a single item only O(logn) times, the overal complexity of merge is still O(n) because the items should be copied in any case. On Nov 8, 12:01 pm, Terence technic@gmail.com wrote: No. It is possible. This problem focuses on comparisons of each element. The overall time complexity of merge operation can be as high as O(nlogn), while the normal merge operation has time complexity O(n). But the normal merge operation does not meet the requirement, since in the worst case, (the largest number in one sequence is smaller than the smallest of the other), one element can be included in n comparisons at most. On 2010-11-8 17:00, G nen Ercan wrote: does not seem possible, there is a proof that shows that comparison based algorithm can have at best O(nlogn) worst case running time. You can check this proof from algorithms CLRS book. Using this proof, by master's theorem if the merge operation can be implemented in O(lgn) using merge sort with this merge operation, the complexity would be O(logn) contradicting with O(nlogn). So I think its not possible to design such merge algorithm. On Nov 8, 4:58 am, lichenga2404lichenga2...@gmail.com wrote: Suppose we'd like to implement a sorting variant where every element is compared only a small number of times. a) devise a divide and conquer algorithm to merge 2 sorted arrays of length n , which guarantees that every element is included in at most O(log n ) comparisons. b) using this modified merge , prove that Merge-Sort will include element in at most O( (log n)^2) comparisons. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Directi question-centre of the tree
I am thinking on these lines. Start from any node. DFS to the fartheset node from there. let the farthest node be B. Start a new DFS from B to reach the fartheset node from B , let that be C. It can be proved that BC is the longest path in the tree. Then, the node in the center will be the answer to the question. Incase the path length is even we will have two nodes. I havent proved it yet, the second part of my solution. this was a quick thought. On Sep 29, 9:41 pm, jayapriya surendran priya7...@gmail.com wrote: In graph theory, a tree is defined as a graph on N nodes,and (N-1) un-directed edges such that there are no cycles in the graph.Each node has a single unique path to every other node. Let D(u,v) be the number of edges in the unique path from node 'u' to node 'v' (or from node 'v' to 'u' since the edges are un-directed).D(u,u) is 0 for all nodes 'u'. M(u)=MAX(D(u,i):for all nodes i) The center of a tree is the node (or nodes) 'u',for which M(u) is minimum among all the nodes in the graph. You'll be given a graph which has N nodes (1=N=20).The nodes are labeled 1,2,3,..N.You will be provided with N-1 edges in the form of a b pairs where 1=a,b=N.No edge will be repeated.You can assume that the edges are specified such that the graph is a valid tree as defined above. Output the node labels of the center(or centers) of the tree. Sample Input: 6(value of N) 1 3 (edges) 1 4 1 2 2 5 2 6 Sample Output 1 2 Expected:O(N) complexity algo can anyone plz help me out with O(N) algo? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Take 5 digit number and find 2 power that number.............
a 5 digit number is of order 10^5 which is 10^16 of which int in C is of size. Just multiply both numbers. On Sep 2, 10:39 am, prasad rao prasadg...@gmail.com wrote: Program that takes a 5 digit number and calculates 2 power that number and prints it and should not use the Big-integer and Exponential Function's. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.