Untitled
unknown
plain_text
a year ago
1.3 kB
6
Indexable
#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; }
Editor is loading...
Leave a Comment