The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

Problem

You are given an integer m (1 <= m <= 1,000,000) and two non-empty, zero-indexed arrays A and B of n integers, a₀, a₁ , . . . , a_n-1 and b₀ , b₁ , . . . , b_n-1 respectively (0 <= a_i , b_i <= m).

The goal is to check whether there is a swap operation, which can be performed on these arrays in such a way that the sum of elements in array A equals the sum of elements in array B, after the swap. By swap operation we mean picking one element from array A and one element from array B and exchanging them.

Do it in O(n³) time, O(n²) time and O(n+m) time.

Example

Let A = [9, 1, 4, 5, 4 ]
Let B = [8, 2, 4, 6, 7]

Current sum of all elements in A is 23.
Current sum of all elements in B is 27.

Notes

- The highest number in either array is 9, so m = 9. It is given that all the numbers in A and B are positive.

- The function should return true, when the first possible swap is detected. If no swap is possible, to make both array sums equal, then the function should return false.

Note: only one pair of elements have to be swapped to cause the change (equal sums for both arrays). The pair must not necessarily have the same index in either array. So, not more than one pair has to be swapped. From inspection of the above given arrays (lists), the first two numbers that can be swapped to cause equality, of both array sums, are 4 from array A and 6 from array B; moving from left to right, in the arrays. The new sum in either array would be twenty-five. 5 and 7 can also be swapped to cause the same effect. However, when the first possible swap is detected, the function should return true.

In the programs below, both arrays are of the same length, n.

O(n³) Time Solution

For this time complexity, every pair of elements are swapped, and for each swap, the totals (sums) are calculated. The totals are compared before the next swapping. After each swap, if the totals are not the same, the reverse swapping has to be made, for the next new totals to be correctly done. The program is:

    #include <stdio.h>
    #include <stdbool.h>
    
    bool solution(int A[], int B[], int n, int m) {
        int sumA = 0;    
        int sumB = 0;
        for (int i=0; i < n; i++) {
            for (int j=0; j < n; j++) {
                //swapping
                int temp = A[i];
                A[i] = B[j];
                B[j] = temp;
                for (int k=0; k < n; k++) {
                    sumA = sumA + A[k];
                    sumB = sumB + B[k];  
                }  
                if (sumA == sumB) 
                    return true;
                else {//swap back
                    int temp = A[i];   
                    A[i] = B[j];
                    B[j] = temp;
                }
                sumA = 0; sumB = 0;  //resetting sums
            }
        }
        
        return false;
    } 

    int main(int argc, char **argv)
    {
        int A[] = {9, 1, 4, 5, 4};
        int B[] = {8, 2, 4, 6, 7};
        int n = sizeof(A) / sizeof(A[0]);
        bool bl = solution(A, B, n, 9); 
        printf("%i\n", bl);

        return 0;
    }

The output is 1, for true. False would be returned (last statement in function, solution() ), if true is not returned. The swapping indexes for which the totals became equal, were not asked for. However, they are the zero-based index 2 for array A (value of 4), and the zero based index 3, for array B (value of 6).

There are three for-loops. The second one is nested in the first one and the third one is nested in the second one. The third one calculates the totals (sums) after each swap. The equality of the sums is checked just after each scan of the third for-loop. If after swapping, the sums are not equal, then the swapped values are swapped back. The swapping code for forward and backward swapping, is the same, that is:

                    int temp = A[i];
                    A[i] = B[j];
                    B[j] = temp;

If the time consumed by the two swapping code segments are ignored, then the time complexity is O(n³) . If the operations from the swapping code segments are not ignored, then the time complexity is higher than O(n³). Well, when quoting the time complexity in practice, the swapping code segments are ignored.

Note that the parameter, m was not used in the above solution() function; and the strategy for counting the number of occurrences for each element, was also not used.

O(n²) Time Solution

The arrays and their totals are as follows:

Let A = [9, 1, 4, 5, 4 ];      sumA = 23

Let B = [8, 2, 4, 6, 7];      sumB = 27

That is, for array A: 9 + 1 + 4 + 5 + 4 = 23. For array B: 8 + 2 +4 + 6 + 7 = 27. The difference between the two totals (sums) is 27 – 23 = 4. When the first value of 4 from A, was swapped with 6 from B, to make both sums equal, 2 was essentially subtracted from 27, and added to 23 to make both sums 25.

6 - 4 = 2. The difference between both sums (totals) is 4. 2 is half (½) of 4. This means that for one swap to cause both sums to be equal, for any given pair of arrays, the difference between both sums must be an even number (e.g. 4 above); and the difference between both swapped values must be half the difference of both sums (both totals), e.g. 2 above. The halved number must not necessarily be an even number. So, the correct swapped pair, sends half the difference of the smaller sum from the bigger sum, to the smaller sum array.

The function coding will be similar to the above solution() function, but the inner for-loop will be eliminated. The summing of the two arrays, is done before the two for-loops (with one nested) are engaged. The time taken to determine these two totals is ignored. And so the resulting time complexity is considered as O(n²), based on the two for-loops (one nested). Remember that both arrays are of the same length, n.

The preceding summing of A and B are done in two simple for-loops. The solution function is:

    #include <stdio.h>
    #include <stdbool.h>
    
    bool solution(int A[], int B[], int n, int m) {
        int sumA = 0;    
        for (int i=0; i<n; i++) sumA = sumA + A[i];
        int sumB = 0;
        for (int i=0; i<n; i++) sumB = sumB + B[i];
        bool sumBBiggerThanSumA = false;
        int diff = 0;
        if (sumB > sumA) {
            diff = sumB - sumA;
            sumBBiggerThanSumA = true;
        }
        else {
            diff = sumA - sumB;
            sumBBiggerThanSumA = false;
        }

        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                //check possible swapping without swapping
                int change = 0;
                if (sumBBiggerThanSumA == true)
                    change = B[j] - A[i];
                else
                    change = A[i] - B[j];
              
                if (change > 0 && change == 0.5 * diff) 
                    return true; 
            }
        }
        
        return false;
    } 

    int main(int argc, char **argv)
    {
        int A[] = {9, 1, 4, 5, 4};
        int B[] = {8, 2, 4, 6, 7};
        int n = sizeof(A) / sizeof(A[0]);
        bool bl = solution(A, B, n, 9); 
        printf("%i\n", bl);

        return 0;
    }

The output is 1, for true. Note that the parameter, m has still not been used here; and the strategy for counting the number of occurrences for each element, has also not been used.

O(n+m) Time Solution

The above algorithm can be seen as follows: obtain the difference, d of the total sums of both arrays. Obtain half the difference, h. Then, for each element in B, subtract h and see if the answer is found in A, by checking all the elements in A. This leads to O(n²) time.

O(n+m) time is usually less than O(n²) time. Scanning each element in B takes n time. A count array for array A, can be made in m time, where m is the largest element in A. Let each element in B be B[i], where i is an index for a B element. In order to know if B[i] - h exits as an element in A, use the count array, where B[i] - h is an index. If the value (count) of the index in the count array is greater than 0, then B[i] - h exists in array A, and the correct swapping can then take place. Remember that the index for the count array has as value, the number of occurrences of one value (an index in count), in a given array. Of course, B[i] – h should not be less than 0, and should not be greater than the maximum index, m of the count array. The time complexity will be O(n+m) time.

The durations to determine the two array totals (sums), are ignored when quoting the time complexity. The solution function is:

    #include <stdio.h>
    #include <stdbool.h>
    
    bool solution(int A[], int B[], int n, int m) {
        int sumA = 0;    
        for (int i=0; i < n; i++) sumA = sumA + A[i];
        int sumB = 0;
        for (int i=0; i < n; i++) sumB = sumB + B[i];
        int d = sumB - sumA;
        if (d % 2 == 1 || d % 2 == -1 ) return false;  //d cannot be odd integer
        int h = d/2;

        int count[m+1];
        for (int i=0; i < m+1; i++)
            count[i] = 0;
            
        for (int i=0; i < n; i++)  //time complexity: m operations
            count[A[i]] = count[A[i]] + 1;

        for (int i=0; i < n; i++)  //time complexity: n operations
            if (0 <= B[i] - h && B[i] - h <= m && count[B[i] - h] > 0)  //still valid for -ve h
                return true;
        
        return false;
    } 

    int main(int argc, char **argv)
    {
        int A[] = {9, 1, 4, 5, 4};
        int B[] = {8, 2, 4, 6, 7};
        int n = sizeof(A) / sizeof(A[0]);
        bool bl = solution(A, B, n, 9); 
        printf("%i\n", bl);

        return 0;
    }

The output is 1, for true.

This is another example, where after establishing the count array, the given array is iterate over in conjunction with the count array, to obtain the result. With many other solutions, only the count array is iterated over, after establishment, to have the result.

"if (count[B[i] - h] > 0)" means that B[i] - h occurs at least once in array A.

Thanks for reading.