Author |
Topic: Find the minimum difference betwen two numbers (Read 10778 times) |
|
spirit
Newbie
Posts: 11
|
 |
Find the minimum difference betwen two numbers
« on: Jun 18th, 2007, 9:33am » |
 Quote  Modify
|
there is a given array.we have to find the minimum difference between two numbers of the array in o(n) complexity.
E.g. 1 5 10 34 45 56 57
the answer would be 1(57-56=1)
|
|
 IP Logged |
|
|
|
A
Full Member
Perder todas as esperanças é liberdade!
Gender: 
Posts: 236
|
|
Re: Find the minimum difference betwen two numbers
« Reply #1 on: Jun 18th, 2007, 9:35am » |
Quote Modify
|
Atleast in the Given Example , The Input Looks like sorted one , So you Just Need to Compare the Adjacent numbers 
Am i missing something ?
|
|
IP Logged |
What Doesn't Kill Me Will Only Make Me Stronger
|
|
|
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 #2 on: Jun 18th, 2007, 9:47am » |
Quote Modify
|
It seems like a hard thing to do if the array weren't sorted, so I'd assume that's a precondition.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
andyv
Newbie
Posts: 14
|
|
Re: Find the minimum difference betwen two numbers
« Reply #3 on: Jun 18th, 2007, 10:21am » |
Quote Modify
|
sort the array with radix sort (linear time). Then compare the differences of adiacent elements
|
|
IP Logged |
|
|
|
spirit
Newbie
Posts: 11
|
|
Re: Find the minimum difference betwen two numbers
« Reply #4 on: Jun 18th, 2007, 10:13pm » |
Quote Modify
|
no the numbers are not sorted ,it just the case that in the example given they are sorted .. 
|
|
IP Logged |
|
|
|
spirit
Newbie
Posts: 11
|
|
Re: Find the minimum difference betwen two numbers
« Reply #5 on: Jun 18th, 2007, 10:16pm » |
Quote Modify
|
on Jun 18th, 2007, 10:21am, andyv wrote:| sort the array with radix sort (linear time). Then compare the differences of adiacent elements |
|
range of number is not given so the radix sort will not do the trick here..
|
|
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 #6 on: Jun 19th, 2007, 1:17am » |
Quote Modify
|
And I don't suppose you mean the different between two consecutive numbers either?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
spirit
Newbie
Posts: 11
|
|
Re: Find the minimum difference betwen two numbers
« Reply #7 on: Jun 19th, 2007, 2:08am » |
Quote Modify
|
no but if the numbers are sorted then the minimum difference would obviously be between the consecutive numbers
|
|
IP Logged |
|
|
|
andyv
Newbie
Posts: 14
|
|
Re: Find the minimum difference betwen two numbers
« Reply #8 on: Jun 19th, 2007, 3:05am » |
Quote Modify
|
on Jun 18th, 2007, 10:16pm, spirit wrote:
range of number is not given so the radix sort will not do the trick here..
|
|
Radix sort can be used even if we don't know the range.
|
| « Last Edit: Jun 19th, 2007, 3:06am by andyv » |
IP Logged |
|
|
|
spirit
Newbie
Posts: 11
|
|
Re: Find the minimum difference betwen two numbers
« Reply #9 on: Jun 19th, 2007, 3:30am » |
Quote Modify
|
but what about the space complexity ?
|
| « Last Edit: Jun 19th, 2007, 3:35am by spirit » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Find the minimum difference betwen two numbers
« Reply #10 on: Jun 19th, 2007, 9:26am » |
Quote Modify
|
on Jun 18th, 2007, 10:16pm, spirit wrote:
range of number is not given so the radix sort will not do the trick here..
|
|
Just find max and min. max - min gives us a range to work with...
|
|
IP Logged |
|
|
|
spirit
Newbie
Posts: 11
|
|
Re: Find the minimum difference betwen two numbers
« Reply #11 on: Jun 20th, 2007, 4:12am » |
Quote Modify
|
just applying radix sort will not ensure o(n) complexity .. the complexity of radix sort is o(d(n+k))
where d=numbers of digits,k= numbers of values that can take in any digit.
consider tha case where the digits are two large(means value od d is too large ).
In that complexity would be better by nlogn only in the case if d<logn.
so it would not give us o(n) every time.Consider the case n=100 and d=50 in that case radix sort will not work.usually we apply radix sort in those cases where d is small.so applying radix sort will not give the general solution
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Find the minimum difference betwen two numbers
« Reply #12 on: Jun 20th, 2007, 11:20am » |
Quote Modify
|
Let R = max-min
Then we must have that at least 2 numbers are within R/(N-1) of each other. Perhaps we can make use of that.
|
| « Last Edit: Jun 20th, 2007, 11:21am by Aryabhatta » |
IP Logged |
|
|
|
sumantbhardvaj
Newbie
Posts: 20
|
|
Re: Find the minimum difference betwen two numbers
« Reply #13 on: Jun 26th, 2007, 4:34am » |
Quote Modify
|
Can't we do this problem in the following manner irrespective of the fact the array is sorted or not ??
Step 1 : Find the maximum number in the array. It can
be done in O(n)
Step 2: Find the next Maximum number lower than the maximum number found in step 1 in O(n).
result is the difference of the two numbers.
|
| « Last Edit: Jun 26th, 2007, 4:34am by sumantbhardvaj » |
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 #14 on: Jun 26th, 2007, 4:47am » |
Quote Modify
|
on Jun 26th, 2007, 4:34am, sumantbhardvaj wrote:Can't we do this problem in the following manner irrespective of the fact the array is sorted or not ??
Step 1 : Find the maximum number in the array. It can
be done in O(n)
Step 2: Find the next Maximum number lower than the maximum number found in step 1 in O(n).
result is the difference of the two numbers. |
|
That only works if the minimum difference between any of the number of the array is the difference between the maximum two. This is not the case if you have e.g. 1,5,6,9 ; the minimum difference there is between 5 and 6, not 6 and 9.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
sumantbhardvaj
Newbie
Posts: 20
|
|
Re: Find the minimum difference betwen two numbers
« Reply #15 on: Jun 26th, 2007, 5:50am » |
Quote Modify
|
ooopss my bad.. how can i be so sutpid..
any way,then i think there cannot be a solution in O(n) unless we use a O(n) sorting algo like radix, counting etc.. is'nt it ?
|
| « Last Edit: Jun 26th, 2007, 5:54am by sumantbhardvaj » |
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 #16 on: Jun 26th, 2007, 6:43am » |
Quote Modify
|
I have the same suspicion.
Although, we do get more than what we need if we employ an O(n) sorting algorithm. We only need the minimum difference, so we don't necessarily need to end up with a sorted array nor even know between which two numbers it occurs.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
dante
Newbie
Posts: 34
|
|
Re: Find the minimum difference betwen two numbers
« Reply #17 on: Jun 26th, 2007, 12:06pm » |
Quote Modify
|
the question didnt specify about difference being positive 
so minimum difference = min-max
|
|
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 #18 on: Jun 26th, 2007, 12:35pm » |
Quote Modify
|
on Jun 26th, 2007, 12:06pm, dante wrote:the question didnt specify about difference being positive
so minimum difference = min-max |
|
I thought differences were always positive..
To the effect that subtracting a from b (or b from a) is something other than taking the difference between a and b.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Find the minimum difference betwen two numbers
« Reply #19 on: Oct 15th, 2008, 4:07am » |
Quote Modify
|
on Jun 20th, 2007, 11:20am, Aryabhatta wrote:Let R = max-min
Then we must have that at least 2 numbers are within R/(N-1) of each other. Perhaps we can make use of that.
|
|
Ooops. ... This is valuable for maximal difference.
For minimal diference ... the algorithm cannot be based on comparisons only ... in that case there exist n! cases to be distinguished leading to  (nlog n). (Even the test there is a value twice based on comparisons only require this complexity).
Of course with fixed precission, the twice value problem can be solved by hashing.
And by binary search we can find the precision where each two values are separable (if there are no two same values).
... This will require O(n\log B) where B is the number representation size.
Actually you can eliminate numbers whose are "alone" during the process. ...
But I don't thing we can eliminate a nonconstant function of B as a factor in the complexity.
|
| « Last Edit: Oct 15th, 2008, 4:21am by Hippo » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Find the minimum difference betwen two numbers
« Reply #20 on: Oct 16th, 2008, 6:38am » |
Quote Modify
|
Hmm, double pointing looses information ..., pointing to other thread and back again.
It contained on Jun 18th, 2007, 10:21am, andyv wrote:| sort the array with radix sort (linear time). Then compare the differences of adiacent elements |
|
on Oct 16th, 2008, 12:59am, towr wrote:
?
Seems like a solution.
And it's not like I have a better one.
|
|
The radix sort works in O(nB) ... my proposal works in O(n log B) (unfortunately with much higher constant factor).
|
| « Last Edit: Oct 16th, 2008, 6:45am by Hippo » |
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Find the minimum difference betwen two numbers
« Reply #21 on: Mar 15th, 2011, 12:52pm » |
Quote Modify
|
Sorry for bringing up an old thread, But do we have any solution in O(n) time complexity?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Find the minimum difference betwen two numbers
« Reply #22 on: Mar 16th, 2011, 1:38am » |
Quote Modify
|
Yes if the array is sorted,
yes if we consider numbers in a limited range (in that case sooner or later we will end up with an infinity of duplicates of a limited number of values),
no in the usual sense of O(n) where it is assumed that the maximum size of the possible values is not a limiting factor.
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Find the minimum difference betwen two numbers
« Reply #23 on: Mar 16th, 2011, 1:54am » |
Quote Modify
|
on Mar 16th, 2011, 1:38am, Grimbal wrote:
no in the usual sense of O(n) where it is assumed that the maximum size of the possible values is not a limiting factor.
|
|
i see. i have read this question at many places and they say do it in O(n), where the elements have no restrictions. People do ask wrong questions 
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Find the minimum difference betwen two numbers
« Reply #24 on: Mar 16th, 2011, 8:07am » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print