Re: Simple but confusing algorith question

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance

Did you mean to type

int need = sum - array[ i ];

??


On Thu, 27 Apr 2006 00:47:56 -0400, "Greg Young [MVP]"
<DruckDruckGoose@xxxxxxxxxxx> wrote:

I think you are missing the point about the subtraction part ..

You lower your constant by using the code as I wrote it .. by doing the
subtraction up front you avoid doing the additions.

on a given iteration yours ... is j comparisons + j additions .. mine is j
comparisons + 1 subtraction.

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

Another interesting question is how much data is being passed into this and
how often to you expect to be in your worst case? Since the data if sorted
can be done in linear time, if you expected to be in your worst case (miss)
most of the time with rather large datasets being passed in it might be
worth while to take a look at sorting the data first as it could end up
lowerring your average case.

Greg
<karan.shashi@xxxxxxxxx> wrote in message
news:1146111134.247647.141220@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
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

<karan.shashi@xxxxxxxxx> wrote in message
news:1146101141.203814.21600@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
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.

.

Relevant Pages

  • Re: Subset Sum problem (w/ limited scope)
    ... The "Subset Sum" problem (stated various ways depending on what you ... a subset of those integers that sums up to zero. ... Are there going to be duplicate values in your original array? ...
    (comp.lang.fortran)
  • Re: Python from Wise Guys Viewpoint
    ... > proof that the following java code correctly sums an array of integers? ... // Return the sum of all elements in the array, ... I've written about 20 lines of Java *ever*, ...
    (comp.lang.lisp)
  • Re: How can I find the greatest possible sum within 12 months? A newbie...
    ... It may be because you have headers, and when I tied it first I omitted ... You may have omitted to enter it as an array formula (see notes on ... the starting sum is in A2 and the end sum is in A123. ... Excel will insert them for you. ...
    (microsoft.public.excel.worksheet.functions)
  • Re: Explanation of SUMPRODUCT
    ... I don't even think you need to enter it as an array ... Yes, we know this, but in this case SUM is an array formula SUMPRODUCT ... > each element is the number of times the corresponding cell value appears ...
    (microsoft.public.excel.programming)
  • Re: Simple but confusing algorith question
    ... As you mention that this is an interview question ... ... through the array, then query against the structure somehow. ... structure and the cost of querying the data structure. ... array 1,2,3,4 sum = 5 ...
    (microsoft.public.dotnet.languages.csharp)