Find the Missing Number

You are given an array of n distinct numbers taken from the range \( [0, n] \) (inclusive), with exactly one number missing. Your task is to determine the missing number. One common approach is to compute the expected sum of the full range using the formula \(\frac{n(n+1)}{2}\) and then subtract the sum of the provided numbers.

For example, if n = 3 and the array is [3, 0, 1], the full range would be \(\{0,1,2,3\}\) with an expected sum of \(6\) and the given array sums to \(4\); hence the missing number is \(2\).

inputFormat

The first line of input contains an integer T denoting the number of test cases. For each test case, the first line contains an integer n representing the maximum value in the range (i.e. the numbers are from 0 to n). The next line contains n space-separated integers which form the array. If n = 0, the corresponding line will be empty. It is guaranteed that the array is missing exactly one number from the range \( [0, n] \).

outputFormat

For each test case, output the missing number on a new line.

2
3
3 0 1
1
0

2
1