TopPilot | Topcoder Archive

Problem Statement

TopPilot airlines is committed to customer service and convenience. Thus, it is not simply enough to have a flight from San Francisco, CA to Hartford, CT. There must be a direct flight.

You will be given a String[] representing one-way flight paths. For each element in the String[], the element index is the departure airport number (0-indexed, so the first element is airport 0) and the element is a comma-delimited list of airport numbers to which there is a direct flight from the departure airport.

Write a method that, given these one-way flight paths, adds direct one-way flights between airports that are currently connected by non-direct one-way flights. For example, if there is a direct flight from SFO to JFK and a direct flight from JFK to LAX, and not a direct flight from SFO to LAX, then add a direct flight from SFO to LAX. Do not, however, add a direct flight from an airport to itself, even if a loop exists. Once this is done, the method should return the total number of flights provided by TopPilot airlines.

Definition

Class:: TopPilot
Method:: addFlights
Parameters:: String[]
Returns:: int
Method signature:: int addFlights(String[] destinations)
(be sure your method is public)

Notes

If the destination airport does not appear as an element in destinations (which is always the case when it is greater than 19), there are no departing flights from that airport.
Leading zeroes in the numbers are allowed.

Constraints

No airport will have a direct flight to itself.
destinations will have between 1 and 20 elements, inclusive.
each element of destinations will contain only the characters '0' through '9', and commas ','.
each element of destinations will be a comma delimited list of integers, with no numbers repeated, and no leading, trailing, or extra commas.
each element of destinations will be contain between 1 and 50 characters, inclusive.
destination airport numbers will be between 0 and 50, inclusive.

Examples

```
{"1","2","3"}
```
```
Returns: 6
```
There is a flight from airport 0 to airport 1, from 1 to 2, and from 2 to 3. We add a direct flight from 0 to 2, from 1 to 3, and from 0 to 3 (note that 3 is not an element, so it has no departing flights).
```
{"1","02","3","4,5"}
```
```
Returns: 14
```
We add flights from 0 to 2, 3, 4, and 5. We add flights from 1 to 3, 4, and 5. We add flights from 2 to 4 and 5. Together with the 5 flights we already have, there are 14 total.
```
{"1,2","0,2","1"}
```
```
Returns: 6
```
The only added flight is from 2 to 0.

{"1,5,7,8,13,15,16,23,26,35,32,41"
,"0,2,5,6,7,15,18,21,25,31,34,41,49,50"
,"5,10,15,20,25,30,35,40,45,50"}

Returns: 62

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.