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.


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.


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


  • 2 ≤ N ≤ 100000
  • 1 ≤ M ≤ min(N*(N-1)/2, 100000)
  • 1 ≤ P, Q ≤ N
  • P ≠ Q

Sample Input

1 2
1 4

Sample Output



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


import java.util.Scanner

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

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


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

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

    def split(links: Map[Int, Prisoner]): List[Int] = {
      def removePrisoner(links: Map[Int, Prisoner], prisoner: Prisoner): Map[Int, Prisoner] =
        prisoner.links.foldLeft(links -, id) => links.updated(id, Prisoner(id, links(id).links -

      case class Accumulator(links: Map[Int, Prisoner], sum: Int)
      def extractChain(links: Map[Int, Prisoner], prisoner: Prisoner, acc: Int = 0): Accumulator = {
        prisoner.links.foldLeft(Accumulator(removePrisoner(links, prisoner), 1))((acc, id) => {
          if (acc.links.contains(id)) {
            val nextAcc = extractChain(acc.links, acc.links(id))
            Accumulator(nextAcc.links, acc.sum + nextAcc.sum)
          } else acc

      def findLinks(links: Map[Int, Prisoner], sums: List[Int]): List[Int] = if (links.isEmpty) sums else {
        val prisoner = links.values.head
        val nextAcc = extractChain(links, prisoner)
        findLinks(nextAcc.links, nextAcc.sum :: sums)

      findLinks(links, Nil)

    val chains = split(links)
    val singleCount = n - chains.sum

    println( => math.ceil(math.sqrt(v)).toInt).sum + singleCount)

Note: This problem (Prison Transport) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.

Leave a Comment

Your email address will not be published. Required fields are marked *