Author |
Topic: Find the minimum difference betwen two numbers (Read 10746 times) |
|
birbal
Full Member
Gender: 
Posts: 250
|
 |
Re: Find the minimum difference betwen two numbers
« Reply #25 on: Mar 16th, 2011, 11:28am » |
 Quote  Modify
|
on Mar 16th, 2011, 8:07am, Grimbal wrote:Are you sure it was not between 2 sorted arrays?
i.e. find min of |A[i]-B[j]| over all i,j.
That can be done in O(n).
|
|
Ya i'm pretty sure. I read it in interview quesions. Perhaps they ask such things just so see how ppl deal with them.
|
|
 IP Logged |
The only thing we have to fear is fear itself!
|
|
|
resim
Newbie
Gender:
Posts: 1
|
|
Re: Find the minimum difference betwen two numbers
« Reply #26 on: Jan 22nd, 2012, 2:15am » |
Quote Modify
|
Thanks..
|
|
IP Logged |
|
|
|
David Flower
Newbie
Gender:
Posts: 1
|
|
Re: Find the minimum difference betwen two numbers
« Reply #27 on: Apr 13th, 2012, 8:41am » |
Quote Modify
|
It seems like a difficult factor to do if the range weren't categorized, so I'd believe that's a precondition.
|
|
IP Logged |
|
|
|
deepaknasa
Newbie
Posts: 1
|
|
Re: Find the minimum difference betwen two numbers
« Reply #28 on: Jun 14th, 2012, 4:03am » |
Quote Modify
|
proxmap sorting can sort array in O(n) complexity.
cs.uah.edu/~rcoleman/CS221/Sorting/ProxMapSort.html
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Find the minimum difference betwen two numbers
« Reply #29 on: Jun 14th, 2012, 7:15am » |
Quote Modify
|
Proxmap is O(n2) in the worst case. (Because it's insertion sort in the worst case.)
Nice to learn about a new (to me) sorting technique, though.
|
| « Last Edit: Jun 14th, 2012, 7:16am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Find the minimum difference betwen two numbers
« Reply #30 on: Jun 21st, 2012, 1:21pm » |
Quote Modify
|
Element distinctness problem has proven Omega(n logn) lower bounds in the algebraic decision tree model.
Of course, hashing/radix sort etc don't fall in that, so we still might have some linear time algorithm...
|
|
IP Logged |
|
|
|
Saravana
Newbie
Gender:
Posts: 2
|
|
Re: Find the minimum difference betwen two numbers
« Reply #31 on: Jun 30th, 2012, 1:44am » |
Quote Modify
|
a[]={1,4,8,7,10}
var1=a[0],var2=a[1]
diff= |var1-var2|
for( i=2;i<n;i++)
{
if( |var1-a[i] | < diff )
{
var2=a[i]
diff = var1-var2;
}
if( |var2-a[i] | < diff )
{
var1 =a[i];
diff = var1-var2;
}
}
atlast the diff will have minimum difference
it is 0(n) soln
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Find the minimum difference betwen two numbers
« Reply #32 on: Jun 30th, 2012, 2:20am » |
Quote Modify
|
Have you tried running your code? Because it gives the answer 3, whereas the minimum difference is in fact 1.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print