NINJA5 - K NUMBERS

no tags 

Problem statement:

 

You are given N numbers from 1 to N. Now, your task is to choose some numbers from the N numbers (including 1 & N) such that no two numbers are consecutive. As this is easy, you are given an extra task. You have to definitely choose K numbers which are given. Find the maximum number of numbers that you can choose in such a way.

 

Input:

 

The first line has an integer T, the number of test cases.

Then for each test case, the first line has two integers N and K.

Then the next line has K numbers which you should definitely chooose.

 

Output:

 

For each test case, print the maximum number of numbers that you can choose.

 

Constraints:

 

1 <= T <= 100

2 <= N <= 2 x 10 ^ 6

1 <= K <= N / 2

1 <= X[1...K] <= N

 

Sample input:

 

1

8 2

6 2

 

Sample output:

4


hide comments
anirudnits: 2018-11-17 09:11:59

if any of the two given K numbers are already consecutive, then just print 0. Worked for me!

nadstratosfer: 2018-04-24 19:47:04

Can't pass in raw Python and O(klogk) slower than O(n) in PyPy. Poorly set problem.

singlasahil221: 2017-07-23 07:15:50

Very easy.AC in one go.O(n) solution exists.

bsiddhartha: 2017-06-20 07:06:23

no sorting :) just take char array of size max n.and O(n+t)solution

roshanarya905: 2017-06-18 12:28:34

qsort giving TLE why? @himanshuz1

Last edit: 2017-06-18 12:33:46
manjur1996: 2016-10-28 13:28:50

need to tighten the time.... O(n) easily excepted

himanshu kumar: 2016-07-21 13:39:17

O(n+k) solution passes it easily... while sorting gives tle

hodobox: 2016-07-04 07:51:27

My code does not account for the already selected numbers being consecutive

Piyush Kumar: 2016-06-19 20:58:36

If the question can be done in O(n), I think the constraints can be a little tighter. My O(nlogn) passed comfortably!

Admin Deepak Baghel: 2016-06-09 12:54:58

i think there is bug in test cases may be any two of the given K numbers are consecutive already.

Last edit: 2016-06-09 12:59:49

Added by:mombassa
Date:2016-02-17
Time limit:0.200s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY