@jatin: creating BST from *unsorted *array will take O(nlogn) timeso
how it can be solved in O(n)??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
@Arun : sort the array acc to their abs values .
On Sat, Jul 28, 2012 at 9:51 AM, Arun Kindra arunkin...@gmail.com wrote:
@Dave Sir : Sir if u sort the array(given above) the array would be:
-20,-8-2,4,9,10,12,14,17, and according to ur suggestion, the only ans is
{9,10}...but one of the ans
In O(n^2 ) we can do. But in O(n) i don't get any idea. If any one got the
idea just explain.
On Friday, 27 July 2012 15:35:24 UTC+5:30, Navin Kumar wrote:
Given array of integers (0 or +ve or -ve value) find two elements having
minimum difference in their absolute values.
e.g. Input {10 ,
was thinking that we can make a BST and and inorder traversal(both using
abs values) o(n) though will take log(n) space.
On Friday, 27 July 2012 15:35:24 UTC+5:30, Navin Kumar wrote:
Given array of integers (0 or +ve or -ve value) find two elements having
minimum difference in their absolute
Can you please give the algo of solving it in O(nlogn)
On Friday, 27 July 2012 15:35:24 UTC+5:30, Navin Kumar wrote:
Given array of integers (0 or +ve or -ve value) find two elements having
minimum difference in their absolute values.
e.g. Input {10 , -2, 4, 9,-20,17,-8,14,12)
output {9,-8}
and just for confirming.. will the algo for O(n2) be:
// uses kind of selection sort technique
mindiff = abs(a[1]-a[2]) //take a default min value
for i= 1 to n
for j= 1 to n
if i==j // same no.
continue
if abs(a[i]-a[j]) mindiff // if difference of some other
@s_m154: Sort the array in O(n log n) and then compare adjacent numbers to
find the closest pair in O(n). Total: O(n log n).
Dave
On Friday, July 27, 2012 10:41:28 AM UTC-5, s_m154 wrote:
Can you please give the algo of solving it in O(nlogn)
On Friday, 27 July 2012 15:35:24 UTC+5:30,
@Dave Sir : Sir if u sort the array(given above) the array would be:
-20,-8-2,4,9,10,12,14,17, and according to ur suggestion, the only ans is
{9,10}...but one of the ans {9,-8} is also possible...as he is asking
the difference in absolute values.
correct me if i m wrong...
--
You received
@Arun: I left out that you sort the array by absolute values and compare
absolute values of adjacent elements. The sorted array would be {-2, 4, -8,
9, 10, 12, 14, 17, -20}. Then abs(abs(-8) - abs(9)) is the smallest
difference.
Dave
Dave
On Friday, July 27, 2012 11:21:52 PM UTC-5, Arun
