# Fighting Armies – HackerRank Solution

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

As a General, you initially haveÂ NÂ armies numbered fromÂ 1Â toÂ NÂ under your command. Each army consists of some number of soldiers, and each soldier is assigned an integer,Â c, representative of his or her combat ability. Since, you are responsible for all of them, you want to give orders to your armies and query them about their current state. You must handleÂ QÂ events, where each event is one of theÂ 4Â following types:

1. findStrongest(i)Â – Print the maximum combat ability of any soldier in armyÂ i.
2. strongestDied(i)Â – A soldier with the maximum combat ability among all soldiers in armyÂ iÂ has died, so the soldier is removed from the army.
3. recruit(i, c)Â – A soldier with combat abilityÂ cÂ has joined armyÂ i.
4. merge(i, j) – ArmiesÂ iÂ andÂ jÂ are merged into a single armyÂ i, and armyÂ jÂ is removed (ceases to exist).

Note:Â The input can be quite large, so we suggest you use fast I/O methods.

## Input Format

The first line containsÂ 2Â space-separated integers,Â NÂ (the number of armies you command) andÂ QÂ (the number of events taking place), respectively. Each of theÂ QÂ subsequent lines describes a single event.

Each event first contains an integer,Â , describing the event type.
IfÂ t = 1Â orÂ t = 2, the line containsÂ 1Â more integer denoting the parameter of the event.
IfÂ t = 3Â orÂ t = 4, the line containsÂ 2Â more integers denoting the respective parameters of the event.

## Constraints

• 1 <= N <= 1100000
• 1 <= Q <= 2200000
• 1 <= c <= 107
• 1 <= i, j <= N, where i != j
• Indices of armies in the input represent valid armies at the time they are given.

## Output Format

For each event of typeÂ 1, print a single line containingÂ 1Â integer denoting the answer for the event.

Sample Input

``````2 6
3 1 10
3 2 20
4 1 2
1 1
2 1
1 1``````

Sample Output

``````20
10``````

Explanation

Here is a breakdown of each event:

1. A soldier having combat abilityÂ c = 10Â is added to armyÂ 1.
2. A soldier having combat abilityÂ c = 20Â is added to armyÂ 2.
3. ArmiesÂ 1Â andÂ 2Â are merged into armyÂ 1Â (and armyÂ 2Â no longer exists).
4. The maximum combat ability of a soldier in armyÂ 1Â isÂ 20.
5. The soldier having combat abilityÂ 20Â is removed from armyÂ 1.
6. The maximum combat ability of a soldier in armyÂ 1Â isÂ 10.

## Solution – Fighting Armies – HackerRank Solution

Scala

```import java.io.{BufferedReader, IOException, InputStreamReader}
import java.util.StringTokenizer

import scala.collection.immutable.TreeMap

var st: StringTokenizer = _

def nextInt: Int = next.toInt

def next: String = {
while (st == null || !st.hasMoreElements) try
catch {
case e: IOException =>
e.printStackTrace()
}
st.nextToken
}

def nextLong: Long = next.toLong

def nextDouble: Double = next.toDouble

def nextLine: String = {
var str = ""
try
catch {
case e: IOException =>
e.printStackTrace()
}
str
}
}

trait Army {
def strongest: Int

def values: TreeMap[Int, Int]

def remove(): Army = new RemovedArmy(this)

def merge(that: Army): Army =
if (this.isEmpty) that
else if (that.isEmpty) this
else new MergedArmy(this, that)

def isEmpty: Boolean = false
}

case object Empty extends Army {
override def isEmpty: Boolean = true

override def strongest: Int = throw new Exception("Strongest of empty army")

override def add(c: Int): Army = new SingleArmy(c)

override def remove(): Army = throw new Exception("Remove from empty army")

override def merge(that: Army): Army = that

override def values: TreeMap[Int, Int] = throw new Exception("Values of empty army")
}

class SingleArmy(val strongest: Int) extends Army {
override lazy val values: TreeMap[Int, Int] = TreeMap(strongest -> 1)

override def remove(): Army = Empty
}

class AddedArmy(army: Army, c: Int) extends Army {
override lazy val strongest: Int = math.max(army.strongest, c)

override lazy val values: TreeMap[Int, Int] = army.values + (c -> (army.values.getOrElse(c, 0) + 1))
}

class RemovedArmy(army: Army) extends Army {
override lazy val strongest: Int = values.lastKey

override lazy val values: TreeMap[Int, Int] = {
val (key, value) = army.values.last
if (value == 1) {
army.values - key
} else {
army.values + (key -> (value - 1))
}
}
}

class MergedArmy(left: Army, right: Army) extends Army {
override lazy val strongest: Int = math.max(left.strongest, right.strongest)

override lazy val values: TreeMap[Int, Int] = {
left.values.foldLeft(right.values)((acc, v) => {
val nextValue = acc.getOrElse(v._1, 0) + v._2
acc + (v._1 -> nextValue)
})
}
}

object Solution {
def main(args: Array[String]): Unit = {

val n = sc.nextInt
val q = sc.nextInt

val armies = Array.fill[Army](n)(Empty)

var index = 0

(0 until q).foreach(_ => {
val tokens = sc.nextLine.split(" ").map(_.toInt)

val first = tokens(1) - 1
lazy val second = tokens(2)

event match {
case 1 => //Find
index += 1
case 2 => //Kill
armies(first) = armies(first).remove()
case 3 => //Recruit