Empty Game | Practice Problems

Empty Game

★★★★★

4.3

7 votes

Algorithms, Greedy Algorithms, Basics of Greedy Algorithms

Details

Problem

You are given an array $A$ of length $N$ . In one move, select an integer $X$ and do one of the following operations:

Choose one index $i (1 <= i <= N)$ such that $|A[i] - X| <= 1$ and remove $A[i]$ .
Choose two indices $i$ and $j (1 <= i, j <= N, i ≠ j)$ such that $|A[i] - X| <= 1$ and $|A[j] - X| <= 1$ and remove $A[i]$ and $A[j]$ from the array.

Find the minimum number of moves required to make the array empty.

Input format:

The first line contains an integer $T$ denoting the number of test cases.
The first line of each test case contains an integer $N$ denoting the length of the array.
The second line of each test case contains $N$ space-separated elements of the array $A$ .

Output format:

For each test case, print the minimum moves needed to make the array empty.

Constraints:

$1 <= T <= 10$

$1 <= N <= 10^5$

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

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For test case 1:

Choose $x = 4, i = 2\: and \: j = 3$ . Remove $A[2]$ and $A[3]$ . Now array $A = [1, 2]$ .
Choose $x = 1, i = 1\: and \:j = 2$ . Remove $A[1]$ and $A[2]$ . Now array $A=[\:]$ .

Hence, the minimum number of moves needed is $2$ .

For test case 2:

Choose $x = 6,i = 1\: and \:j = 2$ . Remove $A[1]$ and $A[2]$ . Now array $A = [\:]$ .

Hence, the minimum number of moves needed is $1$ .