Three Set Sum: Given an integer k and 3 sets A, B and C, find a, b, c such that a + b + c = k

Question

You are given an integer k and 3 sets A, B and C, each containing n numbers.  Give an efficient algorithm to determine if there exist 3 integers a, b, c (in sets A, B, C respectively), such that a + b + c = k.  The time complexity of your algorithm should be O(n²) or better.

Answer 1

1.Add each two values of the first two arrays and insert the value into a map. O(n^2).

2.Find if there is a value in the third array matches with the map.O(2n).

Code:

public void findvalue(int[] a,int[] b,int[] c,int value){
    Map<Integer,Integer> map = new HashMap<>();
    for (int i=0;i<a.length;i++){
        for (int j=0;j<b.length;j++){
            int sum = a[i]+b[j];
            map.put(sum, 1);
        }
    }

    int result = 0;

    for (int i=0;i<c.length;i++){
        int define = map.getOrDefault(value-c[i], 0);
        if (define==1) {
            result = 1;
            break;
        }
    }

    if (result == 1) {
        System.out.println("There exist such triple numbers.");
    } else {
        System.out.println("No such triple numbers be found.");

    }
}

The time complexity would be O(n^2).

Answer 2

sorted A,B,C, 3nlogn

a in A, b in B, c in C

if a+b+c<k

a+=1, n

if a+b+c>k

check, 3n

no worse case

totally 3nlogn

Answer 3

Given sets A, B, C of size n each and integer k, determine if there exist a, b, c (a ∈ A, b ∈ B, c ∈ C) such that 

a + b + c = k

Divide and Conquer Algorithm:

Divide If n = 1, directly check if a + b + c = k

If n > 1, split A, B, C into halves: A1, A2 = split(A) B1, B2 = split(B) C1, C2 = split(C)

Conquer Recursively solve 8 subproblems:

T(A1, B1, C1, k)

T(A1, B1, C2, k)

T(A1, B2, C1, k)

T(A1, B2, C2, k)

T(A2, B1, C1, k)

T(A2, B1, C2, k)

T(A2, B2, C1, k)

T(A2, B2, C2, k)

If any returns true, return true. Else return false.

Combine Return result of conquer step.

The recurrence is T(n) = 8T(n/2) + O(n) which solves to O(n^2) by Master's theorem.

As a result, examining all 8 options in a recursive fashion solves the issue in optimal O(n^2) time. Due to halving, the recursion tree depth decreases quickly, resulting in an efficient algorithm.