Find Four Elements in Array Whose Sum Equal to a Given Number X

Find a pair of elements from an array whose sum equals a given number

# Let arr be the given array.
# And K be the give sum

for i=0 to arr.length - 1 do
  # key is the element and value is its index.
  hash(arr[i]) = i  
end-for

for i=0 to arr.length - 1 do
  # if K-th element exists and it's different then we found a pair
  if hash(K - arr[i]) != i  
    print "pair i , hash(K - arr[i]) has sum K"
  end-if
end-for

From 4 given arrays(not sorted), find the elements from each array whose sum is equal to some number X

a kind of dynamic programming approach.

initialize sums (a dict of the form {possible_sum0: [way_to_get_sum0, ...]}) with the first list A. this results in

sums = {0: [[0]], 100: [[100]], -100: [[-100]], 50: [[50]], 200: [[200]]}

the update that dictionary with the lists B and C. sums will now contain entries like

sums = {..., 
        30: [[0, 30, 0]], 
        50: [[0, 30, 20], [50, 0, 0]], 
        29: [[0, 30, -1]], ...}

then in find_sum i sort the last list D and the sums for some speedup and break if a give sum X is no longer accessible.

here is the code:

from collections import defaultdict

A = [0, 100, -100, 50, 200]
B = [30, 100, 20, 0]
C = [0, 20, -1, 80]
D = [50, 0, -200, 1]

def initialize_sums(lst):
    return {item: [[item]] for item in lst}

def update_sums(sums, lst):
    new_sums = defaultdict(list)
    for sm, ways in sums.items():
        for item in lst:
            new_sum = sm + item
            for way in ways:
                new_sums[new_sum].append(way + [item])
    return new_sums

def find_sum(sums, last_lst, X):
    last_lst = sorted(last_lst)
    ret = []
    for sm, ways in sorted(sums.items()):
        for item in last_lst:
            x = sm + item
            if x > X:
                break
            if x == X:
                for way in ways:
                    ret.append(way + [item])
                break
    return ret

sums = initialize_sums(lst=A)
sums = update_sums(sums, lst=B)
sums = update_sums(sums, lst=C)

ret = find_sum(sums, last_lst=D, X=0)
print(ret)
# [[-100, 30, 20, 50], [0, 0, -1, 1], [-100, 100, -1, 1], ...]

...did not analyze the overall complexity though.

Find Exactly four integers from array that sum up to given N and the integers needs to maximize their end product

• Compute the sums of every pair and its product
• Sort it by sum
• For every pair that sum X, find the one that sums N - X with the highest product
• Store the product of the 2 pairs as max between that and previous max
• Once done, display max product

Complexity: O(n^2 * 2 log n).

Pair of elements from a specified array whose sum equals a specific target number

that map value you're seeing is a lookup table and that twoSum method has implemented what's called Dynamic Programming

In Dynamic Programming, you store values of your computations which you can re-use later on to find the solution.

Lets investigate how it works to better understand it:

twoSum([10,20,40,50,60,70], 50)
//I removed one of the duplicate 10s to make the example simpler

In iteration 0:

value is 10. Our target number is 50. When I see the number 10 in index 0, I make a note that if I ever find a 40 (50 - 10 = 40) in this list, then I can find its pair in index 0.

So in our map, 40 points to 0.

In iteration 2:

value is 40. I look at map my map to see I previously found a pair for 40.

map[nums[x]] (which is the same as map[40]) will return 0.

That means I have a pair for 40 at index 0.
0 and 2 make a pair.

---

Does that make any sense now?

Unlike in your solution where you have 2 nested loops, you can store previously computed values. This will save you processing time, but waste more space in the memory (because the lookup table will be needing the memory)

Also since you're writing this in javascript, your map can be an object instead of an array. It'll also make debugging a lot easier ;)

Finding a testcase which fails the code in the 4 sum problem

The algorithm is correct. Consider a quadruple (a, b, c, d) which satisfies the following: (1) arr[a] + arr[b] + arr[c] + arr[d] == k; (2) a < b < c < d.

It is obvious that four distinct element of the array sum to k if and only if such quadruple (a, b, c, d) exists.

Now consider the pair (a, b). You have mentioned the program records the last pair (e, f) (e < f) that is a compliment of (a, b) (i.e. arr[a] + arr[b] + arr[e] + arr[f] == k). Note that since (e, f) is the last pair with such property, so e >= c. Therefore a < b < e < f. Now we have found a valid quadruple (a, b, e, f).

Since the second loop traverse through all pairs, the pair (a, b) must have been visited, and the quadruple must have been detected. Therefore the algorithm is correct.

---

Related Topics