Problem of sum in an array

[Jeka]

Hi, I have a problem and can't get a solve for it.
So this is a problem :

Input: array ordered in growed order and number S
Output: are there two numbers in an array that their sum is equal to S.

The simple way to solve it is by two loops, but in this case program will make about n^2 operation. My task is to solve this problem in n operations.
So if there anybody that can do that please help me...

 

[jamisar]

post the code! -----------
when they don't ask you anymore, where they are come from, and they don't tell you anymore, where they go ... you'r getting older !

 

[marsd]

Here is an example program that does what you ask,ignore
the function pointer if you want, I was testing a compiler setting with it.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAGIC 15

int *makeArray(int, void (*)(int *,int));
void populateArray(int *, int);


int main(void) {
int y,max = 0;
int *pre;
void (*method)(int *,int);
method = populateArray;

pre = makeArray(120,method);

for (y=0 ; y <= 120 ; y++) {
/*printf(&quot;%d\n&quot;, pre[y]);*/
if (pre[y] == MAGIC) {
max++;
}
}
if (max >= 2) {
printf(&quot;Yes: %d\n&quot;, max);
}
free(pre);
return 0;
}

int *makeArray(int num, void(*handler)(int *array,int num_a)) {
int *myarray = malloc(num * sizeof(int));

if (myarray) {
handler(myarray,num);
return myarray;
}
return NULL;
}

void populateArray(int *arr, int n) {
time_t ptr;
int y = 0;

time(&ptr);
srand(ptr);

while (y++ <= n) {
arr[y] = (1 + rand() % n);
}
}

 

[vlakas1981]

i could propose a very general thought:
since the array is ordered, you can use the &quot;divide and conquer&quot; approach. Given S, split the array in the middle and check the number that is there (in the middle of the array). if it is bigger than s, take the part of the array that is before the place you split it and do the same. if it is smaller take the part of the array that is after the place you split it and do again the same. go on until you find the number closest possible to s. then check only the part of the array that remains before this number. this will take down the complexity of the algorithm to something like nlogn which is better than n^2.
hope this helps!

 

[aphrodita]

to vlakas1981:

Consider this sequence: 1,3,5,8,15,20,21,27 and number S = 26, which is the sum of 5 and 21 that are in the opposite halves of the array if you divide it your way.

Jeka
it will be worth to check if the sequence is in superincreasing order. That will solve your problem very fast, with the complexity of n. A superinscreasing sequence is when next element of it is bigger than the sum of all preceeding it. If that is the case, compare your S with all the elements until you find the two you are looking for in this manner:

- Check if the biggest element in the sequence is bigger than the sum, if it is, then it is not one of the two numbers. If it's less, then it is one of them.
- Proceed to the element coming before the biggest till you find the numbers.

This is called an easy knapsack problem.

Quoting...
With non-sperincreasing knapsacks, there is no quick algorithm. The only way to determine which items are in the knapsack in to methodically test possible solutions until you stumble on the correct one.

(The quote is taken from &quot;Applied Cryptography&quot; by Bruce Schneier.)

The solution they are talking about is having two loops for two numbers, which gives the complexity of n^2.

I have not go deep into what marsd code does, for it did not compile on my machine, please explain it. Best Regards,

aphrodita@mail.krovatka.ru {uiuc rules}

http://www.hellforge.org

 

[PieterWinter]

Just a thought:

Given
1. The array is ordered low to high
2. The function returns true or false

Set startIndex and endIndex on start and end of array
while startIndex != endIndex
sum = array[startIndex]+array[endIndex]
if (sum == S) return true;
if (sum < S) startIndex++
else endIndex--;
return false

 

[lionelhill]

I'm not sure if I'm understanding correctly.
(1) the aim is to find 2 numbers from an array such that they add up to a given number? The array is ordered?

(2) If so, then you can cut a lot of corners. For instance, if the largest number in the array is bigger than the number you are looking for, then you can cut off the end of the array (assuming negative numbers aren't allowed). Similarly, if the last number is 25, but you're looking for 35, then you can ignore the start of the array up to 10.

This quickly turns into quite a nice method, alternating looking at start and end of array.

If the &quot;10&quot; didn't exist, then &quot;25&quot; won't do. Now we look at the number before 25. Say it's 20. Now we need a &quot;first&quot; number of 15 or better. So we go back to first position (where we failed to find &quot;10&quot and scan forwards looking for 15.

I'd have thought we only traverse the array once that way, starting at each end and moving two pointers alternately inwards. I haven't analysed this properly, but that shouldn't be much worse than linear.

Am I writing rubbish?

 

[PieterWinter]

Hi lionelhill,

That was what I was proposing

 

[lionelhill]

Hi Pieter,

oh, I'm so sorry! I got so caught up in the knapsacks that I failed to notice your concise, neat reply and implementation. Ooops!

Incidentally, it may be possible to do Better than linear time by combining this approach with the divide-and-conquer mentioned above. Rather than scanning one number at once from each end of the array, you could make binary jumps to half-way points back and forth to search out the next necessary number to make up the sum (as you normally would in doing a search for a particular number in an ordered list). Wot do you reckon? (much more complicated to implement though).

Lionel

 

[aphrodita]

PieterWinter

Your method has a complexity of n^2 as well. Rather going from the beginning of the sequence like one would do in 2 nested loops, you go from behind, which is absolutely the same. Best Regards,

aphrodita@mail.krovatka.ru {uiuc rules}

http://www.hellforge.org

 

[lionelhill]

No, this method is not N-squared. It loops through the data a single time (no number in the array is visited more than once), and has a single loop. The original solution is N-squared because of the nesting, which doesn't exist in Pieter's solution.

Also Pieter's solution isn't just a work-from-behind version of the original: it alternates working forwards and backwards. (note the startindex++ as well as the endindex--)

If any doubt remains, try timing it with various array-lengths.

Also try writing out an array on paper, and try both methods with a pencil and calculator. Pieter's method works very quickly on even quite big arrays.

Hope this makes things clearer. I still have a feeling it could be done on average in better than linear time, because there's no absolute need in all cases to visit all numbers.

 

[vlakas1981]

to aphrodita (and everyone else):

my proposition does not have any problem with your array, it will just not have such a good performance. I use divide and conquer until i find the number closest to the given one. Afterwards, i scan the array from that point down. In your case, after finding 27 i stop, and use the rest of the array (in this case the whole of it) to scan for the numbers. This is not the best algorithm, i suppose, but it is working fine, and gives many times a good performance (not all cases are like your example).