Sum Swap

16.21 Sum Swap: Given two arrays of integers, find a pair of values (one value from each array) that you can swap to give the two arrays the same sum.

EXAMPLE
Input: {4, l, 2, 1, 1, 2} and {3, 6, 3, 3}
Output: {l, 3}

• Brute force very obvious: swap each possible combination, and compare the sums.

• My optimized approach when as follows:

  • We know the a swap performs the following on the sum: sumA - a + b and sumB - b + a

  • We want to find the solution such that sumA - a + b = sumB - b + a. In other words, a swap that equates the sum.

  • In the above example, we would obtain a = -2 + b and b = 2 + a. Although both of which define the same relation, we apply both of these forumulas to our solution.

  • Now it becomes possible for us to iterate through the arrays, and check for the values we expect given these relationships and the current values in the array. However, this is still order n^2 worst case.

  • I am not to sure if the following will be an improvement or not, but if we sort both arrays. We can iterate through both array in a smarter way. In particular, when an element exceeds the number we expect as the minimum (through the formulas), then we can move on to the next iteration of the for loop.

• One flaw about this is that the solution return in index of the element of the sorted array, which would require some extra space to fix. This implies that it is not a very good solution.

pair<int, int> swapSum(vector<int> &A, vector<int> &B) {
    pair<int, int> sol;

    if (A.empty() || B.empty())
        return sol = make_pair(INT_MAX, INT_MAX);

    // find sums
    double sumA = accumulate(A.begin(), A.end(), 0);
    double sumB = accumulate(B.begin(), B.end(), 0);

    cout << sumA << endl;
    cout << sumB << endl;

    //sort
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    for (auto i : A) cout << i << " ";
    cout << endl;
    for (auto i : B) cout << i << " ";
    cout << endl;

    double formulaA = (sumA - sumB) / 2;
    double formulaB = -1 * formulaA;
    // since we are operating with integers, a non-integer
    // formula implies it is not possible
    if (int(formulaA) != int(formulaA)) 
        return sol = make_pair(INT_MAX, INT_MAX);

    for (int iterA = 0; iterA < A.size(); iterA++) {
        for (int iterB = 0; iterB < B.size(); iterB++) {
            int elementA = A.at(iterA);
            int elementB = B.at(iterB);

            // if we exceed the minimum for what we are looking for
            if (elementB > formulaB + elementA) {
                break;
            }

            else if (formulaA + elementB == elementA) {
                return sol = make_pair(iterA, iterB);
            }
        }
    }
    return sol = make_pair(INT_MAX, INT_MAX);
}

int main() {
    vector<int> one = {4,1,2,1,1,2};
    vector<int> two = { 3,3,3,6 };
    pair<int, int> sol = swapSum(one, two);
    cout << sol.first << " ";
    cout << sol.second << endl;
    pause();

    one = { 1,3,4,5,2,12,3,2,1,2,3 };
    two = { 1,3,4,5,2,2,7,1,2,3 };
    sol = swapSum(one, two);
    cout << sol.first << " ";
    cout << sol.second << endl;
    pause();

    one = { 2,3,2,5,2,12,23,2,6,1,1 };
    two = { 1,3,4,5,2,3,7,1,2,30 };
    sol = swapSum(one, two);
    cout << sol.first << " ";
    cout << sol.second << endl;
    pause();

    one = { 4,3,2,5,2,12,2,2,6,1,1 };
    two = { 1,3,4,5,6,3,7,8,5,2 };
    sol = swapSum(one, two);
    cout << sol.first << " ";
    cout << sol.second << endl;
    pause();
}

• Sorting is a subtle improvement, but not the best.

• To optimize this even more, we can sort the elements of B into a hash map, with the value pair being its index we can reference later

  • Basically, we preform the same algorithm as above, besides the sorting; and simply iterate through A , and checking whether the appropriate value for B exists. This will take O(N).

pair<int, int> swapSum(vector<int> &A, vector<int> &B) {
    pair<int, int> sol;

    if (A.empty() || B.empty())
        return sol = make_pair(INT_MAX, INT_MAX);

    // find sums
    double sumA = accumulate(A.begin(), A.end(), 0);
    double sumB = accumulate(B.begin(), B.end(), 0);

    // hash the value for array b
    unordered_map<int, int> hashB;
    for (int i = 0; i < B.size(); i++) {
        hashB.insert({B.at(i), i});
    }

    double formulaA = (sumA - sumB) / 2;
    double formulaB = -1 * formulaA;
    // since we are operating with integers, a non-integer
    // formula implies it is not possible
    if (int(formulaA) != int(formulaA)) 
        return sol = make_pair(INT_MAX, INT_MAX);

    for (int iterA = 0; iterA < A.size(); iterA++) {
        // value we expect b = sumB - sumA/2 + a
        auto &found = hashB.find(formulaB + A.at(iterA));
        if (found != hashB.end()) {
            return sol = make_pair(iterA, found->second);
        }
    }
    return sol = make_pair(INT_MAX, INT_MAX);
}