Thanks and Regards, Pradeep Kumar
SCJP 1.6, SCWCD 5.0
Thanks and Regards,
Suhas
http://www.xplore-java.blogspot.com/
When you do things right, people won't be sure you've done anything at all.
Thanks and Regards, Pradeep Kumar
SCJP 1.6, SCWCD 5.0
When you do things right, people won't be sure you've done anything at all.
Pradeep Kumar wrote:
1. I have 200 numbers ranging from from 1 to 50. more than one number can be found i.e 1 can be repeated 4 times etc.
Misha van Tol wrote:I think the objective of the puzzle is to print only the pairs (1+49, 2+48...) right?
Thanks and Regards, Pradeep Kumar
SCJP 1.6, SCWCD 5.0
David Newton wrote:
Misha van Tol wrote:I think the objective of the puzzle is to print only the pairs (1+49, 2+48...) right?
Not according to the original problem statement, which says nothing about any limit on how many numbers to print for each sum.
Personally, I'd use a boolean array rather than a TreeSet.
Thanks and Regards, Pradeep Kumar
SCJP 1.6, SCWCD 5.0
Reiner Herman wrote:Hallo,
your algorithm for the problem seems to have time complexity O(N*logN) if the number of integres is N. For your specific small input the complexity is of course not important but for the general problem it is probably nice to look for something faster. I think you should be able to get down to O(N) using bucket sort and doing the checking of existence of pairs summing to 50 in a more efficeint way (When the integers are sorted look at the sum of the smallest and largest integers. Too small --> Look at sum of next smallest and greatest. Too big ---> look at sum of smallest and second largest . Equal --> output pair and move look at second smallest and second largest . ...
for example 1+49 make one combination and should print only once.
Reiner Herman wrote:your algorithm for the problem seems to have time complexity O(N*logN) if the number of integres is N.
for example 1+49 make one combination and should print only once.
Thanks and Regards, Pradeep Kumar
SCJP 1.6, SCWCD 5.0
Mike Simmons wrote:
Personally, I'd use a boolean array rather than a TreeSet.
Thanks and Regards, Pradeep Kumar
SCJP 1.6, SCWCD 5.0
Mike Simmons wrote:It seems we still have some different interpretations of the problem. I see this in the original problem statement:
for example 1+49 make one combination and should print only once.
I interpret the "only once" to mean only once, even if either 1 or 49 appear multiple times in the input. Otherwise, why say "only once" at all? Under this interpretation, duplicates in the input are merely distractions to be eliminated. That's why Pradeep is using a TreeMap, and I am using a boolean array. If we do need to count duplicates in the input as separate entities to be considered, then that leads to slightly more complex solutions such as Ryan describes. I don't know which interpretation is more accurate; it seems like a fairly dull problem either way.
Ryan McGuire wrote:
However, I'm sure a boolean array works. ..
Thanks and Regards, Pradeep Kumar
SCJP 1.6, SCWCD 5.0
Ryan McGuire wrote:However, I'm sure a boolean array works. How can you tell the difference between zero, one and two occurences of 25 in the input?
Pradeep wrote:Can you please explain ow would you use a Boolean array to execute this problem domain.
fundoo anshu wrote:I doubt you are getting complexity as O(N). May be in this case you have already assume that thr are only 25 combinations possible and you are gonna hardcode it out. in that case. yes, you will have O(N) but I don't think you should hardcode it out. Correct me in case I got you wrong.
fundoo anshu wrote:Regarding the Object Pool -
I believe you wanna implement a fixed size reusable Object Pool. In that case you must use an array.
If you want to use not-reusable growing object pool. Go for link list.
Thanks and Regards, Pradeep Kumar
SCJP 1.6, SCWCD 5.0
Thanks and Regards, Pradeep Kumar
SCJP 1.6, SCWCD 5.0
Thanks and Regards, Pradeep Kumar
SCJP 1.6, SCWCD 5.0
Mike Simmons wrote:
Ryan McGuire wrote:However, I'm sure a boolean array works. How can you tell the difference between zero, one and two occurences of 25 in the input?
Did you mean you're not sure a boolean array works?
Here's one possible implementation:
Consider Paul's rocket mass heater. |