Simple but confusing algorith question

[karan.shashi]

Hey all,
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[i] + array[j] == sum)
return true;
}
}
return false;
}
Tks, Karan S.

[Greg Young [MVP]]

If the data were sorted you could do much better. If they are not sorted you
would have n^2 as your worst case as you have to check every index of the
array for each value.

even so you could still do slightly better by only issuing a single add/sub
instead of a operation on every iteration ... see example.

bool MyPairSum(int [] array, int sum)
{
for (int i = 0; i < array.Length; i++)
{
int need = sum - array[j];
for (int j = 0; j < array.Length; j++)
{
if (array[j] == sum)
return true;
}
}
return false;
}

Also your code has failure modes because int j = i + 1 ... what about the
following data?

array 0,1,2 sum = 3 by using i+1 you say it doesn't exist.

Another quick question ... what should the behavior be for the following?

array 1,2,3,4 sum = 5

Cheers,

Greg

<ka**********@g mail.com> wrote in message
news:11******** *************@i 39g2000cwa.goog legroups.com...
Hey all,
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[i] + array[j] == sum)
return true;
}
}
return false;
}
Tks, Karan S.

[MSDN]

This is Sorted
array 1,2,3,4 sum = 5

This is not Sorted
array 1,4,2,3 sum = 5

Which one is faster??

SA

"Greg Young [MVP]" <Dr************ *@hotmail.com> wrote in message
news:OM******** *****@TK2MSFTNG P05.phx.gbl...

If the data were sorted you could do much better. If they are not sorted
you
would have n^2 as your worst case as you have to check every index of the
array for each value.

even so you could still do slightly better by only issuing a single
add/sub
instead of a operation on every iteration ... see example.

bool MyPairSum(int [] array, int sum)
{
for (int i = 0; i < array.Length; i++)
{
int need = sum - array[j];
for (int j = 0; j < array.Length; j++)
{
if (array[j] == sum)
return true;
}
}
return false;
}

Also your code has failure modes because int j = i + 1 ... what about the
following data?

array 0,1,2 sum = 3 by using i+1 you say it doesn't exist.

Another quick question ... what should the behavior be for the following?

array 1,2,3,4 sum = 5

Cheers,

Greg

<ka**********@g mail.com> wrote in message
news:11******** *************@i 39g2000cwa.goog legroups.com...
Hey all,
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[i] + array[j] == sum)
return true;
}
}
return false;
}
Tks, Karan S.

[MSDN]

if (array[j] == sum) < == need
return true;

"Greg Young [MVP]" <Dr************ *@hotmail.com> wrote in message
news:OM******** *****@TK2MSFTNG P05.phx.gbl...

If the data were sorted you could do much better. If they are not sorted
you
would have n^2 as your worst case as you have to check every index of the
array for each value.

even so you could still do slightly better by only issuing a single
add/sub
instead of a operation on every iteration ... see example.

bool MyPairSum(int [] array, int sum)
{
for (int i = 0; i < array.Length; i++)
{
int need = sum - array[j];
for (int j = 0; j < array.Length; j++)
{
if (array[j] == sum)
return true;
}
}
return false;
}

Also your code has failure modes because int j = i + 1 ... what about the
following data?

array 0,1,2 sum = 3 by using i+1 you say it doesn't exist.

Another quick question ... what should the behavior be for the following?

array 1,2,3,4 sum = 5

Cheers,

Greg

<ka**********@g mail.com> wrote in message
news:11******** *************@i 39g2000cwa.goog legroups.com...
Hey all,
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[i] + array[j] == sum)
return true;
}
}
return false;
}
Tks, Karan S.

[Greg Young [MVP]]

If you can count on sorted data you can make assumptions in your looping and
get your worst case a whole lot better than O(n^2)

i.e
if current + array[i] > sum {
//skip rest of list
}

"MSDN" <sq**********@h otmail.com> wrote in message
news:%2******** ********@TK2MSF TNGP03.phx.gbl. ..

This is Sorted
array 1,2,3,4 sum = 5

This is not Sorted
array 1,4,2,3 sum = 5

Which one is faster??

SA

"Greg Young [MVP]" <Dr************ *@hotmail.com> wrote in message
news:OM******** *****@TK2MSFTNG P05.phx.gbl...

If the data were sorted you could do much better. If they are not sorted
you
would have n^2 as your worst case as you have to check every index of the
array for each value.

even so you could still do slightly better by only issuing a single
add/sub
instead of a operation on every iteration ... see example.

bool MyPairSum(int [] array, int sum)
{
for (int i = 0; i < array.Length; i++)
{
int need = sum - array[j];
for (int j = 0; j < array.Length; j++)
{
if (array[j] == sum)
return true;
}
}
return false;
}

Also your code has failure modes because int j = i + 1 ... what about the
following data?

array 0,1,2 sum = 3 by using i+1 you say it doesn't exist.

Another quick question ... what should the behavior be for the following?

array 1,2,3,4 sum = 5

Cheers,

Greg

<ka**********@g mail.com> wrote in message
news:11******** *************@i 39g2000cwa.goog legroups.com...
Hey all,
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[i] + array[j] == sum)
return true;
}
}
return false;
}
Tks, Karan S.

[Greg Young [MVP]]

Also O(n^2) is talking about the worst case ... you have provided the best
case as a comparison ...

to compare the worst case in this problem you would actually be looking at
iterations on a miss ..

array 1,2,3,4 sum 12
array 3,2,1,4 sum 12

in the onsorted case you have O^2 (loop through all twice) .. 16

in the sorted case you would be with almost no effort at 9 comparisons on
the worst case as it would allow you to do the simple change in the original
code (use i+1 for j instead of 0)
"MSDN" <sq**********@h otmail.com> wrote in message
news:%2******** ********@TK2MSF TNGP03.phx.gbl. ..

This is Sorted
array 1,2,3,4 sum = 5

This is not Sorted
array 1,4,2,3 sum = 5

Which one is faster??

SA

"Greg Young [MVP]" <Dr************ *@hotmail.com> wrote in message
news:OM******** *****@TK2MSFTNG P05.phx.gbl...

If the data were sorted you could do much better. If they are not sorted
you
would have n^2 as your worst case as you have to check every index of the
array for each value.

even so you could still do slightly better by only issuing a single
add/sub
instead of a operation on every iteration ... see example.

bool MyPairSum(int [] array, int sum)
{
for (int i = 0; i < array.Length; i++)
{
int need = sum - array[j];
for (int j = 0; j < array.Length; j++)
{
if (array[j] == sum)
return true;
}
}
return false;
}

Also your code has failure modes because int j = i + 1 ... what about the
following data?

array 0,1,2 sum = 3 by using i+1 you say it doesn't exist.

Another quick question ... what should the behavior be for the following?

array 1,2,3,4 sum = 5

Cheers,

Greg

<ka**********@g mail.com> wrote in message
news:11******** *************@i 39g2000cwa.goog legroups.com...
Hey all,
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[i] + array[j] == sum)
return true;
}
}
return false;
}
Tks, Karan S.

[Greg Young [MVP]]

n/m on i+1 must need coffee :)

"Greg Young [MVP]" <Dr************ *@hotmail.com> wrote in message
news:OM******** *****@TK2MSFTNG P05.phx.gbl...

If the data were sorted you could do much better. If they are not sorted
you
would have n^2 as your worst case as you have to check every index of the
array for each value.

even so you could still do slightly better by only issuing a single
add/sub
instead of a operation on every iteration ... see example.

bool MyPairSum(int [] array, int sum)
{
for (int i = 0; i < array.Length; i++)
{
int need = sum - array[j];
for (int j = 0; j < array.Length; j++)
{
if (array[j] == sum)
return true;
}
}
return false;
}

Also your code has failure modes because int j = i + 1 ... what about the
following data?

array 0,1,2 sum = 3 by using i+1 you say it doesn't exist.

Another quick question ... what should the behavior be for the following?

array 1,2,3,4 sum = 5

Cheers,

Greg

<ka**********@g mail.com> wrote in message
news:11******** *************@i 39g2000cwa.goog legroups.com...
Hey all,
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[i] + array[j] == sum)
return true;
}
}
return false;
}
Tks, Karan S.

[Lucian Wischik]

"Greg Young [MVP]" <Dr************ *@hotmail.com> wrote:

If you can count on sorted data you can make assumptions in your looping and
get your worst case a whole lot better than O(n^2)

I think it's O(n) if the list is sorted...

(1) Sort the list from smallest to largest
(2) Have two pointers, "left" at the start of the list, "right" at the
end.
(3) If the sum of your two pointers is too big, then "right" has to
move left
(4) If the sum is too small, then "left" has to move right
(5) If the two pointers meet then there is no solution

Proof: suppose there exists a solution x+y where x is smaller. If
left<x and right>y then any move we can make is acceptable. If left=x
then no move will make right<y. Similarly if right=y then no move will
make left>x.

--
Lucian

[karan.shashi]

The array isn't sorted I believe, just no dupes.Also, it just checks if
two indexes summed equals sum like array[3] + array[33] = sum !!

Thanks for your input though :)
Greg Young [MVP] wrote:

If the data were sorted you could do much better. If they are not sorted you
would have n^2 as your worst case as you have to check every index of the
array for each value.

even so you could still do slightly better by only issuing a single add/sub
instead of a operation on every iteration ... see example.

bool MyPairSum(int [] array, int sum)
{
for (int i = 0; i < array.Length; i++)
{
int need = sum - array[j];
for (int j = 0; j < array.Length; j++)
{
if (array[j] == sum)
return true;
}
}
return false;
}

Also your code has failure modes because int j = i + 1 ... what about the
following data?

array 0,1,2 sum = 3 by using i+1 you say it doesn't exist.

Another quick question ... what should the behavior be for the following?

array 1,2,3,4 sum = 5

Cheers,

Greg

<ka**********@g mail.com> wrote in message
news:11******** *************@i 39g2000cwa.goog legroups.com...
Hey all,
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[i] + array[j] == sum)
return true;
}
}
return false;
}


Tks, Karan S.

[karan.shashi]

It does seem like there's no way around checking all possibilties
unless some other data structure was involved. I was trying to cut down
on comparisons/summations by eliminating the first element, then the
second, so the over run time would be on the order of

n ( n - 1 )
----------------
2

in the worse case, which basically is O(n²).

like from your example
comparisons: 1 with 2, 1 with 3, 1 with 4, 2 with 3, 2 with 4, 3 with 4
(done, all combos tested). You wouldn't compare 1 with 1, 2 with 2, and
the like since they're not different indexes. worse case runtime = 1/2
n² which amounts to O(n²) unfortunately.

Thanks for your reply

Greg Young [MVP] wrote:

Also O(n^2) is talking about the worst case ... you have provided the best
case as a comparison ...

to compare the worst case in this problem you would actually be looking at
iterations on a miss ..

array 1,2,3,4 sum 12
array 3,2,1,4 sum 12

in the onsorted case you have O^2 (loop through all twice) .. 16

in the sorted case you would be with almost no effort at 9 comparisons on
the worst case as it would allow you to do the simple change in the original
code (use i+1 for j instead of 0)
"MSDN" <sq**********@h otmail.com> wrote in message
news:%2******** ********@TK2MSF TNGP03.phx.gbl. ..

This is Sorted
array 1,2,3,4 sum = 5

This is not Sorted
array 1,4,2,3 sum = 5

Which one is faster??

SA

"Greg Young [MVP]" <Dr************ *@hotmail.com> wrote in message
news:OM******** *****@TK2MSFTNG P05.phx.gbl...

If the data were sorted you could do much better. If they are not sorted
you
would have n^2 as your worst case as you have to check every index of the
array for each value.

even so you could still do slightly better by only issuing a single
add/sub
instead of a operation on every iteration ... see example.

bool MyPairSum(int [] array, int sum)
{
for (int i = 0; i < array.Length; i++)
{
int need = sum - array[j];
for (int j = 0; j < array.Length; j++)
{
if (array[j] == sum)
return true;
}
}
return false;
}

Also your code has failure modes because int j = i + 1 ... what about the
following data?

array 0,1,2 sum = 3 by using i+1 you say it doesn't exist.

Another quick question ... what should the behavior be for the following?

array 1,2,3,4 sum = 5

Cheers,

Greg

<ka**********@g mail.com> wrote in message
news:11******** *************@i 39g2000cwa.goog legroups.com...
Hey all,
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[i] + array[j] == sum)
return true;
}
}
return false;
}
Tks, Karan S.