Header Ads Widget

Nearby Squares | Hackerearth solution

Rajnish Tripathi 10:50

 Problem

You are given an array 𝐴 of length 𝑁. There are two empty arrays, 𝐵 and 𝐶. You have to put every element of 𝐴 into either 𝐵 or 𝐶.

The score of an array is defined as the square of the sum of all of its elements. Find the minimum possible absolute difference between the score of 𝐵 and 𝐶.

Input Format:

  • The first line of input contains a single integer 𝑇, denoting the number of test cases.
  • The first line of each test case contains a single integer 𝑁, denoting the length of the array 𝐴.
  • The second line of each test case contains 𝑁 integers, denoting the elements of array 𝐴.

Output Format:

For each test case, print the minimum possible absolute difference between the score of 𝐵 and the score of 𝐶.

Constraints:

1 <= T <= 10
1 <= N <= 20
1 <= A[i] <= 10⁸
Sample Input Sample Output
2 44
4 0
4 5 10 3
5
1 3 5 4 5
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

First test case:
We can put the third element in 𝐵 and the other elements in 𝐶.
The score of 𝐵 is 102=100.
The score of 𝐶 is (4+5+3)2=144.
Their absolute difference is |100−144|=44.
It can be shown that this is the minimum possible absolute difference. Thus, the answer is 44.

Second test case:
We can put the first three elements in 𝐵 and the last two elements in 𝐶.
The score of 𝐵 is (1+3+5)2=81.
The score of 𝐶 is (4+5)2=81.
Their absolute difference is |81−81|=0. Thus, the answer is 0.

Solution:-

  
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// Function to return the minimum of two numbers
long long min(long long a, long long b) {
return (a < b) ? a : b;
}

// Recursive function to calculate the minimum absolute difference
// between the scores of two groups formed from the array elements
long long minScoreDifference(int n, int currentIndex, int group1Sum, int group2Sum, int arr[]) {
// Base case: when all elements are processed
if (currentIndex == n) {
// Calculate and return the absolute difference of squares of sums
return llabs(1LL * group1Sum * group1Sum - 1LL * group2Sum * group2Sum);
} else {
// Recursive case 1: Include the current element in the first group (group1Sum)
long long option1 = minScoreDifference(n, currentIndex + 1, group1Sum + arr[currentIndex], group2Sum, arr);
// Recursive case 2: Include the current element in the second group (group2Sum)
long long option2 = minScoreDifference(n, currentIndex + 1, group1Sum, group2Sum + arr[currentIndex], arr);
// Return the minimum of both options
return min(option1, option2);
}
}

int main() {
int testCases; // Number of test cases
// Read the number of test cases
scanf("%d", &testCases);
// Process each test case
while (testCases--) {
int arrayLength; // Length of the array
// Read the length of the array
scanf("%d", &arrayLength);
int arr[arrayLength]; // Array to store the elements
// Read the array elements
for (int i = 0; i < arrayLength; i++) {
scanf("%d", &arr[i]);
}
// Calculate the minimum absolute difference between the scores of two groups
long long result = minScoreDifference(arrayLength, 0, 0, 0, arr);
// Output the result
printf("%lld\n", result);
}
return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
ios_base::sync_with_stdio(false); // Optimize input/output
cin.tie(nullptr);

int testCases;
cin >> testCases; // Read the number of test cases

while (testCases--) {
int arraySize;
cin >> arraySize; // Read the size of the array

vector<int> arr(arraySize);
for (int i = 0; i < arraySize; ++i) {
cin >> arr[i]; // Read each element of the array
}

long long totalSum = accumulate(arr.begin(), arr.end(), 0LL); // Calculate total sum of the array
long long minDifference = LLONG_MAX; // Initialize minimum difference

set<long long> subsetSums; // Set to store subset sums
int halfSize = arraySize / 2; // Calculate half size of the array

// Generate subset sums for the first half of the array
for (int mask = 0; mask < (1 << halfSize); ++mask) {
long long currentSubsetSum = 0;
for (int i = 0; i < halfSize; ++i) {
if (mask & (1 << i)) {
currentSubsetSum += arr[i]; // Calculate current subset sum
}
}
subsetSums.insert(currentSubsetSum); // Store the sum in the set
}

// Convert set to sorted vector for binary searching
vector<long long> sortedSubsetSums(subsetSums.begin(), subsetSums.end());

// Generate subset sums for the second half of the array
for (int mask = 0; mask < (1 << (arraySize - halfSize)); ++mask) {
long long currentSubsetSum = 0;
for (int i = 0; i < (arraySize - halfSize); ++i) {
if (mask & (1 << i)) {
currentSubsetSum += arr[halfSize + i]; // Calculate current subset sum for second half
}
}

// Find closest subset sum to minimize the difference
auto it = lower_bound(sortedSubsetSums.begin(), sortedSubsetSums.end(), totalSum / 2 - currentSubsetSum);
for (auto j = it; j != sortedSubsetSums.end() && j <= it + 1; ++j) {
if (j >= sortedSubsetSums.begin() && j < sortedSubsetSums.end()) {
// Update minimum difference
minDifference = min(minDifference, abs(totalSum * (totalSum - 2 * (currentSubsetSum + *j))));
}
}
}

cout << minDifference << '\n'; // Output the minimum absolute difference
}

return 0; // Successful execution
}

Text Copied!

easycodingzone

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-


Tags:

Post a Comment

0 Comments