swap pair to make sum equal

Question

Question: Given two arrays of integers A[] and B[] of size N and M, the task is to check if a pair of values (one value from each array) exists such that swapping the elements of the pair will make the sum of two arrays equal.

My approach:

1. find sum of both arrays.
2. Identify array with larger sum(denote with A[]).
3. Sort A.
4. For all values in B binary search (sum(A)-sum(B)/2 + B[i]) in A, if found return true.
5. Return false.

code:

int sum(int a[], int n){
    int s=0;
    for(int i=0; i<n; i++){
        s+= a[i];
    }
    return s;
}

int findSwapValues(int A[], int n, int B[], int m)
{
    // Your code goes here
    int a = sum(A, n);
    int b = sum(B,m);
    int t;
    int *temp;
    
    if(a<b){
        temp  = A; 
        A = B;
        B = temp;
        t  = n;
        n = m;
        m = t;
        
        t = a;
        a = b;
        b = t;
    }
    
    sort(A, A+n);
    for(int i=0; i<m; i++){
        if(binary_search(A,A+n,(a-b)/2+B[i])){
            return 1;
        }
    }
    return -1;
}

Doubt: My algorithm is failing for some test cases(not TLE). As the test cases are very large, it's difficult to reason out the problem in the algorithm. I searched online and understood other approaches. My only curiosity is why its incorrect?

Answer 1

I think the error in your code is that you find B[i] + (a-b)/2.

The problem with this is that if (a-b) is an odd value, division by 2 will round it down to the nearest integer and you end up finding the wrong value.

What you can instead do is check if the difference is odd before even swapping the arrays, and if it is true, straight-away return -1 because if the difference is odd, no such pair can ever exist.

I hope I cleared your doubt :).