Suppose that x is an integer and A is an array of n intergers. Give an efficient algorithm to find if there exists two elements in A whose sum is x. Determine the time complexity of this algorithm.

I need this before Mon 15Jun so if you can get it right by then the 250 points are yours. Hopefully the time complexity will be better than O(n^2)

I need this before Mon 15Jun so if you can get it right by then the 250 points are yours. Hopefully the time complexity will be better than O(n^2)

Homework problem? Nah, couldn't be that, you must have a job where they give you problems like this.

Big hint #2: don't interview at Microsoft. (I wrote your name down.)

B ekiM

After the function has returned true , you can get the first element using FINDSRESULT->FirstNumber and the second using SecondNumber . I have not tested this routine , so tell me if you see problems ( but you should not , I think ! )

typedef struct FINDSRESULT

{

int FirstNumber;

int SecondNumber;

}

bool FindS(char*A,int x,int n,FINSRESULT* f)

{

for (int k = 0 ; k < n ; k++)

{

for (int z = k + 1 ; z < n ; z++)

{

if ((A[k] + A[z]) == x)

{

f->FirstNumber = k;

f->SecondNumber = z;

return true;

}

}

}

return false;

}

I don't want to do your school / study / workcourse assingment for you, but here's maybe something worth considering:

Are the elements in the array all positive (unsigned)? if so, than you don't need to check for an counter-element to make X if the first element is larger than (or is) X, because it's sum will never be equal to X without a negative entry.

Furthermore: it may be handy to check the MIN and MAX value of the elements in the array. if you find a first element that needs a number larger than MAX, or smaller than MIN, than you don't need to bother finding one.

Also, sorting the array (as said before) can give you a big advantage.

The answer from WxW is, in my opinion not correct. you asked for an algorithm with better than O(n^2) performance. the one in use is, in worst case, O(n^2)!

and i suggest you make an apologise to nietod for your rude comments

I wasn't aware that there was a different standard of conduct for the internet.

This question is in violation of your academic oath. That is not my opinion. That is fact. I'm sure you believe that as well. Or do you think it would be okay to tell your professer where you got the answer? In addition, this is also a violation of the customer agreement you agreed to as a client of experts exchange. That is grounds for removal from the service.

Please provide your email to receive a sample view!

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.