Return the total number of pairs (a, b) where a is from A and b is from B, and a + b is <= c

Question

Trying to do some practice and I ran across this problem...

Given two int arrays A and B, and an int c, return the total number of pairs (a, b) where a is from A and b is from B, and a + b is <= c

Came up with brute force solution immediately, but can't seem to connect the dots in order to do this in better time complexity. I tried sorting the arrays first, and trying to find some type of pattern but that didn't get me anywhere. I thought about cases where one array had negative numbers. In this case, I cant just look at a value from A or B and check if it itself is less than c, because there may be a negative value in the other array that when added together gives me a result of <= c. Any insight, or ideas, or clues would be appreciated.

import java.util.*;

public class CountPairs {

    public static void main(String args[]){
        int arrayA[] = {32,45,9,4};
        int arrayB[] = {43,457,54,90};

        Scanner scan = new Scanner(System.in);

        System.out.println("Choose the value that you want to find pairs <= ");
        int c = scan.nextInt();

        System.out.println("The total number of pairs are : " + pairs(arrayA, arrayB, c));
    }

    public static int pairs(int A[], int B[], int n) {
        int count = 0;

        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B.length; j++) {
                int total = A[i] + B[j];

                if(total <= n)
                    count++;
            }
        }

        return count;
    }
}

check this http://stackoverflow.com/questions/3815116/given-two-arrays-a-and-b-find-all-pairs-of-elements-a1-b1-such-that-a1-belong — root, Nov 15 '16 at 06:13
I can't @Hulk because if array B has any negative values, I could potentially miss a pair that satisfies the condition. Consider a = 10, c = 5. If skipped the inner loop for situations like these but arrayB has a value such as b = -6 then we miss a pair. — Elroy Jetson, Nov 15 '16 at 14:23
@ElroyJetson you are correct, of course - I missed that there could be negative numbers — Hulk, Nov 15 '16 at 15:30

Grzegorz Piwowarek · Answer 1 · 2016-11-15T13:13:56.733

11

Let's spare a second to appreciate how easy the task becomes when working with Javaslang and utilizing the declarative functional approach:

Initial data:

int arrayA[] = {32, 45, 9, 4};
int arrayB[] = {43, 457, 54, 90};

int c = 100;

Solution:

int result = List.ofAll(arrayA)
  .crossProduct(List.ofAll(arrayB))
  .distinct()
  .count(t -> t._1 + t._2 <= c);

edited Nov 15 '16 at 13:13

answered Nov 15 '16 at 06:40

Grzegorz Piwowarek

13,172
8
62
93

1

this doesn't work. Zip will not create all combinations, only those with the same index. You need a flatmap. – Ulysse Mizrahi Nov 15 '16 at 12:23
@UlysseMizrahi good point :) indeed combinations are needed here – Grzegorz Piwowarek Nov 15 '16 at 12:30

score 6 · Answer 2 · edited Nov 15 '16 at 07:43

6

If you are doing this for the purpose of practice then I recommend you completely ignore performance and aim for clarity of code.

Often developers will get in the habit of making their code as efficient as possible at the expense of simplicity and clarity which is generally a bad idea as it's almost impossible to tell ahead of time what will be a performance issue.

In terms of clarity, you might want to consider using Stream API instead of a common iteration:

Arrays.stream(arrayA)
    .flatMap(n1 -> Arrays.stream(arrayB).map(n2 -> n1 + n2))
    .filter(n -> n <= total)
    .count();

edited Nov 15 '16 at 07:43

Grzegorz Piwowarek

13,172
8
62
93

answered Nov 15 '16 at 06:54

sprinter

27,148
6
47
78

@pivovarit really? why? I can't see anything in OP's question about counting distinct pairs. – sprinter Nov 17 '16 at 21:41

score 5 · Accepted Answer · answered Nov 16 '16 at 16:06

We can solve this in O(m log m + n log m) = O(log m (m + n)) time where m is the cardinality of the smaller array; n, the larger. First, sort the smaller array:

A = {32,45,9,4};
B = {43,457,54,90};

=> A = {4,9,32,45}

Now for each b in B, use a binary search on A to find the index of the greatest a less than or equal to (c - b). Add (index + 1) to the accumulating result. For example:

c = 100:
  43  => 100 - 43  = 57   => largest a <= c-b = 45, index 3 => add 4 to result
  457 => 100 - 457 = -357 => largest a <= c-b = None
  54  => 100 - 54  = 46   => largest a <= c-b = 45, index 3 => add 4 to result
  90  => 100 - 90  = 10   => largest a <= c-b = 9,  index 1 => add 2 to result

result = 4 + 4 + 2 = 10
 corresponding with the following pairs:
 (43,4),(43,9),(43,32),(43,45),(54,4),(54,9),(54,32),(54,45),(90,4),(9,9)

...this is a really intuitive approach. It also doesn't count non-distinct pairs, which is great. Thanks . — Elroy Jetson, Nov 17 '16 at 22:06
That is a very efficient solution. Would have upvoted twice. — jetstream96, Nov 19 '16 at 03:14

score 3 · Answer 4 · answered Nov 15 '16 at 06:21

Starting with sorting the arrays is a good idea. I'd work backwards from the maximums down, and find which indexes give a value under c:

public static int pairs(int a[], int b[], int c) {
    // a and b should be sorted before being passed here

    // Find the largest a that has a pair under c:
    int amax;
    int bmax_for_a;
    for (amax = a.length; amax > 0; amax--) {
        for (int bmax_for_a = b.length; bmax_for_a > 0; bmax_for_a--) {
            if (a[amax] + b[bmax_for_a] <= c) {
                break;
            }
        }
    }

    // Find the largest b that has a pair under c:
    int bmax;
    int amax_for_b;
    for (bmax = b.length; bmax > 0; bmax--) {
        for (int amax_for_b = a.length; amax_for_b > 0; amax_for_b--) {
            if (a[amax_for_b] + b[bmax] <= c) {
                break;
            }
        }
    }

    // Now that we have the indexes, calculate the total matches
    // and discard duplicates:
    return (amax * bmax_for_a) + (bmax * amax_for_b) - (amax_for_b * bmax_for_a);
}

n247s · Answer 5 · 2016-11-17T08:26:48.027

I like the idea of sorting both lists and search for the edge cases. Nevertheless this will only work well if the numbers in the array have a pattern in them ass well. (E.g. {1, 2, 3' ...} or {1, 3, 5, ...}) cause you can design a specific algorithm for that specific pattern.

A way to cut unecessary looping though would be to sort both arrays, and get the lowest number. And check at wich index you dont have to look for pairs anymore. Like
- imagine A= {1, 5, 6, 12} and B {1, 2, 3, 4, 5, 6} and c is 7.
- For Array A the lowest number is 1. This means beyond index 5 in array B there is no match, meaning you have to iterate till index 5.
- For array B the lowest number is 1 as well. Beyond index 2 there shouldnt be any possible pairs.

This way you can cut off a portion of both arrays, but you still need to check every index before that point since there is no guranty that all possible pair meet the preset condition.

David Ehrmann · Answer 6 · 2016-11-15T06:47:04.867

What about taking advantage of a NavigableSet for sorting and for its headSet method:

public int countPairs(int[] a, int[] b, int c) {
    NavigableSet<Integer> aSet = IntStream.of(a).boxed().collect(Collectors.toCollection(TreeSet::new));
    NavigableSet<Integer> bSet = IntStream.of(b).boxed().collect(Collectors.toCollection(TreeSet::new));

    int total = 0;

    for (int aVal : aSet) {
        int max = c - aVal;
        Set<Integer> bVals = bSet.headSet(max, true);
        total += bVals.size();

        // Optimization to break from loop once there are no values small enough to satisfy the condition
        if (bVals.isEmpty()) {
            break;
        }
    }

    return total;
}

This does assume that for a = [0, 1], b = [0, 1], c = 5 that the pairs 0, 1 and 1, 0 are distinct pairs. It also clusters together duplicates in each array, but that could be handled with some added record keeping (that makes the algorithm harder to follow).

Return the total number of pairs (a, b) where a is from A and b is from B, and a + b is <= c

6 Answers6