Nearby Squares

★★★★★

3.5

12 votes

Recursion, Recursion and Backtracking, Basic Programming

Details

Problem

You are given an array $A$ of length $N$ . There are two empty arrays, $B$ and $C$ . You have to put every element of $A$ into either $B$ or $C$ .

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 $B$ and $C$ .

Input Format:

The first line of input contains a single integer $T$ , denoting the number of test cases.
The first line of each test case contains a single integer $N$ , denoting the length of the array $A$ .
The second line of each test case contains $N$ integers, denoting the elements of array $A$ .

Output Format:

For each test case, print the minimum possible absolute difference between the score of $B$ and the score of $C$ .

Constraints:

$1 <= T <= 10$

$1 <= N <= 20$

$1 <= A[i] <= 10^8$

Sample Input

Sample Output

44
0

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

First test case:
We can put the third element in $B$ and the other elements in $C$ .
The score of $B$ is $10 ^ 2 = 100$ .
The score of $C$ 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 $B$ and the last two elements in $C$ .
The score of $B$ is $( 1 + 3 + 5 ) ^ 2 = 81$ .
The score of $C$ is $( 4 + 5 ) ^ 2 = 81$ .
Their absolute difference is $| 81 - 81 | = 0$ . Thus, the answer is $0$ .

Contributers:

Rohit Pradhan

Geetartha Kaustav