Algorithm Challenge

[Raja]

here is an array A[1 to n] of numbers. You need to find the min
index i such that A[ i ] + A[ j ] = M , where M is a given constant
and i < j <= n. The complexity of the algo shd be O(n).

Can anyone please tell me the idea ?

Thank You,

[rossum]

Re: Algorithm Challenge

On 15 Dec 2006 05:18:09 -0800, "Raja" <rokkamraja@gma il.comwrote:

>here is an array A[1 to n] of numbers. You need to find the min
>index i such that A[ i ] + A[ j ] = M , where M is a given constant
>and i < j <= n. The complexity of the algo shd be O(n).
>
>Can anyone please tell me the idea ?
>
>Thank You,

1 This question is nothing to do with C++ so it is OT on comp.lang.c++
I would suggest comp.programmin g for a general algorithm question such
as this.

2 We don't do homework, and nor do the people at comp.programmin g.

3 If you are stuck with C++ then show us the C++ code you are having
problems with and we can help you with it.

rossum

[frame]

Re: Algorithm Challenge


Raja wrote:

here is an array A[1 to n] of numbers. You need to find the min
index i such that A[ i ] + A[ j ] = M , where M is a given constant
and i < j <= n. The complexity of the algo shd be O(n).
>
Can anyone please tell me the idea ?
>
Thank You,

1. Declare an empty hash table that provides O(1) lookup on average.
2. Iterate through the array A[1...n] using j as index.
if(A[j] < M) {
if (look up for A[j] as key in the hash table is success) {
You got the answer:
i = value of A[j] in the hash table;
j = current value of j;
}
else
store the difference (M - A[j]) as key and j as value in
the hash table.
}

[frame]

Re: Algorithm Challenge

frame wrote:

if(A[j] < M) {

Typo: please read "if(A[j] < M)" as "if(A[j] <= M)."

[This is bit off-topic, you should have posted this in some group
focussed on algorithms]

Thanks!

[frame]

Re: Algorithm Challenge

frame wrote:

if(A[j] < M) {

Typo: please read the above as "if(A[j] <= M) {"

[This is bit off-topic, you should have posted this in some group
focussed on algorithms]

Thanks!