Solved

Finding 2 elements in Array whose sum is x

Posted on 1998-06-13
12
375 Views
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)
0
Comment
Question by:buyer
  • 3
  • 3
  • 2
  • +3
12 Comments
 
LVL 32

Expert Comment

by:jhance
ID: 1165841
Homework problem?  Nah, couldn't be that, you must have a job where they give you problems like this.
0
 
LVL 11

Expert Comment

by:mikeblas
ID: 1165842
Big hint #1: sort the array.

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

B ekiM


0
 
LVL 6

Accepted Solution

by:
WxW earned 250 total points
ID: 1165843
Answer in comment below...
0
 
LVL 6

Expert Comment

by:WxW
ID: 1165844
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;
      }

                        

0
 

Expert Comment

by:topkapi
ID: 1165845
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.
0
 

Expert Comment

by:topkapi
ID: 1165846
WxW:
your answer does have an O(n^2) performance in worst case scenario. that doesn't work
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 22

Expert Comment

by:nietod
ID: 1165847
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.
0
 

Author Comment

by:buyer
ID: 1165848
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.
0
 

Expert Comment

by:topkapi
ID: 1165849
buyer:

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
0
 

Author Comment

by:buyer
ID: 1165850
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.
0
 
LVL 22

Expert Comment

by:nietod
ID: 1165851
>> 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.
0
 

Author Comment

by:buyer
ID: 1165852
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.  
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

920 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now