java - Total number of ways such that the sum of elements is less than or equal to k

Question

Task: Find the number of possible ways to pick a single element from each array, such that their sum is less than k.

Here is my program looks like:

public static long process(List<Integer> a, List<Integer> b, List<Integer> c, List<Integer> d, int k) {
    Collections.sort(a);
    Collections.sort(b);
    Collections.sort(c);
    Collections.sort(d);
    long total = 0;
    // four layer for loop to check all combinations of four arrays
    for (int i = 0; i < a.size(); i++) {
        long v = a.get(i);
        for (int j = 0; j < b.size() && v < k; j++) {
            long v1 = b.get(j);
            for (int m = 0; m < c.size() && v + v1 < k; m++) {
                long v2 = c.get(m);
                for (int l = 0; l < d.size() && v + v1 + v2 < k; l++) {
                    long v3 = d.get(l);
                    if (v + v1 + v2 + v3 <= k) {
                        total = total + 1;
                    } else {
                        break;
                    }
                }
            }
        }
    }
    return total;   
}

This was asked during an interview, I see that when I have used it, the program failed for test cases saying time limit exceeded.

What is best approach to follow for this task?

question from:https://stackoverflow.com/questions/66062522/total-number-of-ways-such-that-the-sum-of-elements-is-less-than-or-equal-to-k

Answer 1

Let the length of the lists be N. Your approach is O(N^4), which is likely to time out.
A simple yet faster approach would be:

1. Generate all pair sums (which are less than k) from arrays A and B. Store them in an array X. Complexity: O(N^2)
2. Generate all pair sums (which are less than k) from arrays C and D, store them in array Y. Complexity: O(N^2)
3. Sort arrays X and Y. Complexity: O(N^2 logN)
4. For each element in X, find the maximum element in Y such that their sum < k. Using binary search, complexity: O(N^2 logN)

Space complexity: O(N^2), Time Complexity: O(N^2 logN)