Author |
Topic: Two numbers with minimum difference (Read 5794 times) |
|
howard roark
Full Member
Posts: 241
|
 |
Two numbers with minimum difference
« on: Oct 14th, 2008, 10:14pm » |
 Quote  Modify
|
Algorithm to find the two numbers whose difference is minimum among the set of numbers.
For example the sequence is 5, 13, 7, 0, 10, 20, 1, 15, 4, 19
The algorithm should return min diff = 20-19 = 1.
Constraint - Time Complexity O(N)
|
|
 IP Logged |
|
|
|
howard roark
Full Member
Posts: 241
|
|
Re: Two numbers with minimum difference
« Reply #2 on: Oct 15th, 2008, 6:19pm » |
Quote Modify
|
Thanks towr...... but the post you have given doesnt solve the problem........ Do you think there is any solution for this question
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Two numbers with minimum difference
« Reply #3 on: Oct 16th, 2008, 12:59am » |
Quote Modify
|
on Oct 15th, 2008, 6:19pm, hoogle wrote:| Thanks towr...... but the post you have given doesnt solve the problem........ Do you think there is any solution for this question |
|
?
on Jun 18th, 2007, 10:21am, andyv wrote:| sort the array with radix sort (linear time). Then compare the differences of adjacent elements |
|
Seems like a solution.
And it's not like I have a better one.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Two numbers with minimum difference
« Reply #4 on: Oct 16th, 2008, 6:37am » |
Quote Modify
|
I expected editting the original thread is prefered way ... so I will continue in doing that
|
|
IP Logged |
|
|
|
prof
Newbie
Posts: 1
|
|
Re: Two numbers with minimum difference
« Reply #5 on: Oct 14th, 2011, 12:32am » |
Quote Modify
|
-> Form a binary search tree which requires O(logn ).
-> Traverse BST in inorder fashion .
-> We will have sorted array.
-> Then track the minimum number variable from whole sorted array sequence.
-> That substraction number difference and its two corresponding numbers are the answer of the given thing.
|
|
IP Logged |
|
|
|
RajivG
Junior Member
Gender:
Posts: 72
|
|
Re: Two numbers with minimum difference
« Reply #6 on: Oct 14th, 2011, 4:14am » |
Quote Modify
|
on Oct 14th, 2011, 12:32am, prof wrote:
-> Form a binary search tree which requires O(logn ).
|
|
are you sure  check once again
|
|
IP Logged |
|
|
|
mmgc
Newbie
Gender:
Posts: 47
|
|
Re: Two numbers with minimum difference
« Reply #7 on: Oct 21st, 2011, 11:34pm » |
Quote Modify
|
If space is not a big constraint & max - min < c * N where c is not a big number then allocate an array of size max - min. Traverse the original array and keep updating the new array for e.g. if we have 5 in original array then put newArray[5 - min] = 1.
Now traverse the new array while tracking the difference b/w subscripts with element 1.
|
|
IP Logged |
|
|
|
computing
Newbie
Gender:
Posts: 2
|
|
Re: Two numbers with minimum difference
« Reply #8 on: Oct 22nd, 2011, 11:54am » |
Quote Modify
|
@mmgc, good technique. Yet read the question again. There is no guarantee that the difference max - min will be less than N, size of original array.
Perhaps we could optimize your solution? While updating the auxiliary array, check for adjacent locations (on both the sides) and update a global element for least minimum. Hope it works...
|
|
IP Logged |
|
|
|
MrLambert
Newbie
Posts: 13
|
|
Re: Two numbers with minimum difference
« Reply #10 on: Oct 31st, 2011, 9:51am » |
Quote Modify
|
"sdcvvc" wrote about smallest and largest numbers.
I dont see this happening here, but with small change to his solution, this is solved.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print