tug_of_war.cpp

/* tug_of_war.cpp
 * This is soln of Tug of War problem of Coding Ninjas. This is O(pow(2, N)) time, O(1) space soln.
 * https://www.codingninjas.com/codestudio/problem-details/tug-of-war_985253
 * Date Created: 24 Feb, 2022
 *       Author: Akhilesh Kumar Verma
 */

int tugOfWar(vector<int> &arr, int n) {
    int sum1 = arr.back(), sum2 = 0;
    for (int ele: arr) {
        sum2 += ele;
    }
    sum2 -= sum1;
    // zero in mask tell grp 2 and one tell grp 1
    int min_diff = sum1+sum2;
    for (int i = 0, mask, prev = 1 << (n-1); i < (1 << n); ++i, prev=mask) {
        mask = i ^ (i >> 1);
//         cout << hex << mask << dec << endl;
        int pos = __builtin_ctz(mask^prev);
        // element moved to GRP 2
        if (!(mask & (1 << pos))) {
            sum2 += arr[pos], sum1 -= arr[pos];
        }
        // Element moved to GRP 1
        else {
            sum1 += arr[pos], sum2 -= arr[pos];
        }
        int m = __builtin_popcount(mask);
//         cout << pos << ":" << sum1 << ":" << sum2 << endl;
        // neither ceil nor floor
        if (m != n/2 and m != (n+1)/2) {
            continue;
        }
//         cout << hex << mask << dec << ":" << min_diff
//             << ":" << abs(sum1 - sum2) << endl;
        min_diff = min(min_diff, abs(sum1 - sum2));
    }
    return min_diff;
}