Solved

Finding 2 elements in Array whose sum is x

Posted on 1998-06-13
12
378 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
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
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

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

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

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

733 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