[algogeeks] Re: absolute minimum difference
@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 https://groups.google.com/d/msg/algogeeks/-/NEsBS0oK_DkJ. 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?hl=en.
Re: [algogeeks] Re: absolute minimum difference
@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 {9,-8} is also possible...as he is asking
the difference in absolute values.
correct me if i m wrong...
--
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?hl=en.
--
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?hl=en.
[algogeeks] Re: absolute minimum difference
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 , -2, 4, 9,-20,17,-8,14,12)
output {9,-8}
I have solved it in O(nlogn). can it 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
https://groups.google.com/d/msg/algogeeks/-/viXnfcSJGZgJ.
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?hl=en.
[algogeeks] Re: absolute minimum difference
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 values.
e.g. Input {10 , -2, 4, 9,-20,17,-8,14,12)
output {9,-8}
I have solved it in O(nlogn). can it 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
https://groups.google.com/d/msg/algogeeks/-/HinzziloXxUJ.
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?hl=en.
[algogeeks] Re: absolute minimum difference
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}
I have solved it in O(nlogn). can it 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
https://groups.google.com/d/msg/algogeeks/-/-gzyD6CoO6gJ.
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?hl=en.
[algogeeks] Re: absolute minimum difference
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 pair of no is smaller a=a[i], b=a[j] // save those no.s mindiff = abs(a[i]-a[j]) // make that difference the smallest print a,b I am quite new to programming so please tell me if what i have written is correct even though I know it has a higher complexity. Thank you. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/eaTEFJHiVwoJ. 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?hl=en.
[algogeeks] Re: absolute minimum difference
@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, 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}
I have solved it in O(nlogn). can it 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
https://groups.google.com/d/msg/algogeeks/-/9HjgwKTqomAJ.
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?hl=en.
Re: [algogeeks] Re: absolute minimum difference
@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 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?hl=en.
Re: [algogeeks] Re: absolute minimum difference
@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 Kindra 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 {9,-8} is also possible...as he is asking
the difference in absolute values.
correct me if i m wrong...
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/xqgVivlgw68J.
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?hl=en.
