Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
1.3 kB
3
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3", "unroll-loops")
auto init = []() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 'c';
}();

// MAIN FUNCTION TO FOCUS ON!
long long nearbySquares(vector<int>& arr, int n, int totalSum, int i, int leftSum) {

	//Base Case: find and return the curr diff of B and C
	if(i == n){
		long long rightSum = totalSum - leftSum;
		return abs(leftSum*leftSum - rightSum*rightSum);
	}

	//Recursive Call: Calling with options: arr[i] being added to B or C arr at a time
	long long left = leftSum + arr[i];
	long long rightSum = totalSum - leftSum; 
	long long right = rightSum + arr[i];

	//adding arr[i] to B. getting the minDiff from this option.
	long long leftMinDiff = nearbySquares(arr, n, totalSum, i + 1, left);

	//adding arr[i] to C. getting the minDiff.
	long long rightMinDiff = nearbySquares(arr, n, totalSum, i + 1, leftSum);

	//Small Calculation
	return min(leftMinDiff, rightMinDiff);
}

int main() {

	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		
		vector<int> nums(n, 0);
		int totalSum = 0;
		for(int i = 0; i < n; i++){
			cin >> nums[i];
			totalSum += nums[i];
		}

		// Main Function Call
		cout << nearbySquares(nums, n, totalSum, 0, 0) << endl;
	}
    return 0;
}
Leave a Comment