find four elements in array whose sum equal to a given number X

Question

hello, I need help to find an algorithm that finds:

• four elements in array
• whose sum equal to a given number X
• in O(n^2*log(n))

prefer in pseudo-code or c,c++

thanks moti

Answer 1

Sounds like homework to me. But here's what I'd do.

First sort the numbers (there's your n*log(n)).

Now, create pointers to the list, initialize it with the first 4 numbers. Once you have that, you check the sum of your 4 current numbers with the total. It should be less than or equal to your search sum (if it's not, you can quit early). Now all you need to do is traverse rest of your list alternately replacing your pointers with the current value in the list. This only need to happen once (or really at worst 4 times) so there's your other n, which makes n^2*log(n)

You'll need to keep track of some logic to know if you're over/under your sum and what to do next, but I leave that as your homework assignment.

Answer 2

I'm not going to answer your question completely, since I think it is homework and also think that this is easily done. But I do think that I know why you are having difficulty with an answer, so I will help you out a little bit.

Firstly, you should look into recursion. That means calling a function from within itself.

Second, you should use a helper function, which is called by the function you want to write. This function should take as arguments: - an array of numbers - the length of the array - the value you want find members that sum up to - the number of members of the array that you want to sum up

This function will be called by your other function and passed a 4 for the last argument. It will then call itself adjusting the arguments as it tries to find results by partial trial and error.

edit 2

Upon further thought I realized that this not O(n^2), as I claimed earlier (I mentally glossed over the the middle steps). It is limited by n^4, but may have a lower limit than that due to ample opportunity to short cut in many cases. I do not believe that this short cutting improves it to the point of n^2, though.

Answer 3

You can do it in O(n^2). Works fine with duplicated and negative numbers.

edit as Andre noted in comment, time is with use of hash, which has 'worst case' (although it's less likely than winning in a lottery). But you can also replace hashtable with balanced tree (TreeMap in java) and get guaranteed stable O(n^2 * log(n)) solution.

Hashtable sums will store all possible sums of two different elements. For each sum S it returns pair of indexes i and j such that a[i] + a[j] == S and i != j. But initially it's empty, we'll populate it on the way.

for (int i = 0; i < n; ++i) {
    // 'sums' hastable holds all possible sums a[k] + a[l]
    // where k and l are both less than i

    for (int j = i + 1; j < n; ++j) {
        int current = a[i] + a[j];
        int rest = X - current;
        // Now we need to find if there're different numbers k and l
        // such that a[k] + a[l] == rest and k < i and l < i
        // but we have 'sums' hashtable prepared for that
        if (sums[rest] != null) {
            // found it
        }
    }

    // now let's put in 'sums' hashtable all possible sums
    // a[i] + a[k] where k < i
    for (int k = 0; k < i; ++k) {
        sums[a[i] + a[k]] = pair(i, k);
    }
}

Let's say, X = a[1] + a[3] + a[7] + a[10]. This sum will be found when i = 7, j = 10 and rest = a[1] + a[3] (indexes 1 and 3 will be found from hash)

Answer 4

Abusing the fact that no memory constrain is specified. And using the usual divide and conquer approach.

Number of all permutations for 4 number subsets is C(n,4) and is O(n^4). Number of all permutations for 2 numbers is C(n,2) and is O(n^2). O(n^2) seems to be OK for the task.

1. Input is: an array A with n elements, X.
2. Generate all permutations for 2 number subsets (that's O(n^2)) and put their sums into array B with n^2 elements (also remembering the subsets). Let's denote as S[B[i]] the subset (consisting of the two numbers) whose sum is B[i].
3. Sort the B, O(n^2*log(n^2)).

4. Walk through the array B (O(n^2)) i = [0,n^2) and quick search O(log(n^2)) = O(log(n)) in it for the value (X - B[i]). There might be several of them (but not more than n^2).

   4.1. Walk through all the elements with value of (X - B[i]), using index k.

   4.2. Skip the elements B[k] where S[B[k]] intersects with S[B[i]]. Intersection of two sets with two numbers can be calculated in O(1).

   4.3 If k is the index a element where B[i] + B[k] == X and S[B[k]] doesn't intersect with S[B[i]], then the sum of the sets S[B[k]] and S[B[i]] are the four sought numbers.

Performance is: O( n^2 + n^2*log(n^2) + n^2*log(n^2) ) = O( n^2 * log(n^2) ) = O( n^2 * log(n) )

On step four, when we iterate over the multiple matching elements of B using nested loop. Yet, total number of iterations of the two nested loops is limited by the |B| which is O(n^2). The quick search is not the usual variation but the one which finds the matching element with the lowest index. (Alternatively one can use the usual bsearch and since we might have landed in the middle, use two adjacent loops, checking elements in both directions.)

Answer 5

Like a few other posters, it can be done with a hash in O(n^2)

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <math.h>
#include <map>

using namespace std;

struct Entry
{
   int a;
   int b;
};

int main () {

   typedef vector<int> VI;

   VI l(5);
   l[0] = 1;
   l[1] = 2;
   l[2] = -1;
   l[3] = -2;
   l[4] = 5;
   l[5] = 6;

   sort(l.begin(), l.end());

   int sumTo = 0;

   typedef multimap<int, Entry> Table;

   typedef pair<int,Entry> PairEntry;

   Table myTbl;

   // N
   for (int i = 0; i < l.size(); ++i)
   {
      // N
      for (int j = i+1; j < l.size(); ++j)
      {
         // Const
         int val = l[i] + l[j];

         // A is always less than B
         Entry ent = {i, j};

         myTbl.insert(PairEntry(val,ent));
      }
   }

   pair<Table::iterator, Table::iterator> range;

   // Start at beginning of array
   for (Table::iterator ita = myTbl.begin();
        ita != myTbl.end();
        ++ita)
   {
      int lookFor = sumTo - ita->first;
      // Find the complement
      range = myTbl.equal_range(lookFor);

      // Const bound
      for (Table::iterator itb = range.first;
           itb != range.second;
           ++itb)
      {
         if (ita->second.a == itb->second.a || ita->second.b == itb->second.b)
         {
            // No match
         }
         else
         {
            // Match
            cout << l[ita->second.a] << " " << l[itb->second.a] << " "
                 << l[ita->second.b] << " " << l[itb->second.b] << endl;

            return 0;
         }
      }
   }

   return 0;
}

Answer 6

1) Create an array of all possible pair sums [O(N^2)]

2) Sort this array in ascending order [O(N^2 * Log N)]

3) Now this problem reduces to finding 2 numbers in a sorted array that sum to a given number X, in linear time. Use 2 pointers: a LOW pointer starting from the lowest value, and a HIGH pointer starting from the highest value. If the sum is too low, advance LOW. If the sum is too high, advance HIGH (backwards). Eventually they will find that pair or cross each other (this can be easily proven). This process takes linear time in the size of the array, i.e. O(N ^ 2)

This gives a total time of O(N^2 * log N) as required.

NOTE : This method can be generalized for solving the case of M numbers in O(M * N^(M/2) * log N) time.

-- EDIT --

Actually my response is very similar to Dummy00001's response, except the final lookup, where I use a faster method (though the overall complexity is the same...)

Answer 7

Thanks all, after a couple of hours today i have reached similar answers like you. I don't need all possible 4 numbers, i need only one option. My solution has also O(n^2) place complexity

Answer 8

find four elements in array whose sum equal to a given number X

for me following algorithm works:

Dim Amt(1 To 10) As Long Dim i

For i = 1 To 10 Amt(i) = Val(List1.List(i)) Next i

Dim Tot As Integer Dim lenth As Integer lenth = List1.ListCount

'sum of 4 numbers

For i = 1 To lenth

 For j = 1 To lenth
     For k = 1 To lenth
         For l = 1 To lenth
             If i <> j And i <> k And i <> l And j <> k And j <> l And k <> l Then
                  Debug.Print CBAmt(i) & " , " & CBAmt(j) & " , " & CBAmt(k) & " , " & CBAmt(l)
                  If CBAmt(i) + CBAmt(j) + CBAmt(k) + CBAmt(l) = Val(Text1) Then
                       MsgBox "Found"
                       found = True
                       Exit For
                  End If
                End If
         Next
         If found = True Then Exit For
         Next
         If found = True Then Exit For
    Next
    If found = True Then Exit For
Next