### PROBLEM LINK:

**Author:** Sunny Aggarwal

**Tester:** Shiplu Hawlader

**Editorialist:** Lalit Kundu

### DIFFICULTY:

MEDIUM

### PRE-REQUISITES:

Maths

### PROBLEM:

**K** numbers denoted by array **B** from set **S = [1,2,…N]** are removed. Find the minimum number **X** such that **X** cannot be formed by picking a set of numbers from **S**.

1 ≤ **N** ≤ 10^{9}

1 ≤ K ≤ 5*10^{5}

### EXPLANATION:

If the minimum **X** is odd, second player wins, else first player wins.

So, we just need to find **X**.

If **k == 0**, then all numbers from 1 to **(N * (N + 1)) / 2** are possible to form.

Consider a special case, **X = 1** if 1 has been removed from set **[1…N]**.

Based on this observation, we can first sort the array **B** in ascending order.

**Fact**: Let’s say all numbers from 1 to **i** are available, then we can form every number till **(i * (i + 1)) / 2**.

Let’s consider last reachable number till now is **M**. So now we want to form numbers **M + 1**, **M + 2** and so on.

We have generated all numbers till **M** now and now we want to generate **M + 1** and the new number that available number we get is say **B _{i} + 1**, we can’t generate

**M + 1**, if

**B**. In such a case

_{i}+ 1 > M + 1**X**will be

**M + 1**.

Or else, we know that all numbers between

**B**and

_{i}+ 1**B**(both inclusive) are available. So, we know that all numbers from

_{i+1}- 1**M + 1**to

**M + S**are also available, where

**S**= sum of all numbers between

**B**and B_{i+1} - 1(both inclusive).

_{i}+ 1We do this for all unavailable numbers in sorted traversal to get the maximum unachievable sum **M**.

Complexity: **O(K log K)**

You might want to read this, for better clarity.