wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Find the minimum difference betwen two numbers
        
(Message started by: spirit on Jun 18^th, 2007, 9:33am)

Title: Find the minimum difference betwen two numbers
Post by spirit on Jun 18^th, 2007, 9:33am

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)

Title: Re: Find the minimum difference betwen two numbers
Post by R0B1N on Jun 18^th, 2007, 9:35am

Atleast in the Given Example , The Input Looks like sorted one , So you Just Need to Compare the Adjacent numbers ::)

Am i missing something ?

Title: Re: Find the minimum difference betwen two numbers
Post by towr on Jun 18^th, 2007, 9:47am

It seems like a hard thing to do if the array weren't sorted, so I'd assume that's a precondition.

Title: Re: Find the minimum difference betwen two numbers
Post by andyv on Jun 18^th, 2007, 10:21am

sort the array with radix sort (linear time). Then compare the differences of adiacent elements

Title: Re: Find the minimum difference betwen two numbers
Post by spirit on Jun 18^th, 2007, 10:13pm

no the numbers are not sorted ,it just the case that in the example given they are sorted .. ;) ;)

Title: Re: Find the minimum difference betwen two numbers
Post by spirit on Jun 18^th, 2007, 10:16pm

on 06/18/07 at 10:21:14, 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..

Title: Re: Find the minimum difference betwen two numbers
Post by towr on Jun 19^th, 2007, 1:17am

And I don't suppose you mean the different between two consecutive numbers either?

Title: Re: Find the minimum difference betwen two numbers
Post by spirit on Jun 19^th, 2007, 2:08am

no but if the numbers are sorted then the minimum difference would obviously be between the consecutive numbers

Title: Re: Find the minimum difference betwen two numbers
Post by andyv on Jun 19^th, 2007, 3:05am

on 06/18/07 at 22:16:01, 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.

Title: Re: Find the minimum difference betwen two numbers
Post by spirit on Jun 19^th, 2007, 3:30am

but what about the space complexity ?

Title: Re: Find the minimum difference betwen two numbers
Post by Aryabhatta on Jun 19^th, 2007, 9:26am

on 06/18/07 at 22:16:01, 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...

Title: Re: Find the minimum difference betwen two numbers
Post by spirit on Jun 20^th, 2007, 4:12am

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

Title: Re: Find the minimum difference betwen two numbers
Post by Aryabhatta on Jun 20^th, 2007, 11:20am

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.

Title: Re: Find the minimum difference betwen two numbers
Post by sumantbhardvaj on Jun 26^th, 2007, 4:34am

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.

Title: Re: Find the minimum difference betwen two numbers
Post by towr on Jun 26^th, 2007, 4:47am

on 06/26/07 at 04:34:10, sumantbhardvaj wrote:

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.

Title: Re: Find the minimum difference betwen two numbers
Post by sumantbhardvaj on Jun 26^th, 2007, 5:50am

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 ?

Title: Re: Find the minimum difference betwen two numbers
Post by towr on Jun 26^th, 2007, 6:43am

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.

Title: Re: Find the minimum difference betwen two numbers
Post by dante on Jun 26^th, 2007, 12:06pm

the question didnt specify about difference being positive ???
so minimum difference = min-max ::)

Title: Re: Find the minimum difference betwen two numbers
Post by towr on Jun 26^th, 2007, 12:35pm

on 06/26/07 at 12:06:11, 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.

Title: Re: Find the minimum difference betwen two numbers
Post by Hippo on Oct 15^th, 2008, 4:07am

on 06/20/07 at 11:20:50, 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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/theta.gif(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.

Title: Re: Find the minimum difference betwen two numbers
Post by Hippo on Oct 16^th, 2008, 6:38am

Hmm, double pointing looses information ..., pointing to other thread and back again.

It contained
on 06/18/07 at 10:21:14, andyv wrote:

sort the array with radix sort (linear time). Then compare the differences of adiacent elements

on 10/16/08 at 00:59:28, 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).

Title: Re: Find the minimum difference betwen two numbers
Post by birbal on Mar 15^th, 2011, 12:52pm

Sorry for bringing up an old thread, But do we have any solution in O(n) time complexity?

Title: Re: Find the minimum difference betwen two numbers
Post by Grimbal on Mar 16^th, 2011, 1:38am

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.

Title: Re: Find the minimum difference betwen two numbers
Post by birbal on Mar 16^th, 2011, 1:54am

on 03/16/11 at 01:38:02, 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 :-/

Title: Re: Find the minimum difference betwen two numbers
Post by Grimbal on Mar 16^th, 2011, 8:07am

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).

Title: Re: Find the minimum difference betwen two numbers
Post by birbal on Mar 16^th, 2011, 11:28am

on 03/16/11 at 08:07:33, 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.

Title: Re: Find the minimum difference betwen two numbers
Post by resim on Jan 22^nd, 2012, 2:15am

Thanks..

Title: Re: Find the minimum difference betwen two numbers
Post by David Flower on Apr 13^th, 2012, 8:41am

It seems like a difficult factor to do if the range weren't categorized, so I'd believe that's a precondition.

Title: Re: Find the minimum difference betwen two numbers
Post by deepaknasa on Jun 14^th, 2012, 4:03am

proxmap sorting can sort array in O(n) complexity.

cs.uah.edu/~rcoleman/CS221/Sorting/ProxMapSort.html

Title: Re: Find the minimum difference betwen two numbers
Post by towr on Jun 14^th, 2012, 7:15am

Proxmap is O(n²) in the worst case. (Because it's insertion sort in the worst case.)

Nice to learn about a new (to me) sorting technique, though.

Title: Re: Find the minimum difference betwen two numbers
Post by Aryabhatta on Jun 21^st, 2012, 1:21pm

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...

Title: Re: Find the minimum difference betwen two numbers
Post by Saravana on Jun 30^th, 2012, 1:44am

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

Title: Re: Find the minimum difference betwen two numbers
Post by towr on Jun 30^th, 2012, 2:20am

Have you tried running your code? Because it gives the answer 3, whereas the minimum difference is in fact 1.