aspose file tools*
The moose likes Beginning Java and the fly likes Find two elements in an array that sum to k Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Find two elements in an array that sum to k" Watch "Find two elements in an array that sum to k" New topic
Author

Find two elements in an array that sum to k

Raihan Jamal
Ranch Hand

Joined: Mar 23, 2010
Posts: 86
Given : An unsorted array A of integers
Input : An integer k

A = {3,4,5,1,4,2}

Input : 6
Output : {5,1}, {4,2}

How can I do this in O(n) or O(log n). Any suggestions will be appreciated.
Sagar Dabas
Ranch Hand

Joined: Nov 15, 2011
Posts: 47



Live Curious!!!
Raihan Jamal
Ranch Hand

Joined: Mar 23, 2010
Posts: 86
If I take this as an array then your code only prints
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18114
    
    8

Does the fact that you are given an unsorted array of integers suggest anything?
rahul sengupta
Greenhorn

Joined: Aug 25, 2011
Posts: 8
Just a little change in the above code and we can have {3,3} also



solution deleted
Sagar Dabas
Ranch Hand

Joined: Nov 15, 2011
Posts: 47

Hmm..... I never read questions correctly..

that means,if the input is :
array : {1,2,3,0,5,4}
sum : 6
then answer should be {1,5} and {2,4}

Did you find this question in any book??
I hope i am wrong but I doubt there can be any solution to this problem with o(n) complexity.....
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7029
    
  16

Raihan Jamal wrote:How can I do this in O(n) or O(log n). Any suggestions will be appreciated.

You might want to look at Henry's solution from your other thread, as a variant of it will provide you with one that works in O(n) time for this one too.

Winston


Isn't it funny how there's always time and money enough to do it WRONG?
Artlicles by Winston can be found here
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10908
    
  12

Please don't provide a solution. We encourage people to figure these things out for themselves. Providing a full blown solution (even a wrong one) doesn't help anyone.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Sagar Dabas
Ranch Hand

Joined: Nov 15, 2011
Posts: 47

I am a student and I get these kind of questions usually in "algorithms" classes...

So, just for knowledge I want to ask can it be done without using collections???

and isn't it that, even for implementing collections like Hashmaps , there are some steps executed backstage which could change O(n) to something else???

Don't know , just being curious.....
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7029
    
  16

Sagar Dabas wrote:I am a student and I get these kind of questions usually in "algorithms" classes...
So, just for knowledge I want to ask can it be done without using collections???

What do you think a "collection" is?

Winston
Sagar Dabas
Ranch Hand

Joined: Nov 15, 2011
Posts: 47

Winston Gutkowski wrote:
What do you think a "collection" is?
Winston


Collections are used to store dynamic types of data or objects. We use collections for storing objects rather than normal primitive types in a structured manner. They got many other uses also.

Algorithms was in my previous semester and we were allowed to use just simple arrays.
Even for list, we had to write steps (not code).....
so i was hoping, this question could have been asked in my last semester exam.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7029
    
  16

Sagar Dabas wrote:Collections are used to store dynamic types of data or objects...

I didn't ask what they store. I asked what they are. Hint: the answer is in the name of your classes last year.

Winston
Sagar Dabas
Ranch Hand

Joined: Nov 15, 2011
Posts: 47

yes, I know they are algorithms....

that's why i wrote:
and isn't it that, even for implementing collections like Hashmaps , there are some steps executed backstage which could change O(n) to something else???


I want to know , how could using hashmap, the efficiency of this question's solution would be just O(n)?

May be there's something I am missing. Would you please elaborate the solution to this problem?

Thanks for your time..
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7029
    
  16

Sagar Dabas wrote:I want to know , how could using hashmap, the efficiency of this question's solution would be just O(n)?

What's the efficiency of a HashMap retrieval, and how long does it take to traverse an array? In fact, it would probably be closer to O(4n), but since there is no power or log involved, it's still written as O(n).

Winston

 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Find two elements in an array that sum to k
 
Similar Threads
Studied for 17 days - Passed - 84%
passed SCWCD - 95%
NX:Exceptions
help
Convert C code in Java