Win a copy of Functional Reactive Programming this week in the Other Languages forum!

# Find two elements in an array that sum to k

Raihan Jamal
Ranch Hand
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
Posts: 47

Raihan Jamal
Ranch Hand
Posts: 86
If I take this as an array then your code only prints

Paul Clapham
Sheriff
Posts: 21416
33
Does the fact that you are given an unsorted array of integers suggest anything?

rahul sengupta
Greenhorn
Posts: 8
Just a little change in the above code and we can have {3,3} also

solution deleted

Sagar Dabas
Ranch Hand
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
Posts: 10527
64
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

fred rosenberger
lowercase baba
Bartender
Posts: 12198
35
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.

Sagar Dabas
Ranch Hand
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
Posts: 10527
64
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
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
Posts: 10527
64
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
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?

Winston Gutkowski
Bartender
Posts: 10527
64
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