InternetConnection | Topcoder Archive

Problem Statement

An apartment building needs to have its internet connectivity improved. Some floors already have routers present. However, your friendly neighborhood network technician has suggested that no two consecutive floors should be without a router. You have been tasked with figuring out how many new routers new to be purchased in order to meet that requirement. Of course, you want to minimize the cost involved, by installing as few new routers as possible.

The number of floors in the building is given in int floors and existing connections are given in int[] connections. Return the minimum number of new routers that are needed.

Definition

Class:: InternetConnection
Method:: connect
Parameters:: int, int[]
Returns:: int
Method signature:: int connect(int floors, int[] connections)
(be sure your method is public)

Notes

The floors will be numbered from 1 to floors.

Constraints

floors will be between 1 and 1000000.
connections will have between 1 and 50 elements.
The elements of connections will be all different.
The elements of connections will be in increasing order.
The elements of connections will be between 1 and floors included.

Examples

```
2
```
```
{1}
```
```
Returns: 0
```
There are two floors, one of them (the first floor) has a router so no other routers are needed.
```
10
```
```
{1,3,5,10}
```
```
Returns: 2
```
Routers are needed in floors 7 and 9, 7 and 8 or 6 and 8.
```
5
```
```
{1,2,3,4,5}
```
```
Returns: 0
```
Note that all floors have routers, so there are no routers needed.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.