Win a copy of Spark in Action this week in the Open Source Projects forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
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
  • 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.
 
Ranch Hand
Posts: 47
PHP C++ Java
  • 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
 
Marshal
Posts: 25668
69
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?
 
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
PHP C++ Java
  • 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.....
 
Bartender
Posts: 10777
71
Hibernate Eclipse IDE 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
 
lowercase baba
Posts: 12869
62
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
PHP C++ Java
  • 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
Posts: 10777
71
Hibernate Eclipse IDE 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
PHP C++ Java
  • 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
Posts: 10777
71
Hibernate Eclipse IDE 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
PHP C++ Java
  • 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
Posts: 10777
71
Hibernate Eclipse IDE 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

 
Straws are for suckers. Now suck on this tiny ad!
Thread Boost feature
https://coderanch.com/t/674455/Thread-Boost-feature
    Bookmark Topic Watch Topic
  • New Topic