Re: [algogeeks] Re: do this: two numbers with min diff
@ sorurav yes , the basic logic is required so that the code can be understood in single Run.. i also request the same to all dear friends. Regards.. On Tue, Sep 28, 2010 at 8:11 PM, sourav souravs...@gmail.com wrote: Hi Friends This is an interesting problem and request you all to give a brief intro to your code before putting the code. Or you may just mention the under lying concept in the code. This will be of great help and others will find it more ready to improve by adding there approach. Coming back to the problem an O(n) solution can exist by following the approach of building a min heap (or max heap) from an array of elements. A mean heap from an array of elements can be built by starting from middle element (all elements from mid +1 to end are them selves single element min heaps) (references available in Cormen or other books). During constructing the mean heap always track the min difference between any two elements in the so far constructed heap. At any instant if you are handling root 'a' which has left child l and right child r and aiming to build a min heap rooted at a, then the following cases arise 1. a is less than both l and r. In this case no movement of a is required. Now find |a-l| = x and |a-r| = y. 'a' cannot have a difference z with any element under tree rooted at l such that z x becuase l is the least element in the tree rooted at l. Similarly 'a' cannot have a difference z' with any element under tree rooted at r such that z' r. So least of x and y is the min diff between any elements in the so far constructed min heap rooted at 'a'. 2. a is less than l but greater than r. In this case r will replace a and a need to be pushed down the its right child. While pushing 'a' down keep calculating the differences between 'a' and 'r' as long as 'a' is not pushed down to a node where it is the min element. While you keep calculating also keep track of the min diff calculated so far (say 'p'). Compare this 'p' with |a-l| and min diff between any two elements for the tree rooted at l. Least of these three will be the min diff between any 2 elements for the min head rooted at 'r' (which replaced 'a''s position. 3. Both 'l' and 'r' are less than 'a'. Take the lesser or 'l' and 'r' and replace that with 'a' and push 'a' down as in case 2 (normal min heap construction algo). Thus we can continue building the min heap and at the end have the min diff between any 2 elements in the array. Just we keep tracking the min diff, we can also keep note of the 2 elements than are contributing to this min diff my adding some more steps. This idea is all based on the fact that min heap can be constructed from an array in linear time. Thanks, Sourav On Sep 27, 1:32 pm, rahul rahulr...@gmail.com wrote: If their is no constrain on assumptions. 1.Sort the array. 2. check the dif between 2 elements. { 99,35,45,33,88,9098,112,33455,678,3} sorted arrary : { } would be something. now update the min_diff. another example : { 7,8,1,3,5,4} sorted arrary : { 1,3,4,5,7,8} min diff is 1. Please correct me if i missed something. On Mon, Sep 27, 2010 at 1:13 PM, satish satish@gmail.com wrote: step1construct heap using siftdown. // time complexity wil be O(n) and space complexity O(1). step2take mindifference=a[1]. step3for i=1 ,i=n/2 do { find the difference of (root,root-left),(root,root-right)and (root-left,root-right).and maintain mindifference is the smallest difference of among three differences. } step4return mindifference. plz correct me if im wrong -- You received this message because you are subscribed to the Google Groups Algorithm 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. -- *Divesh* (¨`·.·´¨) Always `·.¸(¨`·.·´¨ ) Keep (¨`·.·´¨)¸.·´Smiling! `·.¸.·´ Life can give u 100's of reason 2cry,but u can give life 1000's of reasons 2Smile -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to
Re: [algogeeks] Re: do this: two numbers with min diff
step1construct heap using siftdown. // time complexity wil be O(n) and space complexity O(1). step2take mindifference=a[1]. step3for i=1 ,i=n/2 do { find the difference of (root,root-left),(root,root-right)and (root-left,root-right).and maintain mindifference is the smallest difference of among three differences. } step4return mindifference. plz correct me if im wrong -- You received this message because you are subscribed to the Google Groups Algorithm 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: do this: two numbers with min diff
If their is no constrain on assumptions. 1.Sort the array. 2. check the dif between 2 elements. { 99,35,45,33,88,9098,112,33455,678,3} sorted arrary : { } would be something. now update the min_diff. another example : { 7,8,1,3,5,4} sorted arrary : { 1,3,4,5,7,8} min diff is 1. Please correct me if i missed something. On Mon, Sep 27, 2010 at 1:13 PM, satish satish@gmail.com wrote: step1construct heap using siftdown. // time complexity wil be O(n) and space complexity O(1). step2take mindifference=a[1]. step3for i=1 ,i=n/2 do { find the difference of (root,root-left),(root,root-right)and (root-left,root-right).and maintain mindifference is the smallest difference of among three differences. } step4return mindifference. plz correct me if im wrong -- You received this message because you are subscribed to the Google Groups Algorithm 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: do this: two numbers with min diff
Printing the Array: 99 35 45 33 88 9098 112 33455 678 3 Min elements are 1: 3 2: 33 Absolute difference between two minimum elements are 30 On Fri, Sep 24, 2010 at 9:39 AM, Dave dave_and_da...@juno.com wrote: @Rishi: Try it on the original data with a[1] changed from 12 to 35: int array[10]={99,35,45,33,88,9098,112,33455,678,3}; What do you get as a result? Dave On Sep 23, 12:36 pm, Rishi Agrawal rishi.b.agra...@gmail.com wrote: @Dave, I check for the values you suggested but the code worked fine. There were other errors in the code. I have rectified them now. The following code seems to be working fine and in O(n) time. #include stdio.h #include stdlib.h void find_two_mins(int array[], int size) { int i,t; int min1, min2; if(array[0] = array[1]) { min1=array[0]; min2=array[1]; } else { min2=array[0]; min1=array[1]; } for (i=2; isize; i++){ t=array[i]; if(t=min1) { min2=min1; min1=t; continue; } if(t=min2) { min2=t; } } printf(\nMin elements are 1: %d 2: %d, min1,min2); printf(\n Absolute difference between two minimum elements are %d\n\n, abs(min1-min2)); } int main() { //int array[10]={ 9,2,3,4,1,7,5,6,8,0}; // //int array[10]={3,3,1,33,88,9098,112,33455,678,1}; //int array[10]={5,3,1,33,88,9098,112,33455,678,1}; //int array[10]={2,3,21,33,88,9098,112,33455,678,12}; int array[10]={3,2,21,33,88,9098,112,33455,678,12}; find_two_mins(array,10); return 0; }- 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. -- Regards, Rishi Agrawal -- You received this message because you are subscribed to the Google Groups Algorithm 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: do this: two numbers with min diff
Modeling Expert 's code is greedyit won't work for the test cases in which the optimal answer is does not lie between first two numbers.. On 9/23/10, Srinivas lavudyasrinivas0...@gmail.com wrote: can anyone post this answer pls?? -- You received this message because you are subscribed to the Google Groups Algorithm 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: do this: two numbers with min diff
I hope this will work. It finds the two minimum numbers and then prints the difference. #include stdio.h #include stdlib.h void find_two_mins(int array[], int size) { int i,t; int min1=array[0], min2=array[1]; for (i=2; isize; i++){ t=array[i]; if(t=min1) { min2=min1; min1=t; continue; } } printf(\nMin elements are 1: %d 2: %d, min1,min2); printf(\n Absolute difference between two minimum elements are %d, abs(min1-min2)); } int main() { //int array[10]={ 9,2,3,4,1,7,5,6,8,0}; // int array[10]={99,12,45,33,88,9098,112,33455,678,3}; find_two_mins(array,10); 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: do this: two numbers with min diff
i dont think there exists a o(n) solution for this the best we can do is sort in o(nlogn) and then do a o(n) traversal On Thu, Sep 23, 2010 at 8:48 PM, Dave dave_and_da...@juno.com wrote: @Yellow: Change the 12 in a[1] in your test case to 35 and see what you get. Dave On Sep 23, 10:09 am, Yellow Sapphire pukhraj7...@gmail.com wrote: I hope this will work. It finds the two minimum numbers and then prints the difference. #include stdio.h #include stdlib.h void find_two_mins(int array[], int size) { int i,t; int min1=array[0], min2=array[1]; for (i=2; isize; i++){ t=array[i]; if(t=min1) { min2=min1; min1=t; continue; } } printf(\nMin elements are 1: %d 2: %d, min1,min2); printf(\n Absolute difference between two minimum elements are %d, abs(min1-min2)); } int main() { //int array[10]={ 9,2,3,4,1,7,5,6,8,0}; // int array[10]={99,12,45,33,88,9098,112,33455,678,3}; find_two_mins(array,10); return 0; }- 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. -- 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 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: do this: two numbers with min diff
@Dave, I check for the values you suggested but the code worked fine. There were other errors in the code. I have rectified them now. The following code seems to be working fine and in O(n) time. #include stdio.h #include stdlib.h void find_two_mins(int array[], int size) { int i,t; int min1, min2; if(array[0] = array[1]) { min1=array[0]; min2=array[1]; } else { min2=array[0]; min1=array[1]; } for (i=2; isize; i++){ t=array[i]; if(t=min1) { min2=min1; min1=t; continue; } if(t=min2) { min2=t; } } printf(\nMin elements are 1: %d 2: %d, min1,min2); printf(\n Absolute difference between two minimum elements are %d\n\n, abs(min1-min2)); } int main() { //int array[10]={ 9,2,3,4,1,7,5,6,8,0}; // //int array[10]={3,3,1,33,88,9098,112,33455,678,1}; //int array[10]={5,3,1,33,88,9098,112,33455,678,1}; //int array[10]={2,3,21,33,88,9098,112,33455,678,12}; int array[10]={3,2,21,33,88,9098,112,33455,678,12}; find_two_mins(array,10); 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: do this: two numbers with min diff
Guyswe need to find two numbers in a array with minimum difference ah On Tue, Sep 21, 2010 at 8:52 PM, Rahul Singal rahulsinga...@gmail.comwrote: try running it on [ 11 , 6 , 100, 101] -- You received this message because you are subscribed to the Google Groups Algorithm 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.