Solved

Finding 2 elements in Array whose sum is x

Posted on 1998-06-13
12
377 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
Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
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
 
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

Networking for the Cloud Era

Join Microsoft and Riverbed for a discussion and demonstration of enhancements to SteelConnect:
-One-click orchestration and cloud connectivity in Azure environments
-Tight integration of SD-WAN and WAN optimization capabilities
-Scalability and resiliency equal to a data center

Question has a verified solution.

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

Suggested Solutions

This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
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 be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

860 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