An array $b$ of length $k$ is called good if its arithmetic mean is equal to $1$. More formally, if $$\frac{b_1 + \cdots + b_k}{k}=1.$$

Note that the value $\frac{b_1+\cdots+b_k}{k}$ is not rounded up or down. For example, the array $[1,1,1,2]$ has an arithmetic mean of $1.25$, which is not equal to $1$.

You are given an integer array $a$ of length $n$. In an operation, you can append a non-negative integer to the end of the array. What's the minimum number of operations required to make the array good?

We have a proof that it is always possible with finitely many operations.


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. Then $t$ test cases follow.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 50$) — the length of the initial array $a$.

The second line of each test case contains $n$ integers $a_1,\ldots,a_n$ ($-10^4\leq a_i \leq 10^4$), the elements of the array.


-----Output-----

For each test case, output a single integer — the minimum number of non-negative integers you have to append to the array so that the arithmetic mean of the array will be exactly $1$.


-----Examples-----

Input
4
3
1 1 1
2
1 2
4
8 4 6 2
1
-2
Output
0
1
16
1


-----Note-----

In the first test case, we don't need to add any element because the arithmetic mean of the array is already $1$, so the answer is $0$.

In the second test case, the arithmetic mean is not $1$ initially so we need to add at least one more number. If we add $0$ then the arithmetic mean of the whole array becomes $1$, so the answer is $1$.

In the third test case, the minimum number of elements that need to be added is $16$ since only non-negative integers can be added.

In the fourth test case, we can add a single integer $4$. The arithmetic mean becomes $\frac{-2+4}{2}$ which is equal to $1$.

Source: codeforces | Difficulty: EASY
Tags: Mathematics

Greedy algorithms


Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	lst = input().split()
	lst = [int(i) for i in lst]
	sm = sum(lst)
	if sm < n:
		print(1)
	else:
		print(sm - n)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(maxsplit=n - 1)))
	if sum(a) >= n:
		print(sum(a) - n)
	else:
		print(1)


def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		nums = list(map(int, input().strip().split()))
		total = sum(nums)
		if total > n:
			print(total - n)
		elif total < n:
			print(1)
		else:
			print(0)
main()


for _ in range(int(input())):
	n = int(input())
	temp = list(map(int, input().split()))
	k1 = sum(temp)
	if k1 > 0 and k1 > n:
		print(k1 - n)
	elif k1 // n == 1:
		print(0)
	else:
		print(1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	if s / n == 1:
		print(0)
	elif sum(l) <= 0:
		print(1)
	elif sum(l) < n:
		print(1)
	else:
		print(s - n)


t = int(input())
for i in range(t):
	count = 0
	n = int(input())
	l = [int(i) for i in input().split()]
	sum1 = sum(l)
	if sum1 < n:
		print(1)
	elif sum1 == n:
		print(0)
	else:
		print(sum1 - n)


t = int(input())
while t:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	if s > n:
		print(s - n)
	elif s == n:
		print('0')
	else:
		print('1')


import sys
import math
__ = int(sys.stdin.readline())
for _ in range(__):
	n = int(sys.stdin.readline())
	l = list(map(int, sys.stdin.readline().split()))
	x = sum(l)
	if x == n:
		print(0)
	elif x < n:
		print(1)
	else:
		print(x - n)


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	sm = sum(lst)
	if sm < n:
		print(1)
	elif sm == n:
		print(0)
	else:
		print(sm - n)


t1 = int(input())
for i in range(t1):
	n = int(input())
	a = list(map(int, input().split()))
	if sum(a) < len(a):
		print(1)
	else:
		print(sum(a) - len(a))


def solve():
	n = int(input())
	l = list(map(int, input().split()))
	s = -n
	for i in l:
		s += i
	if s < 0:
		s = 1
	elif s == 0:
		s = 0
	print(s)
t = int(input())
for i in range(t):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	total = sum(a)
	if total >= n:
		print(total - n)
	else:
		print(1)


for s in [*open(0)][2::2]:
	print(abs(min(1, len((a := s.split())) - sum(map(int, a)))))


t = int(input())
ans = []
for i in range(t):
	n = int(input())
	nums = tuple(map(int, input().split()))
	sumofnums = sum(nums)
	if sumofnums < n:
		ans.append(1)
	else:
		ans.append(abs(sumofnums - n))
for case in tuple(ans):
	print(case)


t = int(input())
for case in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	total = sum(a)
	if total == n:
		print(0)
	elif total < n:
		print(1)
	else:
		print(total - n)


def solve():
	n = int(input())
	a = [int(i) for i in input().split()]
	q = sum(a) - n
	return 1 if q < 0 else sum(a) - n
t = int(input())
ans = []
while t:
	ans.append(str(solve()))
	t -= 1
print('\n'.join(ans))


t = int(input())
for i in range(t):
	x = int(input())
	arr = list(map(int, input().split()))
	s = sum(arr)
	if s == x:
		print(0)
	elif s > x:
		print(s - x)
	else:
		print(1)


import math
t = int(input())
for _ in range(t):
	c = 0
	d = 0
	n = int(input())
	l = list(map(int, input().split()))
	if sum(l) >= n:
		print(sum(l) - n)
	else:
		print(1)


test_cases = int(input())
for i in range(test_cases):
	length = int(input())
	arr = list(map(int, input().split()))
	if sum(arr) >= len(arr):
		print(sum(arr) - len(arr))
	else:
		print(1)


n = int(input())
for i in range(n):
	a = int(input())
	b = list(map(int, input().split()))
	b.sort()
	if a == sum(b):
		print(0)
	elif sum(b) > a:
		print(sum(b) - a)
	else:
		print(1)


w = int(input())
l = []
for i in range(w):
	k = int(input())
	t = list(map(int, input().split()))
	l.append(t)
for i in l:
	mean = sum(i) / len(i)
	if mean == 1.0:
		print(0)
	elif mean > 1.0:
		print(sum(i) - len(i))
	else:
		print(1)


import sys
input = sys.stdin.readline

def read_int_list():
	return list(map(int, input().split()))

def solve(a):
	s = sum(a)
	if s >= 0:
		if sum(a) - len(a) >= 0:
			return sum(a) - len(a)
	return 1
for _ in range(int(input())):
	n = int(input())
	print(solve(read_int_list()))


t = int(input())
for i in range(t):
	k = int(input())
	l = list(map(int, input().split()))
	if sum(l) / k == 1:
		print('0')
	elif sum(l) <= 0 or sum(l) < k:
		print('1')
	else:
		print(sum(l) - k)


t = int(input())
natija = []
for i in range(t):
	n = int(input())
	satr = input()
	ruyhat = satr.split(' ')
	for i in range(n):
		ruyhat[i] = int(ruyhat[i])
	Sum = sum(ruyhat)
	if Sum < n:
		natija.append(1)
	elif Sum == n:
		natija.append(0)
	else:
		natija.append(Sum - n)
for i in range(t):
	print(natija[i])


t = int(input())
while t != 0:
	a = int(input())
	b = [int(x) for x in input().split()]
	if sum(b) / len(b) == 1:
		print('0')
	elif sum(b) < len(b):
		print('1')
	else:
		print(sum(b) - len(b))
	t = t - 1


t = int(input())

def q(n, s):
	if s >= n:
		return s - n
	else:
		return 1
for i in range(t):
	n = int(input())
	j = input().split()
	l = list(map(int, j))
	s = sum(l)
	print(q(n, s))


for g in [*open(0)][2::2]:
	a = list(map(int, g.split()))
	s = sum(a)
	l = len(a)
	print([s - l, '1'][s < l])


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	x = sum(a)
	if x >= n:
		print(x - n)
	elif x < n:
		print(1)


for i in range(int(input())):
	n = int(input())
	a = [int(j) for j in input().split()]
	cnt = 0
	if sum(a) >= n:
		print(sum(a) - n)
	else:
		print(1)


t = int(input())
for tt in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	sm = sum(a)
	if sm == n:
		print(0)
	elif sm < n:
		print(1)
	else:
		print(sm - n)


for _ in ' ' * int(input()):
	n = int(input())
	arr = list(map(int, input().split()))
	a = sum(arr)
	print(a - n if a >= n else 1)


h = int(input())
for i in range(0, h):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	if s - n == 0:
		print('0')
	if s - n < 0:
		print('1')
	if s - n > 0:
		print(s - n)


n = int(input())
for i in range(n):
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	if s < n:
		print(1)
	else:
		print(s - n)


def main():
	l = 1
	T = int(input())
	out = ''
	while l != T + 1:
		N = int(input())
		A = map(int, input().split(' '))
		out += f'{solve(N, A)}\n'
		l += 1
	print(out, flush=True)

def solve(N, A):
	S = sum(A)
	if S == N:
		return 0
	elif S > N:
		return S - N
	else:
		return 1
main()


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	total = 0
	for i in range(n):
		total += arr[i]
	if total < n:
		print(1)
	else:
		print(total - n)
t = int(input())
for i in range(t):
	solve()


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	S = sum(arr)
	if S / n == 1:
		return 0
	else:
		return max(S - n, 1)
for _ in range(int(input())):
	print(solve())


ans = []
for _ in range(int(input())):
	n = int(input())
	sn = sum(map(int, input().split()))
	if n == sn:
		ans.append(0)
	elif n > sn:
		ans.append(1)
	else:
		ans.append(sn - n)
print('\n'.join(map(str, ans)))


for i in range(int(input())):
	a = int(input())
	b = sum(map(int, input().split()))
	if b < a:
		print(1)
	else:
		print(b - a)


t = int(input())
for i in range(t):
	count = 0
	n = int(input())
	a = input().split(' ')
	for j in a:
		count += int(j)
	if count < len(a):
		print(1)
	else:
		print(count - len(a))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	if s / n < 1:
		print(1)
		continue
	if s / n == 1:
		print(0)
		continue
	print(s - n)


x = int(input())
for _ in range(x):
	m = int(input())
	b = list(map(int, input().split()))
	s = sum(b)
	if s / m < 1:
		print(1)
		continue
	if s / m == 1:
		print(0)
		continue
	print(s - m)


t = int(input())
while t > 0:
	t = t - 1
	k = int(input())
	lst = list(map(int, input().split()))
	p = sum(lst)
	if p > 0 and p >= k:
		print(p - k)
	else:
		print('1')


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split(' ')))
	x = sum(a)
	if x == n:
		print(0)
	elif x > n:
		print(x - n)
	else:
		print(1)


for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	if sum(b) == a:
		print(0)
	elif sum(b) < a:
		print(1)
	else:
		print(sum(b) - a)


from sys import stdin
input = stdin.readline
from itertools import accumulate

def solve():
	n = int(input())
	arr = [int(char) for char in input().split()]
	total = sum(arr)
	if total == n:
		return 0
	elif total < n:
		return 1
	else:
		return total - len(arr)
for _ in range(int(input())):
	print(solve())


for _ in range(int(input())):
	n = int(input())
	a = list((int(x) for x in input().split()))
	if sum(a) / n == 1:
		print(0)
	elif sum(a) / n > 1:
		print(sum(a) - n)
	else:
		print(1)


t = int(input())
for _ in range(t):
	n = int(input())
	l = []
	l = list(map(int, input().strip().split()))
	s = sum(l)
	x = len(l)
	if s > x:
		print(s - x)
	elif s == x:
		print(0)
	else:
		print(1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s_a = sum(a)
	if s_a == n:
		print(0)
	elif s_a > n:
		print(s_a - n)
	else:
		ans = 0
		while s_a < n:
			ans += 1
			s_a += abs(s_a - n) + ans
			n += 1
		print(ans)


t = int(input())
while t > 0:
	sum = 0
	n = int(input())
	arr = []
	arr = list(map(int, input().split()[:n]))
	for i in range(0, n):
		sum = sum + arr[i]
	if sum <= 0:
		print(1)
	elif sum < n:
		print(1)
	else:
		sum = sum - n
		print(sum)
	t -= 1


t = int(input())
for i in range(t):
	l = int(input())
	a = input().split()
	n = 0
	for j in a:
		n += int(j)
	if n < 0:
		print('1')
	if n == 0:
		print('1')
	if n > 0 and n > l:
		print(n - l)
	if n > 0 and n < l:
		print('1')
	if n > 0 and n == l:
		print('0')


t = int(input())
while t > 0:
	n = int(input())
	a = [int(a) for a in input().split()]
	s = 0
	for i in a:
		s = s + i
	if s < n:
		print(1)
	else:
		print(s - n)
	t = t - 1


def matriz_arit(casos):
	for n in range(casos):
		suma = 0
		longitud = int(input())
		elementos = [int(x) for x in input().split()]
		comprobar = []
		for i in elementos:
			suma += i
		if suma <= 0 or suma < longitud:
			print(1)
		else:
			print(suma - longitud)

def main():
	casos = int(input())
	matriz_arit(casos)
main()


while True:
	try:
		t = eval(input())
		for i in range(t):
			n = eval(input())
			list0 = list(map(int, input().split()))
			if sum(list0) >= n:
				print(sum(list0) - n)
			else:
				print(1)
	except:
		break


for i in range(int(input())):
	n = input()
	arr = input().split()
	arr = [int(k) for k in arr]
	if sum(arr) <= 0:
		ans = 1
	elif sum(arr) / len(arr) == 1 and sum(arr) % len(arr) == 0:
		ans = 0
	else:
		ans = sum(arr) - len(arr)
	if ans < 0:
		ans = 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	s = input().split(' ')
	s = [int(x) for x in s]
	contador = 0
	if sum(s) / n < 1:
		contador = 1
	if sum(s) / n > 1:
		contador = sum(s) - n
	print(contador)


n = int(input())
for i in range(n):
	x = int(input())
	l = input()
	l = l.split(' ')
	l = list(map(int, l))
	l = sum(l)
	if l >= x:
		m = l - x
	else:
		m = 1
	print(m)


import math
t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	if s <= 0:
		print('1')
	elif s >= n:
		print(s - n)
	else:
		print('1')
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	if sum(x) / n == 1:
		print(0)
	elif sum(x) > n:
		print(abs(sum(x) - n))
	else:
		print(1)


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	if sum(a) > 0 and sum(a) >= len(a):
		print(sum(a) - len(a))
	else:
		print(1)


for _ in range(int(input())):
	n = int(input())
	a = [int(_) for _ in input().split()]
	print(0 if sum(a) / n == 1 else 1 if sum(a) <= 0 else 1 if sum(a) < n else sum(a) - n)


testcases = int(input())
for i in range(testcases):
	n = int(input())
	l = [int(x) for x in input().split(' ')]
	if n == sum(l):
		print(0)
	elif sum(l) < 0 or sum(l) < n:
		print(1)
	else:
		print(sum(l) - n)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if sum(arr) >= n:
		print(sum(arr) - n)
	else:
		print(1)


def main():
	for _ in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		s = sum(l)
		if s >= n:
			print(s - n)
		else:
			print(1)
main()


a = int(input())
for f in range(a):
	s = 0
	b = int(input())
	c = input().split()
	for d in range(b):
		k = int(c[d])
		s += k
	if s < b:
		print(1)
	else:
		print(s - b)


for _ in range(int(input())):
	n = int(input())
	w = [int(i) for i in input().split()]
	if sum(w) / n < 1:
		print(1)
	else:
		print(sum(w) - n)


n = int(input())
for i in range(n):
	m = int(input())
	arr = list(map(int, input().split(' ')))
	sum_ = sum(arr)
	if sum_ / m == 1:
		print(0)
	else:
		k = m + 1 - sum(arr)
		if k > 0:
			print(1)
		else:
			print(-k + 1)


t = int(input())
res = []
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	k = len(a)
	for el in a:
		s += el
	if s == k:
		res.append(0)
	elif s < k:
		res.append(1)
	elif s > k:
		res.append(s - k)
for el in res:
	print(el)


for _ in range(int(input())):
	n = int(input())
	s = input().split()
	ss = 0
	for i in s:
		ss += int(i)
	out = 1
	if ss >= n:
		out = ss - n
	print(out)