Add each number in array to every other number in array

Question

How can I add every object, which is an NSNumber object to every other NSNumber object in the array and add the sum object to a new array?

e.g.

array1 has numbers 1, 2, and 3.
then do:
1 + 1 = 2 then add 2 to array2.
1 + 2 = 3 then add 3 to array2.
1 + 3 = 5 then add 4 to array2.

2 + 1 = 3 then add 3 to array2.
2 + 2 = 4 then add 4 to array2.
2 + 3 = 5 then add 5 to array2.

3 + 1 = 4 then add 4 to array2.
3 + 2 = 5 then add 5 to array2.
3 + 3 = 6 then add 6 to array2.

So array2 has 2, 3, 4, 3, 4, 5, 4, 5, 6.

I can handle the removal of the duplicates. I've tried putting a for loop within another for loop which would essentially do what I had outlined above but I have over 28,000 numbers which are not the numbers 1 - 28,000. It took over a very long time to compute since there are 28,000^2 possible sums. Surely there must be another way. Can anyone please elaborate?

So you're saying you can't have duplicates? That would make a big difference in the algorithm — Merlevede
– Merlevede, Commented Feb 22, 2014 at 8:34
@Merlevede It doesn't matter for me. Duplicates are ok, as long as it doesn't take like three hours. — Milo
– Milo, Commented Feb 22, 2014 at 8:45
I meant show your code. Did you think about multi-threading? Why are you trying this on a mobile device?? — Wain
– Wain, Commented Feb 22, 2014 at 9:29

Amin Negm-Awad · Accepted Answer · 2014-02-22 09:06:37Z

1

If you have a set of N random numbers and have to add each to each other, I would not be sure that this is not O(N²).

Computing all numbers leads to 784.000.000 sums before uniquing them. Using 32 bit integers (not NSNumber instance objects) the memory footprint would be almost 3 GB.

You have to implement this lazy ("every sum on demand")

answered Feb 22, 2014 at 9:06

Amin Negm-Awad

16.7k3 gold badges39 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Merlevede Over a year ago

Good point. Suppose you do this algorithm for consecutive numbers 1..100. There are 49 combinations with result=100. If results are added on a Dictionary or a collection that strips duplicates the amount of memory could be drastically improved, but maybe the lookup time is a drawback.... just some thaughts!

Amin Negm-Awad Over a year ago

Yes, with a different problem a different solution is possible. "I have over 28,000 numbers which are not the numbers 1 - 28,000." However, doing close to 1 G calculations and object creations is that slow that obvious ricks like "reducing it a bit" would not work.

Merlevede · Accepted Answer · 2014-02-22 09:15:34Z

0

Something like this, maybe

NSMutableArray *myNewArray = [NSMutableArray array];
NSUInteger length = myArray.length;  // or size?? I don't remember 
for (NSUinteger i=0; i=0<length; i++)
    for (NSUinteger j=i; j=0<length; j++)
        [myNewArray addObject:([array objectAtIndex:i] + [array objectAtIndex:j])];

Here the secret is the initial condition in the inner for loop j=i. For example, since you have already done the sum for 1+2 you don't need to do 2+1 anymore, hence duplicates are not included, although you could still have duplicate results (e.g. 3+4 = 7; 1+6 = 7).

Instead of having n^2 sums, you have n*(n+1)/2 sums... almost half of it!

edited Feb 22, 2014 at 9:15

answered Feb 22, 2014 at 8:29

Merlevede

8,1781 gold badge26 silver badges40 bronze badges

1 Comment

Milo Over a year ago

Thanks, I'll try this right now. Also, in the last line of your code, do you mean to have one of the objectAtIndex:i to be objectAtIndex:j? BTW it's myArray.count :)

Collectives™ on Stack Overflow

Add each number in array to every other number in array

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related