[algogeeks] Re: minimum difference.

[ankur aggarwal]

@vivek

check the 2nd reply of varun
he acccept his

any thought better than nlogn


On Wed, Sep 2, 2009 at 3:00 PM, Vivek S  wrote:

> @Varun S VIt wont work for this 1 3 4 5
>
> 2009/9/2 Varun S V 
>
>> Since we difference between two minumum elements should suffice, how about
>> finding the min and second minimum element in the array in single scan and
>> returning their difference. This should take not more than O(N) time.
>>
>> Regards,
>> -Varun.
>>
>>
>> On Wed, Sep 2, 2009 at 12:09 AM, Shishir Mittal 
>> <1987.shis...@gmail.com>wrote:
>>
>>> Sort the array and find the minimum of difference of adjacent values of
>>> the sorted array.
>>> Time Complexity : O(nlogn), Space Complexity : O(1)
>>>
>>> On Tue, Sep 1, 2009 at 6:35 PM, ankur aggarwal >> > wrote:
>>>
 given  a array of length n. find  2 number such that their differnce is
 minimum.





>>>
>>>
>>> --
>>> Shishir Mittal
>>> Ph: +91 9936 180 121
>>>
>>>
>>>
>>>
>>
>>
>>
>
>
> --
> "Reduce, Reuse and Recycle"
> Regards,
> Vivek.S
>
> >
>

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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
-~--~~~~--~~--~--~---

[algogeeks] Re: minimum difference.

[Vivek S]

@Varun S VIt wont work for this 1 3 4 5

2009/9/2 Varun S V 

> Since we difference between two minumum elements should suffice, how about
> finding the min and second minimum element in the array in single scan and
> returning their difference. This should take not more than O(N) time.
>
> Regards,
> -Varun.
>
>
> On Wed, Sep 2, 2009 at 12:09 AM, Shishir Mittal <1987.shis...@gmail.com>wrote:
>
>> Sort the array and find the minimum of difference of adjacent values of
>> the sorted array.
>> Time Complexity : O(nlogn), Space Complexity : O(1)
>>
>> On Tue, Sep 1, 2009 at 6:35 PM, ankur aggarwal 
>> wrote:
>>
>>> given  a array of length n. find  2 number such that their differnce is
>>> minimum.
>>>
>>>
>>>
>>>
>>>
>>
>>
>> --
>> Shishir Mittal
>> Ph: +91 9936 180 121
>>
>>
>>
>>
>
> >
>


-- 
"Reduce, Reuse and Recycle"
Regards,
Vivek.S

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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
-~--~~~~--~~--~--~---

[algogeeks] Re: minimum difference.

[Prashant]

Hi,
I think we can use Min Heap Algorithm right!


On Wed, Sep 2, 2009 at 3:03 PM, Varun S V  wrote:

> Sorry this doesnt work. The difference between any other two sets can be
> lesser than the difference between two min numbers.
>
>
> On Wed, Sep 2, 2009 at 2:57 PM, Varun S V  wrote:
>
>> Since we difference between two minumum elements should suffice, how about
>> finding the min and second minimum element in the array in single scan and
>> returning their difference. This should take not more than O(N) time.
>>
>> Regards,
>> -Varun.
>>
>>
>> On Wed, Sep 2, 2009 at 12:09 AM, Shishir Mittal 
>> <1987.shis...@gmail.com>wrote:
>>
>>> Sort the array and find the minimum of difference of adjacent values of
>>> the sorted array.
>>> Time Complexity : O(nlogn), Space Complexity : O(1)
>>>
>>> On Tue, Sep 1, 2009 at 6:35 PM, ankur aggarwal >> > wrote:
>>>
 given  a array of length n. find  2 number such that their differnce is
 minimum.





>>>
>>>
>>> --
>>> Shishir Mittal
>>> Ph: +91 9936 180 121
>>>
>>>
>>>
>>>
>>
>
> >
>


-- 
Regards,
Prashant Kulkarni

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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
-~--~~~~--~~--~--~---

[algogeeks] Re: minimum difference.

[Bharath]

If the range of numbers is known, sort the array using radix sort and
compare difference of adjacent elements.

On Sep 2, 2:33 pm, Varun S V  wrote:
> Sorry this doesnt work. The difference between any other two sets can be
> lesser than the difference between two min numbers.
>
> On Wed, Sep 2, 2009 at 2:57 PM, Varun S V  wrote:
>
> > Since we difference between two minumum elements should suffice, how about
> > finding the min and second minimum element in the array in single scan and
> > returning their difference. This should take not more than O(N) time.
>
> > Regards,
> > -Varun.
>
> > On Wed, Sep 2, 2009 at 12:09 AM, Shishir Mittal 
> > <1987.shis...@gmail.com>wrote:
>
> >> Sort the array and find the minimum of difference of adjacent values of
> >> the sorted array.
> >> Time Complexity : O(nlogn), Space Complexity : O(1)
>
> >> On Tue, Sep 1, 2009 at 6:35 PM, ankur aggarwal 
> >> wrote:
>
> >>> given  a array of length n. find  2 number such that their differnce is
> >>> minimum.
>
> >> --
> >> Shishir Mittal
> >> Ph: +91 9936 180 121

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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
-~--~~~~--~~--~--~---

[algogeeks] Re: minimum difference.

[Amit Chauhan]

It won't work for following case

If suppose array contains the following integers
10 5 1 15 9
then according to you answer would be diff = |1-5| = 4
but correct answer is diff = |9-10| = 1

Thanks and Regards

Amit Chauhan
http://web.iiit.ac.in/~chauhan
Mobile : +91-9966347645

Y! IM   :  amitc_...@yahoo.co.in
GTalk  : amitchauhan@gmail.com



  There is always, always, always something to be thankful for !!

Sent from Hyderabad, AP, India
Ogden Nash   -
"The trouble with a kitten is that when it grows up, it's always a cat."

On Wed, Sep 2, 2009 at 2:57 PM, Varun S V  wrote:

> Since we difference between two minumum elements should suffice, how about
> finding the min and second minimum element in the array in single scan and
> returning their difference. This should take not more than O(N) time.
>
> Regards,
> -Varun.
>
>
> On Wed, Sep 2, 2009 at 12:09 AM, Shishir Mittal <1987.shis...@gmail.com>wrote:
>
>> Sort the array and find the minimum of difference of adjacent values of
>> the sorted array.
>> Time Complexity : O(nlogn), Space Complexity : O(1)
>>
>> On Tue, Sep 1, 2009 at 6:35 PM, ankur aggarwal 
>> wrote:
>>
>>> given  a array of length n. find  2 number such that their differnce is
>>> minimum.
>>>
>>>
>>>
>>>
>>>
>>
>>
>> --
>> Shishir Mittal
>> Ph: +91 9936 180 121
>>
>>
>>
>>
>
> >
>

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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
-~--~~~~--~~--~--~---

[algogeeks] Re: minimum difference.

[dinesh bansal]

While sorting itself, algorithm can keep track of minimum difference between
two consecutive elements found so far and the elements. This way time
complexity is same as time complexity of sorting algorithm.

Space complexity also I think its O(1).



On Wed, Sep 2, 2009 at 6:00 PM, Ralph Boland  wrote:

>
>
>
> On Sep 1, 7:05 am, ankur aggarwal  wrote:
> > given  a array of length n. find  2 number such that their differnce is
> > minimum.
>
> As already pointed out sorting and then comparing adjacent elements
> gives you an O(n log n) algorithm.
> If you have a likelyhood of duplicates then heapsort might be better
> since the heap can be built in linear time and the sort phase can be
> aborted if a duplicate element is found.  Alternatively one could
> put your elements into a set (using hashing) and stop immediately
> if you discover a duplicate by adding an element to the set that is
> already there (O(n) expected time to build the set).
>
> Ralph Boland
> >
>


-- 
Dinesh Bansal
The Law of Win says, "Let's not do it your way or my way; let's do it the
best way."

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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
-~--~~~~--~~--~--~---

[algogeeks] Re: minimum difference.

[Ralph Boland]

On Sep 1, 7:05 am, ankur aggarwal  wrote:
> given  a array of length n. find  2 number such that their differnce is
> minimum.

As already pointed out sorting and then comparing adjacent elements
gives you an O(n log n) algorithm.
If you have a likelyhood of duplicates then heapsort might be better
since the heap can be built in linear time and the sort phase can be
aborted if a duplicate element is found.  Alternatively one could
put your elements into a set (using hashing) and stop immediately
if you discover a duplicate by adding an element to the set that is
already there (O(n) expected time to build the set).

Ralph Boland
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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
-~--~~~~--~~--~--~---

[algogeeks] Re: minimum difference.

[Geoffrey Summerhayes]

On Sep 1, 8:02 pm, Ramaswamy R  wrote:
> Brute force, pick all combinations and keep track of minimum difference.
> Complexity: O(n^2) - (n-1)+(n-2)+(n-3) ... 1
> A little better, use any of the O(nlog n) sorting algorithm. In O(n) compare
> adjacent pairs and find the minimum difference. Complexity O(nlog n).
>

Could modify the sort to keep track of the minimum distance during
comparison, if two numbers have the minimum distance the sort must
compare them at some point.

--
Geoff
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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
-~--~~~~--~~--~--~---

[algogeeks] Re: minimum difference.

[Varun S V]

Sorry this doesnt work. The difference between any other two sets can be
lesser than the difference between two min numbers.

On Wed, Sep 2, 2009 at 2:57 PM, Varun S V  wrote:

> Since we difference between two minumum elements should suffice, how about
> finding the min and second minimum element in the array in single scan and
> returning their difference. This should take not more than O(N) time.
>
> Regards,
> -Varun.
>
>
> On Wed, Sep 2, 2009 at 12:09 AM, Shishir Mittal <1987.shis...@gmail.com>wrote:
>
>> Sort the array and find the minimum of difference of adjacent values of
>> the sorted array.
>> Time Complexity : O(nlogn), Space Complexity : O(1)
>>
>> On Tue, Sep 1, 2009 at 6:35 PM, ankur aggarwal 
>> wrote:
>>
>>> given  a array of length n. find  2 number such that their differnce is
>>> minimum.
>>>
>>>
>>>
>>>
>>>
>>
>>
>> --
>> Shishir Mittal
>> Ph: +91 9936 180 121
>>
>>
>> >>
>>
>

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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
-~--~~~~--~~--~--~---

[algogeeks] Re: minimum difference.

[Varun S V]

Since we difference between two minumum elements should suffice, how about
finding the min and second minimum element in the array in single scan and
returning their difference. This should take not more than O(N) time.

Regards,
-Varun.

On Wed, Sep 2, 2009 at 12:09 AM, Shishir Mittal <1987.shis...@gmail.com>wrote:

> Sort the array and find the minimum of difference of adjacent values of the
> sorted array.
> Time Complexity : O(nlogn), Space Complexity : O(1)
>
> On Tue, Sep 1, 2009 at 6:35 PM, ankur aggarwal 
> wrote:
>
>> given  a array of length n. find  2 number such that their differnce is
>> minimum.
>>
>>
>>
>>
>>
>
>
> --
> Shishir Mittal
> Ph: +91 9936 180 121
>
>
> >
>

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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
-~--~~~~--~~--~--~---

[algogeeks] Re: minimum difference.

[Shishir Mittal]

Sort the array and find the minimum of difference of adjacent values of the
sorted array.
Time Complexity : O(nlogn), Space Complexity : O(1)

On Tue, Sep 1, 2009 at 6:35 PM, ankur aggarwal wrote:

> given  a array of length n. find  2 number such that their differnce is
> minimum.
>
>
>
> >
>


-- 
Shishir Mittal
Ph: +91 9936 180 121

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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
-~--~~~~--~~--~--~---

[algogeeks] Re: minimum difference.

[Bhanu Pratap Singh]

one simple brute force method I see is that sort the array with the best
possible time complexity and then take the difference between the two middle
most if n is even or compare the difference between the adjacent and middle
element and take the lower is n is odd.

On Tue, Sep 1, 2009 at 6:35 PM, ankur aggarwal wrote:

> given  a array of length n. find  2 number such that their differnce is
> minimum.
>
>
>
> >
>


-- 
Regards

Bhanu Pratap Singh
Software Engineer
A R I C E N T

Mobile   +91 9886738496
Main +91 080 41068106

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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
-~--~~~~--~~--~--~---

[algogeeks] Re: minimum difference.

[Ramaswamy R]

Brute force, pick all combinations and keep track of minimum difference.
Complexity: O(n^2) - (n-1)+(n-2)+(n-3) ... 1
A little better, use any of the O(nlog n) sorting algorithm. In O(n) compare
adjacent pairs and find the minimum difference. Complexity O(nlog n).

On Tue, Sep 1, 2009 at 6:05 AM, ankur aggarwal wrote:

> given  a array of length n. find  2 number such that their differnce is
> minimum.
>
>
>
> >
>


-- 
Yesterday is History.
Tomorrow is a Mystery.
Today is a Gift! That is why it is called the Present :).

http://sites.google.com/site/ramaswamyr

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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
-~--~~~~--~~--~--~---