2

Lets say I have two arrays A and B

A = {1,2,3}
B = {12,11,67}
and have max sum value S = 10

How many maximum number of unique pairs can be formed between the two arrays who's sum is less than or equal to S.

For e.g., the two possible values here are [1,11] [2,12] hence the answer is 2. If there are none, the answer is 0.

My solution was to sort both the arrays and then go do

 if((Math.abs(A[i]-B[i]))<=S)
                 {
                 ans++;
             }

Although it works for this case, clearly this is incorrect.

  • In simplest case I'd use two nested loops to create all possible pairs, and something like a Set<Pair<Integer, Integer>> to store the pairs without repetitions. – 9000 Jun 21 '15 at 2:55
  • That would time out on large N's pretty quickly I think, is there a faster way ? – WeirdAl Jun 21 '15 at 4:34
  • Possibly sorting the arrays would help somehow? – 9000 Jun 21 '15 at 17:30
  • 2+12 ≤ 10? Has math changed? Do you mean S=13, with pairs (1,11), (1,12) and (2,11)? – outis Jun 23 '15 at 17:54
2

The key to doing this efficiently is exploiting the fact that if a1 < a2, then pair(a2) \subseteq pair(a1), where pair(a) = {b \in B : a + b <= S}. Example Java code:

Arrays.sort( A );
Arrays.sort( B );
int count = 0;
int j = B.length - 1;
for( int i = 0; i < A.length; ++i ) {
    while( j >= 0 ) {
        if( A[i] + B[j] <= S ) {
            break;
        }
        --j;
    }
    if( j < 0 ) {
        break;
    }
    count += (j + 1);
}

This code assumes there are no duplicates in A or B. The dominant operation is the O(n log n) sort. The loop traverses each list once, so the overall complexity is O(n log n + 2n) which is in O(n log n). If there are duplicates they can be removed from the sorted lists in linear time.

-1

Assume both A and B have a million members, and you have sorted A and B.

How many pairs can you form with A [0]? To find out, you add A [0] + B [0], A [0] + B [1], A [0] + B [2] etc. You stop when the result is too large, and then you know how many. Say A [0] + B [920178] is not too large, but A [0] + B [920179] is too large, then you can form 920179 pairs using A [0]. That method works because B is sorted.

How many pairs can you form with A [1]? Since A is sorted, A [0] <= A [1]. That means A [1] + B [920179] is too large. You search downward until you find for example that A [1] + B [920174] is not too large. This gives another 920175 pairs.

You repeat the same with A [2], A [3] up to A [999999]. So how long does this take? You examine a million values of A. You also examine at most a million values of B, because your search downward through B will end at B [0].

You'll have to be a bit careful at the ends of the arrays to avoid bugs in your code.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.