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

user_3181365 0
Viewed 469

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?

algorithm java
1 Answers

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)

user_93507200
Related