Missing numbers

★★★★★

3.7

3 votes

Open, Open, Quick Sort, Sorting, Quicksort, Algorithms, Easy, Open, Quicksort, Quicksort

Details

Submissions

Discussion

Editorial

Problem

You are given an array $A$ . You can decrement any element of the array by $1$ . This operation can be repeated any number of times. A number is said to be missing if it is the smallest positive number that is a multiple of $2$ that is not available in array $A$ . You are required to determine the maximum missing number after all possible decrements of the elements.

Input format

First line: $T$ denoting the number of test cases
For each test case:
- First line: $N$ denoting the size of the array
- Second line: $N$ space-separated integers

Output format
Print the answer for each test case in a new line.

Constraints

$1 \le T \le 10$

$1 \le N \le 10^{5}$

$0 \le A_{i} \le 10^{9}$

Sample Input

2
6
1 3 3 3 6 7
3
3 0 2

Sample Output

8
4

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

In the first sample test case, for 0 based indexing, if we decrement the $A_1$ to 2, $A_4$ to 4 and $A_5$ to 6. the array becomes $[1,2,3,3,4,6]$ . The smallest positive multiple of 2 which is not in the modified array is 8, thus the missing number is 8.
In the second sample test case, with or without decrements we can get 2 as the only multiple of 2 in the array, thus the missing number is 4.

Contributers:

Abhinandan Mittal

Akash Sharma