Empty Game

4.3

7 votes
Algorithms, Greedy Algorithms, Basics of Greedy Algorithms
Problem

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

  1. Choose one index i(1<=i<=N) such that |A[i]X|<=1 and remove A[i].
  2. Choose two indices i and j(1<=i,j<=N,ij) 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<=105

1<=A[i]<=106

Sample Input
2
4
1 3 5 2
2
6 7
Sample Output
2
1
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For test case 1:

  • Choose x=4,i=2andj=3. Remove A[2] and A[3]. Now array A=[1,2].
  • Choose x=1,i=1andj=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=1andj=2. Remove A[1] and A[2]. Now array A=[].

Hence, the minimum number of moves needed is 1.

Editor Image

?