Algorithm for searching an array for 5 elements which sum to a value

user_12384830 0
Viewed 494

[I asked lately a similar question, Search unsorted array for 3 elements which sum to a value and got wonderful answers, thank you all! :)]

I need your help for solving the following problem:
I am looking for an algorithm, the time-complexity must be ϴ( n³ ).

The algorithm searches an unsorted array (of n integers) for 5 different integers
which sum to a given z.

E.g.: for the input: ({2,5,7,6,3,4,9,8,21,10} , 22)

the output should be true for we can sum up 2+7+6+3+4=22

(the sorting doesn't really matter. The array can be sorted first without affecting the complexity.

So you can look at the problem as if the array is already sorted.)

-No memory constraints-

-We only know that the array elements are n integers.-

Any help would be appriciated.

big-o time-complexity search arrays algorithm
1 Answers

Algorithm:

1) Generate an array consisting of pairs of your initial integers and sort it. That step will take O(n^2 * log (n^2)) time.

2) Choose a value from your initial array. O(n) ways.

3) Now you have a very similar problem to the linked one. You have to choose two pairs such that their sum will be equal to z - chosen value. Thankfully, you have an array of all pairs, already sorted, of length O(n^2). Finding such pairs should be straightforward -- same thing you did in a 3 integer sum problem. You make two pointers and move both of them O(n^2) times in total.

O(n^3) total complexity.

You may get into some problems with finding pairs that consist of your chosen value. Skip every pair that consists of your chosen value (just move the pointer further when you reach such a pair like it never existed).

Let's say that you have two pairs, p1 and p2, such that sum(p1) + sum(p2) + chosen value = z. If all of the integers in p1 and p2 are different, you have the solution. If not, that's where it gets a little bit messy.

Let's fix p1 and check the next value after p2. It may have the same sum as p2 since two different pairs can have same sum. If it does, definitely you will not have the same collision with p1 as you had with p2, but you may get a collision with the other integer of p1. If so, check the second value after p2, if it also has the same sum -- it definitely won't have any collision with p1.

So assuming that there are at least 3 pairs with same sum as p1 or p2, you will always find a solution checking 3 values for fixed p1 or checking 3 values for fixed p2.

The only possibility left is that there are less than 3 pairs with same sum as p1 and there are less than 3 pairs with same sum as p2. You can choose them in up to 4 ways -- just check each possibility.

It is a bit unpleasant, but in constant amount of operations you are able to handle such problems. That means the total complexity is O(n^3).

user_72014200
Related