[algogeeks] Re: do this: two numbers with min diff
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
.
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
@ 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
[algogeeks] Re: do this: two numbers with min diff
May be this helps
http://ds-gyan.blogspot.com/2009/12/two-numbers-with-minimum-difference.html
On Sep 28, 10:28 am, coolfrog$ dixit.coolfrog.div...@gmail.com
wrote:
@ 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...@googleg
roups.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
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.
[algogeeks] Re: do this: two numbers with min diff
check for this input {7,8,5,1,3,4}
On Sep 23, 10: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;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm 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: do this: two numbers with min diff
I got the problem statement wrong. For a input of 7,8,5,1,3,4 the answer should be 1 due to the difference between 3 and 4 or 7 and 8 or 4 and 5. Rather than 2 due to difference between 1 and 3 Sorry every one :-( -- You received this message because you are subscribed to the Google Groups Algorithm 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.
[algogeeks] Re: do this: two numbers with min diff
You are solving the wrong problem. The problem is not asking for the
difference between the two minimum elements, but for the minimum
difference between any pair of elements. In the case
int array[10]={99,35,45,33,88,9098,112,33455,678,3};
the minimum difference is |35-33| = 2.
Dave
On Sep 24, 5:02 am, Rishi Agrawal rishi.b.agra...@gmail.com wrote:
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- 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: do this: two numbers with min diff
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.
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.
[algogeeks] Re: do this: two numbers with min diff
try for this {100,6,101,11}
On Sep 23, 7:40 pm, Nishant Agarwal nishant.agarwa...@gmail.com
wrote:
int minDiff(int arr[], int arr_size)
{
int min_diff = arr[1] - arr[0];
int max_element = arr[0];
int i;
for(i = 1; i arr_size; i++)
{
if(arr[i] - max_element min_diff)
min_diff = arr[i] - max_element;
if(arr[i] max_element)
max_element = arr[i];
}
return min_diff;
}
On Mon, Sep 20, 2010 at 10:38 AM, Srinivas
lavudyasrinivas0...@gmail.comwrote:
2 nos with min diff
given an array of size n. find 2 numbers from array whose difference
is least in O(n) w/o
using xtra space( i mean constant 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.
--
:-)
*
Nishant Agarwal
Computer Science and Engineering
NIT Allahabad
*- 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.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.
[algogeeks] Re: do this: two numbers with min diff
@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.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.
[algogeeks] Re: do this: two numbers with min diff
Your comment brings to mind that we could do an O(n) sort such as a
Radix Sort. Any ordinary implementation will be O(n) as a fixed number
of passes will be required based on the word size.
Dave
On Sep 23, 11:21 am, nishaanth nishaant...@gmail.com wrote:
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.- 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.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.
[algogeeks] Re: do this: two numbers with min diff
@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.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.
