# Prison Transport – HackerRank Solution

In this post, we will solve Prison Transport HackerRank Solution. This problem (Prison Transport) is a part of HackerRank Functional Programming series.

There are N inmates numbered between [1, N] in a prison. These inmates have superhuman strength because they have drunk a special concoction made by Dr. Evil. They have to be transported by some buses to a new facility. But they are bound by special chains which are made from strong carbon fibres. Each inmate is either chained alone or is chained in a group along with one or more inmates. A group of inmates are those who are directly or indirectly connected to each other. Only one group can be transported per bus.

There are buses which will charge fixed amount bucks for transferring inmates. Charges are directly proportional to the capacity of bus. If a bus charge K bucks then it can carry upto K2 inmates at one time. Buses are available for all positive integral cost ranging from [1, 2, 3, …]. A bus can be used multiple times, and each time it will charge. Note that a bus can also transfer less number of inmates than it’s capacity.

Find the minimal cost to transport all the inmates.

## Input

The first line containsÂ NÂ representing the number of inmates. Second line contains another integer,Â M, number of pairs of inmates who are handcuffed together. Then followsÂ MÂ lines. Each of these lines contains two integers,Â P Q, which means inmate numberedÂ PÂ is handcuffed to inmate numberedÂ Q.

## Output

For the given arrangement, print the minimal cost which can be incurred while transferring inmates.

## Constraints

• 2 â‰¤Â NÂ â‰¤ 100000
• 1 â‰¤Â MÂ â‰¤ min(N*(N-1)/2, 100000)
• 1 â‰¤Â P, QÂ â‰¤ N
• PÂ â‰ Â Q

Sample Input

``````4
2
1 2
1 4``````

Sample Output

``3``

Explanation

InmatesÂ #1,Â #2,Â #4Â are connected to each other (`1--2--4`) so they lies in a single group. So a bus of costÂ 2Â (with capacity 22Â = 4) is required to carry them. Inmate #3 is not handcuffed with anyother. So he can be transported in a bus of cost 1 (with capacity 12Â = 1).

## Solution – Prison Transport – HackerRank Solution

Scala

```import java.util.Scanner

object Solution {
def main(args: Array[String]): Unit = {
val sc = new Scanner(System.in)

val n = sc.nextInt
val m = sc.nextInt
val pairs = (0 until m).map(_ => (sc.nextInt, sc.nextInt))

sc.close()

case class Prisoner(id: Int, links: Set[Int])

val links: Map[Int, Prisoner] = (pairs ++ pairs.map { case (x, y) => (y, x) })
.groupBy(_._1)
.map { case (key, list) => key -> Prisoner(key, list.map(_._2).toSet) }

def split(links: Map[Int, Prisoner]): List[Int] = {
def removePrisoner(links: Map[Int, Prisoner], prisoner: Prisoner): Map[Int, Prisoner] =

case class Accumulator(links: Map[Int, Prisoner], sum: Int)
def extractChain(links: Map[Int, Prisoner], prisoner: Prisoner, acc: Int = 0): Accumulator = {
} else acc
})
}

@scala.annotation.tailrec
}