Win a copy of Spark in Action this week in the Open Source Projects forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Bear Bibeault
• Ron McLeod
• Jeanne Boyarsky
• Paul Clapham
Sheriffs:
• Tim Cooke
• Liutauras Vilda
• Junilu Lacar
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Tim Holloway
• fred rosenberger
• salvin francis
Bartenders:
• Piet Souris
• Frits Walraven
• Carey Brown

# Find two elements in an array that sum to k

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.

Ranch Hand
Posts: 47

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

Marshal
Posts: 25668
69
Does the fact that you are given an unsorted array of integers suggest anything?

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

Bartender
Posts: 10777
71

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

lowercase baba
Posts: 12869
62
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: 10777
71

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: 10777
71

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: 10777
71

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