[etc] Re: Reg. your quiz on numbers. (fwd)

---------- Forwarded message ----------
Date: Wed, 16 Oct 2002 12:14:00 -0500
From: Ashfaq Khokhar <ashfaq@cs.uic.edu>
To: Shashank Khanvilkar <shashank@evl.uic.edu>
Subject: Re: Reg. your quiz on numbers.

You have the question right but I am not sure of the solution.

Ashfaq


Shashank Khanvilkar wrote:

> Hello prof.
> A few days back, you had asked me the following question:
>
> take an Array of numbers (sorted or unsorted).. Given any number X (say),
> find two elements in the array that add up to X.
>
> You had also told me that the solution is trivial if done in O(n^2) and you
> told me that u found a more elegant solution in O(nlgn).
>
> Please let me know if the above is correct.
>
> If the above is correct then the following might be one solution to it..
>
> Consider the following array of elements.
>
> AA = {17, 16, 24, 30, 5, 2, 6, 10, 11, 15}
>
> Assume that i want to find two elemnts that add upto 29 (=X)..
> Now i assuming that 29 = a+ b and a, b > 0... ==> the (29, 0) do not form a
> valid pair).
>
> now if u see series..
> 1, 2, 3, 4,...n
> adding the 1st and last element will lead to the sum (n+1), also the second
> and the second last element will lead to (n+1) and so on..
> and there are n/2 such pairs that lead to sum (n+1).
> hence we can write 14 such pairs for the number 29.. for e.g.
> (1,28), (2, 27).....(14, 15).
>
> So here is an algorithm.
> 1. take the number X (=29)
> 2. divide it by 2 and take floor (X) (=14).
> 3. make a seperate boolean array of 14 elements..x[1], x[2], x[14] and set
> all of them to false(This can be a hash table.. but we assume that space is
> not a constraint).
> 4. now read the first element AA[1]. (=17)
> 5. iS (17 < floor(29/2)) ==> NO, the do X - 17 (i.e 29 -17 = 12)
> 6. if x[12] th element was already true, then we have found the number pair,
> (17, 12). .. if not then just set the x[12] th element to true and go to
> next element of AA.
>
> 8. continue this way till you find the number pair.
>
> This algorithm will finish in O(n).
>
> Let me know if you had asked me a different question.
>
> Regards
> Shashank