Solved

Finding 2 elements in Array whose sum is x

Posted on 1998-06-13
12
374 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
Comment Utility
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
Comment Utility
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
Comment Utility
Answer in comment below...
0
 
LVL 6

Expert Comment

by:WxW
Comment Utility
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
Comment Utility
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
Comment Utility
WxW:
your answer does have an O(n^2) performance in worst case scenario. that doesn't work
0
Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

 
LVL 22

Expert Comment

by:nietod
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
>> 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
Comment Utility
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

Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

Join & Write a Comment

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…
Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
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 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.

763 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

11 Experts available now in Live!

Get 1:1 Help Now