K

#### karan.shashi

I was asked this question in an interview recently:

Suppose you have the method signature

bool MyPairSum(int [] array, int sum)

the array has all unique values (no repeats), your task is to find two

indices in the array whose sum equals the input parameter sum. If there

exists two entries in the array that sum together to equal the input

parameter of sum, then return true, otherwise return false. what's the

most efficient implementation?

My question is can we have a better worse case runtime of O(n²) ??

I'm thinking that in the worse case, you'd have to compare each index

against all the other indices and test each sum until you find one that

matches the input sum. In the worse case, there will be no pair of

indices that equal the input sum parameter. Am I overlooking a very

basic trick? I figured with all the sharp people in here, somebody can

discern whether I'm off base or not

Here's the sample implementation I was thinking of:

bool MyPairSum(int [] array, int sum)

{

for (int i = 0; i < array.Length; i++)

{

for (int j = i + 1; j < array.Length; j++)

{

if ( array

*+ array[j] == sum)*

return true;

}

}

return false;

}

Tks, Karan S.

return true;

}

}

return false;

}

Tks, Karan S.