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]

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.programming for a general algorithm question such
as this.

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

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]

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]

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]

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!