# 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 {