Re: [algogeeks] Re: do this: two numbers with min diff

2010-09-28 Thread coolfrog$
@ 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

2010-09-27 Thread satish
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

2010-09-27 Thread rahul
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

2010-09-24 Thread Rishi Agrawal
 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

2010-09-23 Thread Soundar
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

2010-09-23 Thread Yellow Sapphire
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

2010-09-23 Thread nishaanth
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

2010-09-23 Thread Rishi Agrawal
@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

2010-09-21 Thread LG JAYARAM .
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.