Given a sorted array find all possible |ai - aj| where ai,aj belongs to Array A. n^2 is obvious. Find a solution in O(N).

Go down

Re: Given a sorted array find all possible |ai - aj| where ai,aj belongs to Array A. n^2 is obvious. Find a solution in O(N).

Post  viterbi on Tue Sep 13, 2011 9:53 am

I think this problem for quite a while, and I don't think it's possible. Are you sure about the problem? Where did you see this problem?

viterbi

Posts : 32
Join date : 2011-09-03

View user profile

Back to top Go down

Re: Given a sorted array find all possible |ai - aj| where ai,aj belongs to Array A. n^2 is obvious. Find a solution in O(N).

Post  Admin on Tue Sep 13, 2011 11:11 am

I saw this problem in MITBBS, also not sure about the time complexity it requires.

viterbi wrote:I think this problem for quite a while, and I don't think it's possible. Are you sure about the problem? Where did you see this problem?

Admin
Admin

Posts : 131
Join date : 2011-08-16

View user profile http://codefornongeek.forumotion.com

Back to top Go down

Re: Given a sorted array find all possible |ai - aj| where ai,aj belongs to Array A. n^2 is obvious. Find a solution in O(N).

Post  Sponsored content


Sponsored content


Back to top Go down

Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum