Find four elements in the array whose sum is equal to the given number X

Question

I need help to find an algorithm that finds:

• four elements in an array
• the sum of which is equal to the given number X
• in O (n ^ 2 * log (n))

preferred in pseudocode or c, c ++

Answer 1

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

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

Hashtable sums save all possible sums of two different elements. For each sum S it returns a pair of indices i and j such that a[i] + a[j] == S and i != j But initially it is empty, we will fill it along 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 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 amount will be found when i = 7 , j = 10 and rest = a[1] + a[3] (indices 1 and 3 will be found from the hash)

Answer 2

Like some other posters, this 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 3

Violation of memory limit not specified. And using the usual approach to separation and conquest.

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

• Input: array A with elements n , X
• Generate all permutations for 2 subsets of numbers (which is O (n ^ 2)) and put their sums in array B with n ^ 2 elements (also remembering the subsets). Denote by S[B[i]] subset (consisting of two numbers) whose sum is B[i] .
• Sort B , O (n ^ 2 * log (n ^ 2)).

• Go through the array B (O (n ^ 2)) i = [0,n^2) and quickly search O(log(n^2)) = O(log(n)) in it for the value (X - B[i]) . There may be several of them (but no more than n ^ 2).

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

  4.2. Skip items B[k] , where S[B[k]] intersects S[B[i]] . The intersection of two sets with two numbers can be calculated in O (1).

  4.3 If k is an index, then the element where B[i] + B[k] == X and S[B[k]] does not intersect S[B[i]] , then the sum of the sets S[B[k]] and S[B[i]] are the four numbers sought.

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

In step 4, when we iterate over several matching elements of B using a nested loop. However, the total number of iterations of two nested loops is limited to |B| which is equal to O (n ^ 2). A quick search is not an ordinary option, but one that finds the corresponding element with the lowest index. (Alternatively, you can use regular bsearch , and since we could land in the middle, use two adjacent loops, checking the elements in both directions.)

Answer 4

A working algo Java solution. provided by Nikita Fisher above ..

 // find four numbers in an array such that they equals to X class Pair{ int i; int j; Pair(int x,int y){ i=x; j=y; } } public class FindNumbersEqualsSum { public static void main(String[] args) { int num[]={1,2,3,4,12,43,32,53,8,-10,4}; get4Numbers(num, 17); get4Numbers(num, 55); } public static void get4Numbers(int a[],int sum){ int len=a.length; Map<Integer, Pair> sums = new HashMap<Integer, Pair>(); for (int i = 0; i < len; ++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 < len; ++j) { int current = a[i] + a[j]; int rest = sum - 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.containsKey(rest)) { // found it Pair p = sums.get(rest); System.out.println(a[i]+" + "+a[j]+" + "+a[pi] +" + "+a[pj]+" = "+sum); } } // now let put in 'sums' hashtable all possible sums // a[i] + a[k] where k < i for (int k = 0; k < i; ++k) { sums.put(a[i] + a[k],new Pair(i, k)); } } } } Result: 4 + 8 + 3 + 2 = 17 8 + 4 + 4 + 1 = 17 43 + 8 + 3 + 1 = 55 32 + 8 + 12 + 3 = 55 8 + -10 + 53 + 4 = 55 -10 + 4 + 8 + 53 = 55 

Answer 5

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 boils down to finding 2 numbers in a sorted array that are summed with a given number X in linear time. Use 2 pointers: a LOW pointer starting at the lowest value, and a HIGH pointer starting at the highest value. If the amount is too low, promote LOW. If the amount is too high, push HIGH (back). In the end they will find a pair or cross each other (this is easy to prove). This process takes linear time in the size of the array, i.e. O (N ^ 2)

This gives the total time O (N ^ 2 * log N) as needed.

NOTE This method can be generalized to solve the case of M numbers in O (M * N ^ (M / 2) * log N) times.

- EDIT -

Actually my answer is very similar to Dummy00001's answer, except for the final search, where I use the faster method (although the overall complexity is the same ...)

Answer 6

I like homework. But here is what I will do.

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

Now create pointers in the list, initialize it with the first 4 numbers. Once you do this, you will check the sum of your 4 current numbers with a total. It should be less than or equal to your search sum (if not, you can exit earlier). Now all you have to do is move the rest of your list, alternately replacing the pointers with the current value in the list. This is only needed once (or really 4 times in the worst case), so there will be your other n, which makes n ^ 2 * log (n)

You will need to keep track of some logic to find out if you have run out / under your amount and what to do next, but I leave it as your homework.

Answer 7

I will not fully answer your question, as I think this is homework, and also think that it is easy to do. But I think I know why you had difficulty answering, so I will help you a little.

First, you should study recursion. This means calling the function from the inside.

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

This function will be called by your other function and passed 4 for the last argument. Then he will call himself a correction of the arguments, as he tries to find the results by partial verification and error.

change 2

Thinking, I realized that this is not O (n ^ 2), as I stated earlier (I mentally ignored the middle steps). It is limited to n ^ 4, but may have a lower limit than that, due to the extensive possibility of short circuiting in many cases. I do not think that this short cut improves it to the point n ^ 2.

Answer 8

to find four elements in the array whose sum is equal to the given number X, the following algorithm works for me:

 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 

Answer 9

I wrote an O (N ^^ 2) time function that does not use hashtables but handles negative numbers and duplicates numbers, obviously OK. I process negative numbers in an integer array by adding a large postive number (e.g. 100) to all integers in the array. Then I set the target to target += (4 * 100) . Then, when I find the result, I subtract 100 from the integers in the result. Here is my code and test cases: Please let me know if this is time complexity o (N ^^ 2).

 struct maryclaranicholascameron{ int sum; int component1; int component2; }; void Another2PrintSum(int arr[], int arraysize, int target){ int i(arraysize -1); int j(arraysize -2); int temp(target); int temp2(0); int m(0); int n(0); int sum(0); int original_target(target); for (int ctr = 0; ctr < arraysize; ctr++){ sum += arr[ctr]; } for (int ctrn = 0; ctrn < arraysize; ctrn++){ arr[ctrn] += 100; } maryclaranicholascameron* temparray = new maryclaranicholascameron[sum + (arraysize *100)]; memset(temparray, 0, sizeof(maryclaranicholascameron) * (sum + 400)); for (m = 0; m < arraysize; m++){ for (n = m + 1; n < arraysize; n++){ temparray[arr[m] + arr[n]].sum = arr[m]+ arr[n]; temparray[arr[m] + arr[n]].component1 = m; temparray[arr[m] + arr[n]].component2 = n; } } target += (4 * 100); original_target = target; bool found(false); while (i >= 0 && i < arraysize && found == false){ target -= (arr[i]); while(j >= 0 && j < arraysize && found == false){ temp2 = target; target -= (arr[j]); if (i != j && temparray[target].sum == target && temparray[target].sum != 0 && temparray[target].component1 != i && temparray[target].component2 != i && temparray[target].component1 != j && temparray[target].component2 != j){ printf("found the 4 integers i = %dj = %dm = %dn = %d component1 = %d component = %di %dj %d\n", arr[i] - 100, arr[j] - 100, arr[temparray[target].component1] - 100, arr[temparray[target].component2] - 100, temparray[target].component1, temparray[target].component2, i, j); found = true; break; } j -= 1; target = temp2; } i -= 1; j = i; target = original_target; } if (found == false){ printf("cannot found the 4 integers\n"); } delete [] temparray; } // test cases int maryclaranicholas[] = {-14,-14,-14,-14,-12 ,-12, -12 ,-12 ,-11, -9,-8,-7,40}; Another2PrintSum(maryclaranicholas, 13,-2}; int testarray[] = {1,3,4,5,7,10}; Another2PrintSum(testarray, 6, 20); 

Answer 10

This problem can be reduced to finding all combinations of length 4. For each combination obtained, we sum the elements and check whether it is equal to X.

Answer 11

This problem can be taken as a variation of the identity of pascals,

here is the full code:

Sorry, as the code is in java:

 public class Combination { static int count=0; public static void main(String[] args) { int a[] = {10, 20, 30, 40, 1, 2,4,11,60,15,5,6}; int setValue = 4; getCombination(a, setValue); } private static void getCombination(int[] a, int setValue) { // TODO Auto-generated method stub int size = a.length; int data[] = new int[setValue]; createCombination(a, data, setValue, 0, 0, size); System.out.println(" total combinations : "+count); } private static void createCombination(int[] a, int[] data, int setValue, int i, int index, int size) { // TODO Auto-generated method stub if (index == setValue) { if(data[0]+data[1]+data[3]+data[2]==91) { count ++; for (int j = 0; j < setValue; j++) System.out.print(data[j] + " "); System.out.println(); }return; } // System.out.println(". "+i); if (i >= size) return; // to take care of repetation if (i < size - 2) { while (a[i] == a[i + 1]) i++; } data[index] = a[i]; // System.out.println(data[index]+" "+index+" ....."); createCombination(a, data, setValue, i + 1, index + 1, size); createCombination(a, data, setValue, i + 1, index, size); } 

}

Input Example :

 int a[] = {10, 20, 30, 40, 1, 2,4,11,60,15,5,6}; 

Output :

 10 20 1 60 10 30 40 11 10 60 15 6 20 30 40 1 20 60 5 6 30 40 15 6 11 60 15 5 total combinations : 7