Win a copy of Functional Reactive Programming this week in the Other Languages forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Find two elements in an array that sum to k

 
Raihan Jamal
Ranch Hand
Posts: 86
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
C++ Java PHP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
 
Raihan Jamal
Ranch Hand
Posts: 86
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If I take this as an array then your code only prints
 
Paul Clapham
Sheriff
Posts: 21416
33
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Does the fact that you are given an unsorted array of integers suggest anything?
 
rahul sengupta
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Just a little change in the above code and we can have {3,3} also



solution deleted
 
Sagar Dabas
Ranch Hand
Posts: 47
C++ Java PHP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 10527
64
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
C++ Java PHP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 10527
64
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
C++ Java PHP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 10527
64
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
C++ Java PHP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 10527
64
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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

 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic