We help IT Professionals succeed at work.

Finding 2 elements in Array whose sum is x

buyer asked
Medium Priority
Last Modified: 2010-04-01
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)
Watch Question

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

Big hint #1: sort the array.

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

B ekiM

Unlock this solution and get a sample of our free trial.
(No credit card required)

The function FindS , takes the array , the integer x to test , the numbers in the array and a parameter to a structure that will contain the array elements whose sum is x . Function returns true if it founds such integers , else return false.
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;


This is an answer, but WxW locked the question without any answer, just before i could answer!

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.

your answer does have an O(n^2) performance in worst case scenario. that doesn't work

Buyer, it is not ethical for you to ask others to do you work for you.  Nor is it in you best interest.   You can ask for answers to very specific questions and you can have people critue your work, but to have someone do your work is accademically dishonest and grounds for expulsion.


To jhance: Pretty funny but not the answer.
To mikeblas: Also very funny but 2 questions, what name? and why would I want to work for Mickysoft?
To nietod: In the real world you use every resource that is available and if I wanted a lecture I would have talked to my mother.
To WxW and topkapi: Thank you very much.


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


Thanks for the input to the question. Yes I know its worse than n^2. I put that in there to see if I could get something better or close to n^2.
As for any rude comments. I dont think they were rude. Just stating my opinion just like nietod. I needed an answer to a question not a "holyer than thou" lecture. This is the Internet and anyone offended by something like that should seriously consider their presence on it.

>> This is the Internet and anyone offended by something like that should seriously consider their presence on it.

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.


Like I said before, in the real world you use all resources available. Looking at your profile it seems like you should know this. Ive been working in the field for a while now and am going to school at night. All that Im concerened with is getting that piece of paper that says I have a 4 year degree. As for the customer agreement, there is nothing that says I cant post questions like this. Now we could go on for years with what is ethical and what is not but this probably is not the place for it. If you want to discuss that issue furthur then we should probably move it to some newsgroup on Usenet.  
Unlock the solution to this question.
Thanks for using Experts Exchange.

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.


Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.