{"id":7325,"date":"2022-08-11T23:00:00","date_gmt":"2022-08-11T17:30:00","guid":{"rendered":"https:\/\/www.codingbroz.com\/?p=7325"},"modified":"2022-08-06T17:45:45","modified_gmt":"2022-08-06T12:15:45","slug":"minimum-multiple-hackerrank-solution","status":"publish","type":"post","link":"https:\/\/www.codingbroz.com\/minimum-multiple-hackerrank-solution\/","title":{"rendered":"Minimum Multiple &#8211; HackerRank Solution"},"content":{"rendered":"\n<p>In this post, we will solve <strong>Minimum Multiple HackerRank Solution<\/strong>. This problem <strong>(Minimum Multiple)<\/strong> is a part of <strong>HackerRank Functional Programming<\/strong> series.<\/p>\n\n\n\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_65 ez-toc-wrap-left counter-hierarchy ez-toc-counter ez-toc-custom ez-toc-container-direction\">\n<label for=\"ez-toc-cssicon-toggle-item-6640a5e7787bf\" class=\"ez-toc-cssicon-toggle-label\"><label class=\"ez-toc-title\">Table of Contents<\/label>\n<span class=\"ez-toc-cssicon\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #0090ff;color:#0090ff\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #0090ff;color:#0090ff\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-6640a5e7787bf\" checked \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/www.codingbroz.com\/minimum-multiple-hackerrank-solution\/#Task\" title=\"Task\">Task<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/www.codingbroz.com\/minimum-multiple-hackerrank-solution\/#Input_Format\" title=\"Input Format\">Input Format<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/www.codingbroz.com\/minimum-multiple-hackerrank-solution\/#Constraints\" title=\"Constraints\">Constraints<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/www.codingbroz.com\/minimum-multiple-hackerrank-solution\/#Output_Format\" title=\"Output Format\">Output Format<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/www.codingbroz.com\/minimum-multiple-hackerrank-solution\/#Solution_%E2%80%93_Minimum_Multiple_%E2%80%93_HackerRank_Solution\" title=\"Solution &#8211; Minimum Multiple &#8211; HackerRank Solution\">Solution &#8211; Minimum Multiple &#8211; HackerRank Solution<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Task\"><\/span><strong>Task<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>Calculi is Lambda&#8217;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\u00a0<em><strong>N<\/strong><\/em>\u00a0integers,\u00a0<strong><em>A<\/em> = {a<sub>0<\/sub>, a<sub>1<\/sub>, . . . , a<sub>N-1<\/sub>}<\/strong>, followed by\u00a0<em><strong>K<\/strong><\/em>\u00a0queries. Each query is of two types:<\/p>\n\n\n\n<ul><li><strong><em>Q l r<\/em><\/strong>: Find the minimum positive integer,\u00a0<em><strong>M<\/strong><\/em>, such that each element in subarray\u00a0<strong><em>arr<\/em>[<em>l<\/em> . . . <em>r<\/em>] ({<em>a<sub>l<\/sub><\/em>, <em>a<\/em><sub><em>l+1<\/em><\/sub>, . . . , <em>a<sub>r<\/sub><\/em>})<\/strong>\u00a0divides\u00a0<em><strong>M<\/strong><\/em>.<\/li><li><strong><em>U idx val<\/em><\/strong>: Multiply the value at\u00a0<em><strong>idx<\/strong><\/em>\u00a0by\u00a0<em><strong>val<\/strong><\/em>. That is\u00a0<strong>a&#8217;<sub>idx<\/sub><\/strong> = <strong>a<sub>idx<\/sub> x <em>val<\/em><\/strong>, where\u00a0<strong>a&#8217;<sub>idx<\/sub><\/strong>\u00a0is the updated value.<\/li><\/ul>\n\n\n\n<p>Your task is to help Calculi tackle this challenge. For each query of type\u00a0<em><strong><sup>n<\/sup><\/strong><\/em><strong><em>Q l r<sup>n<\/sup><\/em><\/strong>, find the value of\u00a0<em><strong>M<\/strong><\/em>. As this value can be very large, print the\u00a0<em><strong>M<\/strong><\/em>\u00a0modulo\u00a0<strong>(10<sup>9<\/sup> + 7)<\/strong>, i.e.,\u00a0<strong><em>M<\/em> % (10<sup>9<\/sup> + 7)<\/strong>. For query of type\u00a0<strong><sup>n<\/sup><em>U idx val<sup>n<\/sup><\/em><\/strong>, update the required element.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Input_Format\"><\/span><strong>Input Format<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>The first line contains an integer,\u00a0<em><strong>N<\/strong><\/em>, which represents the length of array,\u00a0<em><strong>A<\/strong><\/em>.<br>In second line, there are\u00a0<em><strong>N<\/strong><\/em>\u00a0space-separated integers,\u00a0<strong>a<sub>0<\/sub>, a<sub>1<\/sub>, . . . , a<sub>N-1<\/sub><\/strong>, representing the elements of\u00a0<em><strong>A<\/strong><\/em>.<br>In third line, there is another integer,\u00a0<em><strong>K<\/strong><\/em>, which is the count of queries to follow.<br>Then follows\u00a0<em><strong>K<\/strong><\/em>\u00a0lines, each representing a query of one of the types described above.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Constraints\"><\/span><strong>Constraints<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<ul><li><strong>1 &lt;= <em>N<\/em> &lt;= 5 x 10<sup>4<\/sup><\/strong><\/li><li><strong>1 &lt;= <em>a<sub>i<\/sub><\/em> &lt;= 100, <\/strong>where<strong> <em>i<\/em> \u2208[0, <em>N<\/em> &#8211; 1]<\/strong><\/li><li><strong>1 &lt;= <em>K<\/em> &lt;= 5 x 10<sup>4<\/sup><\/strong><\/li><li><strong>0 &lt;= <em>l<\/em> &lt;= <em>r<\/em> &lt; <em>N<\/em><\/strong><\/li><li><strong>0 &lt;= <em>idx<\/em> &lt; <em>N<\/em><\/strong><\/li><li><strong>1 &lt;= <em>val<\/em> &lt;= 100<\/strong><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Output_Format\"><\/span><strong>Output Format<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>For each query of type\u00a0<code>Q l r<\/code>, print the value of\u00a0<strong><em>M<\/em> % (10<sup>9<\/sup> + 7)<\/strong>\u00a0on a new line.<\/p>\n\n\n\n<p><strong>Sample Input<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-ast-global-color-5-color has-ast-global-color-8-background-color has-text-color has-background\"><code>5\r\n2 5 6 1 9\r\n7\r\nQ 0 4\r\nU 1 2\r\nQ 0 2\r\nQ 3 4\r\nQ 2 4\r\nU 3 8\r\nQ 2 3<\/code><\/pre>\n\n\n\n<p><strong>Sample Output<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-ast-global-color-5-color has-ast-global-color-8-background-color has-text-color has-background\"><code>90\r\n30\r\n9\r\n18\r\n24<\/code><\/pre>\n\n\n\n<p><strong>Explanation<\/strong><\/p>\n\n\n\n<p><em>Query 1 (Q 0 4):<\/em>\u00a0Calculi has to find\u00a0<em><strong>M<\/strong><\/em>\u00a0for (sub)array\u00a0<strong><em>A<\/em>[0 . . . 4] = {2, 5, 6, 1, 9}<\/strong>\u00a0which is 90.<br><em>Query 2 (U 1 2):<\/em>\u00a0<strong><em>a<\/em>&#8216;<sub>1<\/sub> = a<sub>1<\/sub> x 2 = 10<\/strong>. Now updated array is\u00a0<strong><em>A<\/em> = {2, 10, 6, 1, 9}<\/strong>.<br><em>Query 3 (Q 0 2):<\/em>\u00a0<em><strong>M<\/strong><\/em>\u00a0for subarray\u00a0<strong><em>A<\/em>[0 . . . 2] = {2, 10, 6}<\/strong>\u00a0is\u00a0<strong>30<\/strong>.<br><em>Query 4 (Q 3 4):<\/em>\u00a0<em><strong>M<\/strong><\/em>\u00a0for subarray\u00a0<strong><em>A<\/em>[3 . . . 4] = {1, 9}<\/strong>\u00a0is\u00a0<strong>9<\/strong>.<br><em>Query 5 (Q 2 4):<\/em>\u00a0<em><strong>M<\/strong><\/em>\u00a0for subarray\u00a0<strong><em>A<\/em>[2 . . 4] = {6, 1, 9}<\/strong>\u00a0is\u00a0<strong>18<\/strong>.<br><em>Query 6 (U 3 8):<\/em>\u00a0Updated array is\u00a0<strong><em>A<\/em> = {2, 10, 6, 8, 9}<\/strong>.<br><em>Query 7 (Q 2 3):<\/em>\u00a0<em><strong>M<\/strong><\/em>\u00a0for subarray\u00a0<strong><em>A<\/em>[2 . . . 3] = {6, 8}<\/strong>\u00a0is\u00a0<strong>24<\/strong>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Solution_%E2%80%93_Minimum_Multiple_%E2%80%93_HackerRank_Solution\"><\/span><strong>Solution &#8211; Minimum Multiple &#8211; HackerRank Solution<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p><strong>Scala<\/strong><\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"scala\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">import java.io.{BufferedReader, IOException, InputStreamReader}\nimport java.util.StringTokenizer\n\nimport scala.collection.mutable\nimport scala.reflect.ClassTag\n\nclass FastReader() {\n  val br: BufferedReader = new BufferedReader(new InputStreamReader(System.in))\n  var st: StringTokenizer = _\n\n  def nextInt: Int = next.toInt\n\n  def nextLong: Long = next.toLong\n\n  def next: String = {\n    while (st == null || !st.hasMoreElements)\n      try\n        st = new StringTokenizer(br.readLine)\n      catch {\n        case e: IOException =>\n          e.printStackTrace()\n      }\n    st.nextToken\n  }\n\n  def nextDouble: Double = next.toDouble\n\n  def nextLine: String = {\n    var str = \"\"\n    try\n      str = br.readLine\n    catch {\n      case e: IOException =>\n        e.printStackTrace()\n    }\n    str\n  }\n}\n\nabstract class SegmentTree[Node, Value](seq: IndexedSeq[Value])(implicit tag: ClassTag[Node]) {\n  private val len: Int = seq.length\n\n  val nodes: Array[Node] = {\n    val defaultNode = emptyNode\n    Array.fill[Node](4 * len)(defaultNode)\n  }\n\n  def build(v: Int = 1, left: Int = 0, right: Int = len - 1): Unit = {\n    nodes(v) = if (left == right)\n      valueToNode(v, seq(left))\n    else {\n      val middle = (left + right) >> 1\n      build(2 * v, left, middle)\n      build(2 * v + 1, middle + 1, right)\n      combine(nodes(2 * v), nodes(2 * v + 1))\n    }\n  }\n\n  def valueToNode: (Int, Value) => Node\n\n  def add(index: Int, value: Value): Unit = traverse(index, i => nodes(i) = valueToNode(i, value))\n\n  private def traverse(index: Int, f: Int => Any): Unit = {\n    def inner(v: Int = 1, left: Int = 0, right: Int = len - 1): Unit = if (left == right) f(v)\n    else {\n      val middle = (left + right) >> 1\n      if (index &lt;= middle) inner(2 * v, left, middle)\n      else inner(2 * v + 1, middle + 1, right)\n\n      nodes(v) = combine(nodes(2 * v), nodes(2 * v + 1))\n    }\n\n    inner()\n  }\n\n  def remove(index: Int, value: Value): Unit = traverse(index, nodes(_) = emptyNode)\n\n  def emptyNode: Node\n\n  def combine(leftNode: Node, rightNode: Node): Node\n\n  def query[B](leftBound: Int, rightBound: Int, f: (Int, Int, Node) => B, comb: (B, B) => B): B = {\n    def inner(leftBound: Int, rightBound: Int, v: Int = 1, left: Int = 0, right: Int = len - 1): B =\n      if (leftBound == left &amp;&amp; rightBound == right) {\n        f(leftBound, rightBound, nodes(v))\n      } else {\n        val middle = (left + right) >> 1\n\n        if (rightBound &lt;= middle)\n          inner(leftBound, rightBound, 2 * v, left, middle)\n        else if (leftBound > middle)\n          inner(leftBound, rightBound, 2 * v + 1, middle + 1, right)\n        else comb(\n          inner(leftBound, middle, 2 * v, left, middle),\n          inner(middle + 1, rightBound, 2 * v + 1, middle + 1, right)\n        )\n      }\n\n    inner(leftBound, rightBound)\n  }\n\n  build()\n}\n\ncase class Code(seq: IndexedSeq[Int]) {\n  def toInt: Int = seq.indices.foldLeft(1)((acc, i) => {\n    var n = seq(i)\n    var res: Long = acc\n    val prime = Code.primeNumbers(i)\n    while (n > 0) {\n      res = (res * prime) % Code.modulo\n      n -= 1\n    }\n    res.toInt\n  })\n}\n\nobject Code {\n  val maxValue = 100\n  val primeNumbers: IndexedSeq[Int] = (2 to maxValue).filter(v => BigInt(v).isProbablePrime(10))\n  private val modulo = 1000000007\n\n  def apply(value: Int): Code = {\n    @scala.annotation.tailrec\n    def toPrimes(value: Int, index: Int, acc: List[Int]): List[Int] = if (index &lt; primeNumbers.length) {\n      val prime = primeNumbers(index)\n      if (value % prime == 0) toPrimes(value \/ prime, index, (acc.head + 1) :: acc.tail)\n      else toPrimes(value, index + 1, 0 :: acc)\n    }\n    else acc\n\n    new Code(toPrimes(value, 0, 0 :: Nil).tail.reverse.toIndexedSeq)\n  }\n}\n\nclass MaxTree(seq: IndexedSeq[Int]) extends SegmentTree[Code, Int](seq) {\n  override lazy val emptyNode: Code = Code(1)\n\n  override def valueToNode: (Int, Int) => Code = (i, v) => {\n    val code = Code(v)\n    val node = nodes(i)\n    Code(code.seq.indices.map(i => code.seq(i) + node.seq(i)))\n  }\n\n  def query(leftBound: Int, rightBound: Int): Int = super.query(leftBound, rightBound,\n    (_, _, code) => code, combine).toInt\n\n  override def combine(leftNode: Code, rightNode: Code): Code =\n    Code(leftNode.seq.indices.map(i => math.max(leftNode.seq(i), rightNode.seq(i))))\n}\n\nobject Solution {\n  def main(args: Array[String]): Unit = {\n    val sc = new FastReader\n\n    val n = sc.nextInt\n    val values = (0 until n).map(_ => sc.nextInt)\n\n    val tree = new MaxTree(values)\n\n    val q = sc.nextInt\n    val answer = new mutable.Queue[Int]()\n\n    (0 until q).foreach(_ => {\n      val tokens = sc.nextLine.split(\" \")\n      val op = tokens.head.head\n      val left = tokens(1).toInt\n      val right = tokens(2).toInt\n\n      op match {\n        case 'Q' => answer.enqueue(tree.query(left, right))\n        case 'U' => tree.add(left, right)\n      }\n    })\n\n    println(answer.mkString(\"\\n\"))\n  }\n}\n<\/pre>\n\n\n\n<p><strong>Note:<\/strong> This problem <strong>(<a href=\"https:\/\/www.hackerrank.com\/challenges\/minimum-multiple\/problem\" target=\"_blank\" rel=\"noreferrer noopener nofollow\">Minimum Multiple<\/a>)<\/strong> is generated by <strong><a href=\"https:\/\/www.hackerrank.com\/\" target=\"_blank\" rel=\"noreferrer noopener nofollow\">HackerRank<\/a><\/strong> but the solution is provided by <strong><a href=\"https:\/\/www.codingbroz.com\/\">CodingBroz<\/a><\/strong>. This tutorial is only for <strong>Educational<\/strong> and <strong>Learning<\/strong> purpose.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In this post, we will solve Minimum Multiple HackerRank Solution. This problem (Minimum Multiple) is a part of HackerRank Functional Programming series.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[9,684],"tags":[692],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts\/7325"}],"collection":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/comments?post=7325"}],"version-history":[{"count":4,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts\/7325\/revisions"}],"predecessor-version":[{"id":7330,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts\/7325\/revisions\/7330"}],"wp:attachment":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/media?parent=7325"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/categories?post=7325"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/tags?post=7325"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}