Corrupted Array (Codeforces 1512D)
Tags: Greedy, data structures

You are given a number $$$n$$$ and an array $$$b_1, b_2, \ldots, b_{n+2}$$$, obtained according to the following algorithm:   some array $$$a_1, a_2, \ldots, a_n$$$ was guessed;  array $$$a$$$ was written to array $$$b$$$, i.e. $$$b_i = a_i$$$ ($$$1 \le i \le n$$$);  The $$$(n+1)$$$-th element of the array $$$b$$$ is the sum of the numbers in the array $$$a$$$, i.e. $$$b_{n+1} = a_1+a_2+\ldots+a_n$$$;  The $$$(n+2)$$$-th element of the array $$$b$$$ was written some number $$$x$$$ ($$$1 \le x \le 10^9$$$), i.e. $$$b_{n+2} = x$$$; The  array $$$b$$$ was shuffled. For example, the array $$$b=[2, 3, 7, 12 ,2]$$$ it could be obtained in the following ways:   $$$a=[2, 2, 3]$$$ and $$$x=12$$$;  $$$a=[3, 2, 7]$$$ and $$$x=2$$$. For the given array $$$b$$$, find any array $$$a$$$ that could have been guessed initially.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$). Then $$$t$$$ test cases follow.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).The second row of each test case contains $$$n+2$$$ integers $$$b_1, b_2, \ldots, b_{n+2}$$$ ($$$1 \le b_i \le 10^9$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output:   "-1", if the array $$$b$$$ could not be obtained from any array $$$a$$$;  $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, otherwise. If there are several arrays of $$$a$$$, you can output any.


Sample Inputs:
4
3
2 3 7 12 2
4
9 1 7 1 6 5
5
18 2 2 3 2 9 2
3
2 6 9 2 1

Sample Outputs:
2 3 7 
-1
2 2 2 3 9 
1 2 6

Solution (Python):
def solve(n, arr):
    max1 = max(arr)
    arr.remove(max1)
    tsum = sum(arr)
    for ai in arr:
        if tsum - ai == max1:
            arr.remove(ai)
            print(' '.join(map(str, arr)))
            return
    max2 = max(arr)
    if max2 == tsum - max2:
        arr.remove(max2)
        print(' '.join(map(str, arr)))
    else:
        print(-1)
for t in range(int(input())):
    n = int(input())
    arr = list(map(int, list(input().split())))
    solve(n, arr)

Solution (Python):
def solve():
    alen = int(input())
    b = [int(x) for x in input().split()]
    bsum = sum(b)
    d = {}
    for x in b:
        if x in d:
            d[x] += 1
        else:
            d[x] = 1
    for key in d:
        asum = bsum - key
        if asum % 2 == 0 and asum // 2 in d and (asum // 2 != key or d[key] > 1):
            b.remove(key)
            b.remove(asum // 2)
            print(' '.join(map(str, b)))
            return
    print(-1)
numcases = int(input())
for case in range(numcases):
    solve()

Solution (Python):
from collections import defaultdict

def main():
    n = int(input())
    l = list(map(int, input().split()))
    l = sorted(l)
    b = sum(l[:n])
    if b > l[-1] and b > l[-2]:
        print(-1)
        return
    if b == l[-1] or b == l[-2]:
        print(' '.join((str(num) for num in l[:n])))
        return
    diff = l[-1] - b
    diff2 = l[-2] - diff
    if diff2 in l[:n]:
        l.remove(diff2)
        print(' '.join((str(num) for num in l[:n])))
    else:
        print(-1)
        return
for i in range(int(input())):
    main()