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;
    }
}

Answer 1

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);