# Minimum Multiple – HackerRank Solution

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

Calculi is Lambda’s older brother. Lambda is mischievous and always annoys Calculi by asking silly questions. This time around, Lambda would like to surprise Calculi by asking a challenging and interesting question. To that end, Lambda gives Calculi an array ofÂ NÂ integers,Â A = {a0, a1, . . . , aN-1}, followed byÂ KÂ queries. Each query is of two types:

• Q l r: Find the minimum positive integer,Â M, such that each element in subarrayÂ arr[l . . . r] ({al, al+1, . . . , ar})Â dividesÂ M.
• U idx val: Multiply the value atÂ idxÂ byÂ val. That isÂ a’idx = aidx x val, whereÂ a’idxÂ is the updated value.

Your task is to help Calculi tackle this challenge. For each query of typeÂ nQ l rn, find the value ofÂ M. As this value can be very large, print theÂ MÂ moduloÂ (109 + 7), i.e.,Â M % (109 + 7). For query of typeÂ nU idx valn, update the required element.

## Input Format

The first line contains an integer,Â N, which represents the length of array,Â A.
In second line, there areÂ NÂ space-separated integers,Â a0, a1, . . . , aN-1, representing the elements ofÂ A.
In third line, there is another integer,Â K, which is the count of queries to follow.
Then followsÂ KÂ lines, each representing a query of one of the types described above.

## Constraints

• 1 <= N <= 5 x 104
• 1 <= ai <= 100, where i âˆˆ[0, N – 1]
• 1 <= K <= 5 x 104
• 0 <= l <= r < N
• 0 <= idx < N
• 1 <= val <= 100

## Output Format

For each query of typeÂ `Q l r`, print the value ofÂ M % (109 + 7)Â on a new line.

Sample Input

``````5
2 5 6 1 9
7
Q 0 4
U 1 2
Q 0 2
Q 3 4
Q 2 4
U 3 8
Q 2 3``````

Sample Output

``````90
30
9
18
24``````

Explanation

Query 1 (Q 0 4):Â Calculi has to findÂ MÂ for (sub)arrayÂ A[0 . . . 4] = {2, 5, 6, 1, 9}Â which is 90.
Query 2 (U 1 2):Â a1 = a1 x 2 = 10. Now updated array isÂ A = {2, 10, 6, 1, 9}.
Query 3 (Q 0 2):Â MÂ for subarrayÂ A[0 . . . 2] = {2, 10, 6}Â isÂ 30.
Query 4 (Q 3 4):Â MÂ for subarrayÂ A[3 . . . 4] = {1, 9}Â isÂ 9.
Query 5 (Q 2 4):Â MÂ for subarrayÂ A[2 . . 4] = {6, 1, 9}Â isÂ 18.
Query 6 (U 3 8):Â Updated array isÂ A = {2, 10, 6, 8, 9}.
Query 7 (Q 2 3):Â MÂ for subarrayÂ A[2 . . . 3] = {6, 8}Â isÂ 24.

## Solution – Minimum Multiple – HackerRank Solution

Scala

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

import scala.collection.mutable
import scala.reflect.ClassTag

var st: StringTokenizer = _

def nextInt: Int = next.toInt

def nextLong: Long = next.toLong

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

def nextDouble: Double = next.toDouble

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

abstract class SegmentTree[Node, Value](seq: IndexedSeq[Value])(implicit tag: ClassTag[Node]) {
private val len: Int = seq.length

val nodes: Array[Node] = {
val defaultNode = emptyNode
Array.fill[Node](4 * len)(defaultNode)
}

def build(v: Int = 1, left: Int = 0, right: Int = len - 1): Unit = {
nodes(v) = if (left == right)
valueToNode(v, seq(left))
else {
val middle = (left + right) >> 1
build(2 * v, left, middle)
build(2 * v + 1, middle + 1, right)
combine(nodes(2 * v), nodes(2 * v + 1))
}
}

def valueToNode: (Int, Value) => Node

def add(index: Int, value: Value): Unit = traverse(index, i => nodes(i) = valueToNode(i, value))

private def traverse(index: Int, f: Int => Any): Unit = {
def inner(v: Int = 1, left: Int = 0, right: Int = len - 1): Unit = if (left == right) f(v)
else {
val middle = (left + right) >> 1
if (index <= middle) inner(2 * v, left, middle)
else inner(2 * v + 1, middle + 1, right)

nodes(v) = combine(nodes(2 * v), nodes(2 * v + 1))
}

inner()
}

def remove(index: Int, value: Value): Unit = traverse(index, nodes(_) = emptyNode)

def emptyNode: Node

def combine(leftNode: Node, rightNode: Node): Node

def query[B](leftBound: Int, rightBound: Int, f: (Int, Int, Node) => B, comb: (B, B) => B): B = {
def inner(leftBound: Int, rightBound: Int, v: Int = 1, left: Int = 0, right: Int = len - 1): B =
if (leftBound == left && rightBound == right) {
f(leftBound, rightBound, nodes(v))
} else {
val middle = (left + right) >> 1

if (rightBound <= middle)
inner(leftBound, rightBound, 2 * v, left, middle)
else if (leftBound > middle)
inner(leftBound, rightBound, 2 * v + 1, middle + 1, right)
else comb(
inner(leftBound, middle, 2 * v, left, middle),
inner(middle + 1, rightBound, 2 * v + 1, middle + 1, right)
)
}

inner(leftBound, rightBound)
}

build()
}

case class Code(seq: IndexedSeq[Int]) {
def toInt: Int = seq.indices.foldLeft(1)((acc, i) => {
var n = seq(i)
var res: Long = acc
while (n > 0) {
res = (res * prime) % Code.modulo
n -= 1
}
res.toInt
})
}

object Code {
val maxValue = 100
val primeNumbers: IndexedSeq[Int] = (2 to maxValue).filter(v => BigInt(v).isProbablePrime(10))
private val modulo = 1000000007

def apply(value: Int): Code = {
@scala.annotation.tailrec
def toPrimes(value: Int, index: Int, acc: List[Int]): List[Int] = if (index < primeNumbers.length) {
if (value % prime == 0) toPrimes(value / prime, index, (acc.head + 1) :: acc.tail)
else toPrimes(value, index + 1, 0 :: acc)
}
else acc

new Code(toPrimes(value, 0, 0 :: Nil).tail.reverse.toIndexedSeq)
}
}

class MaxTree(seq: IndexedSeq[Int]) extends SegmentTree[Code, Int](seq) {
override lazy val emptyNode: Code = Code(1)

override def valueToNode: (Int, Int) => Code = (i, v) => {
val code = Code(v)
val node = nodes(i)
Code(code.seq.indices.map(i => code.seq(i) + node.seq(i)))
}

def query(leftBound: Int, rightBound: Int): Int = super.query(leftBound, rightBound,
(_, _, code) => code, combine).toInt

override def combine(leftNode: Code, rightNode: Code): Code =
Code(leftNode.seq.indices.map(i => math.max(leftNode.seq(i), rightNode.seq(i))))
}

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

val n = sc.nextInt
val values = (0 until n).map(_ => sc.nextInt)

val tree = new MaxTree(values)

val q = sc.nextInt

(0 until q).foreach(_ => {
val tokens = sc.nextLine.split(" ")
val left = tokens(1).toInt
val right = tokens(2).toInt

op match {