{"id":7357,"date":"2022-08-13T23:00:00","date_gmt":"2022-08-13T17:30:00","guid":{"rendered":"https:\/\/www.codingbroz.com\/?p=7357"},"modified":"2022-08-08T12:56:55","modified_gmt":"2022-08-08T07:26:55","slug":"reverse-factorization-hackerrank-solution","status":"publish","type":"post","link":"https:\/\/www.codingbroz.com\/reverse-factorization-hackerrank-solution\/","title":{"rendered":"Reverse Factorization &#8211; HackerRank Solution"},"content":{"rendered":"\n<p>In this post, we will solve <strong>Reverse Factorization HackerRank Solution<\/strong>. This problem <strong>(Reverse Factorization)<\/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-6635faf2752da\" 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-6635faf2752da\" 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\/reverse-factorization-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\/reverse-factorization-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\/reverse-factorization-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\/reverse-factorization-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\/reverse-factorization-hackerrank-solution\/#Solution_%E2%80%93_Reverse_Factorization_%E2%80%93_HackerRank_Solution\" title=\"Solution &#8211; Reverse Factorization &#8211; HackerRank Solution\">Solution &#8211; Reverse Factorization &#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>At the time when Pythagoreanism was prevalent, people were also focused on different ways to factorize a number. In one class, Pythagoras asked his disciples to solve one such problem,\u00a0<em>Reverse Factorization<\/em>. They were given a set of integer,\u00a0<strong><em>A<\/em> = {a<sub>1<\/sub>, a<sub>2<\/sub>, . . . , a<sub>k<\/sub>}<\/strong>, and an integer\u00a0<em><strong>N<\/strong><\/em>. They need to find the a way to reach\u00a0<em><strong>N<\/strong><\/em>, starting from\u00a0<strong>1<\/strong>, and at each step multiplying current value by any element of\u00a0<em><strong>A<\/strong><\/em>. But soon they realised that there may exist more than one way to reach\u00a0<em><strong>N<\/strong><\/em>. So they decided to find a way in which number of states are least. All of sudden they started on this new problem. People solved it and then started shouting their answer. CRAP!!!. There still exists multiple answers. So finally after much consideration, they settled on the lexicographically smallest series among those solutions which contains the least number of states.<\/p>\n\n\n\n<p>For example, if\u00a0<strong><em>N<\/em> = 12<\/strong>\u00a0and\u00a0<strong><em>A<\/em> = 2, 3, 4<\/strong>\u00a0then following ways exists<\/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>(a) 1  ->  2  ->  4  ->  12\r\n       x2     x2     x3\r\n\r\n(b) 1  ->  4  ->  12\r\n       x4     x3\r\n\r\n(c) 1  ->  3  ->  12\r\n       x3     x4<\/code><\/pre>\n\n\n\n<p>Here\u00a0<code>(a)<\/code>\u00a0is not the minimal state, as it has\u00a0<strong>4<\/strong>\u00a0states in total. While\u00a0<code>(b)<\/code>\u00a0and\u00a0<code>(c)<\/code>\u00a0are contenders for answer, both having 3 states,\u00a0<code>(c)<\/code>\u00a0is lexicographically smaller than\u00a0<code>(b)<\/code>\u00a0so it is the answer. In this case you have to print\u00a0<code>1 3 12<\/code>. If there exists no way to reach\u00a0<em><strong>N<\/strong><\/em>\u00a0print\u00a0<code>-1<\/code>.<\/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>Input contains two lines where first line contains two space separated integer,\u00a0<em><strong>N<\/strong><\/em>\u00a0and\u00a0<em><strong>K<\/strong><\/em>, representing the final value to reach and the size of set\u00a0<em><strong>A<\/strong><\/em>, respectively. Next line contains\u00a0<code>K<\/code>\u00a0space integers representing the set\u00a0<strong><em>A<\/em> = {a<sub>1<\/sub>, a<sub>2<\/sub>, . . . , a<sub>k<\/sub>}<\/strong>.<\/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;= 10<sup>9<\/sup><\/strong><\/li><li><strong>1 &lt;= <em>K<\/em> &lt;= 20<\/strong><\/li><li><strong>2 &lt;= <em>a<\/em><sub>i<\/sub> &lt;= 20,<\/strong> where <strong><em>i<\/em> \u2208 [1, <em>K<\/em>]<\/strong><\/li><li><strong><em>a<\/em><sub>i<\/sub> != <em>a<\/em><sub>j<\/sub>, <\/strong>where <strong>1 &lt;= <em>i<\/em>, <em>j<\/em> &lt;= <em>K<\/em> <\/strong>AND <strong><em>i<\/em> != <em>j<\/em><\/strong><\/li><\/ul>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ul><li><em>Lexicographical order:<\/em>\u00a0If\u00a0<strong><em>list<\/em>1 = [<em>p<\/em><sub>1<\/sub>, <em>p<\/em><sub>2<\/sub>, . . . , <em>p<\/em><sub>m<\/sub>]<\/strong>\u00a0and\u00a0<strong><em>list<\/em>2 = [<em>q<\/em><sub>1<\/sub>, <em>q<\/em><sub>2<\/sub>, . . . , <em>q<\/em><sub>n<\/sub>]<\/strong>\u00a0are two ordered lists, then\u00a0<strong><em>list<\/em>1<\/strong>\u00a0is lexicographically smaller than\u00a0<strong><em>list<\/em>2<\/strong>\u00a0if any one of the following condition satisfies.<ul><li><strong><em>p<\/em><sub>i<\/sub> = <em>q<\/em><sub>i<\/sub>, <em>i<\/em> \u2208 [1, <em>m<\/em>]<\/strong>\u00a0AND\u00a0<strong><em>m<\/em> &lt; <em>n<\/em><\/strong>.<\/li><li><strong><em>p<\/em><sub>i<\/sub> = <em>q<\/em><sub>i<\/sub>, <em>i<\/em> \u2208 [1, <em>k<\/em>]<\/strong>\u00a0AND\u00a0<strong><em>k<\/em> &lt; <em>min<\/em>(<em>m<\/em>, <em>n<\/em>)<\/strong>\u00a0AND\u00a0<strong><em>p<\/em><sub>k+1<\/sub><\/strong> &lt; <strong><em>q<\/em><sub>k+1<\/sub><\/strong>.<\/li><\/ul><\/li><li>You need to find the\u00a0<em>lexigraphically smallest<\/em>\u00a0series among those solutions which contains the least number of states.<\/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>Print the steps to reach\u00a0<em><strong>N<\/strong><\/em>\u00a0if it exists. Otherwise print\u00a0<code>-1<\/code>.<\/p>\n\n\n\n<p><strong>Sample Input 0<\/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>12 3\r\n2 3 4<\/code><\/pre>\n\n\n\n<p><strong>Sample Output 0<\/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>1 3 12<\/code><\/pre>\n\n\n\n<p><strong>Explanation 0<\/strong><\/p>\n\n\n\n<p>This is the same case which is explaned above.<\/p>\n\n\n\n<p><strong>Sample Input 1<\/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>15 5\r\n2 10 6 9 11<\/code><\/pre>\n\n\n\n<p><strong>Sample Output 1<\/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>-1<\/code><\/pre>\n\n\n\n<p><strong>Explanation 1<\/strong><\/p>\n\n\n\n<p>Here no way exists so that we can reach\u00a0<strong>15<\/strong>\u00a0starting from\u00a0<strong>1<\/strong>.<\/p>\n\n\n\n<p><strong>Sample Input 2<\/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>72 9\r\n2 4 6 9 3 7 16 10 5\r<\/code><\/pre>\n\n\n\n<p><strong>Sample Output 2<\/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>1 2 8 72<\/code><\/pre>\n\n\n\n<p><strong>Explanation 2<\/strong><\/p>\n\n\n\n<p>There are multiple ways to reach\u00a0<code>72<\/code>\u00a0using these 8 numbers. Out of which following 6 ways consists of minimal states (4).<\/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>States          =>  Multiplication operation\r\n 1   9  18  72  =>      (x9, x2, x4)\r\n 1   4  36  72  =>      (x4, x9, x2)\r\n 1   2   8  72  =>      (x2, x4, x9)\r\n 1   2  18  72  =>      (x2, x9, x4)\r\n 1   4   8  72  =>      (x4, x2, x9)\r\n 1   9  36  72  =>      (x9, x4, x2)<\/code><\/pre>\n\n\n\n<p>As series\u00a0<code>1 2 8 72<\/code>\u00a0is lexicographically smallest, it is the answer.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Solution_%E2%80%93_Reverse_Factorization_%E2%80%93_HackerRank_Solution\"><\/span><strong>Solution &#8211; Reverse Factorization &#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.util.Scanner\n\nimport scala.collection.mutable\n\nobject Solution {\n  private val data = mutable.Map[(Int, List[Int]), List[Int]]()\n\n  def main(args: Array[String]): Unit = {\n    val sc = new Scanner(System.in)\n\n    val n = sc.nextInt\n    val k = sc.nextInt\n    val a = (0 until k).map(_ => sc.nextInt).sortBy(-_).toList\n\n    println(solve(n, a).mkString(\" \"))\n  }\n\n  def solve(n: Int, a: List[Int]): List[Int] = {\n    def inner(n: Int, a: List[Int], acc: List[Int]): List[Int] = data.getOrElseUpdate((n, a), if (n == 1) acc\n    else a match {\n      case Nil => Nil\n      case v :: vs =>\n        val first = if (n % v == 0) inner(n \/ v, a, v :: acc) else Nil\n        val second = inner(n, vs, acc)\n        if (first.isEmpty || second.nonEmpty &amp;&amp; second.size &lt; first.size) second else first\n    })\n\n    val answer = inner(n, a, Nil)\n    if (answer.isEmpty) List(-1) else answer.foldLeft(List(1))((acc, v) => v * acc.head :: acc).reverse\n  }\n}\n<\/pre>\n\n\n\n<p><strong>Note:<\/strong> This problem <strong>(<a href=\"https:\/\/www.hackerrank.com\/challenges\/reverse-factorization\/problem\" target=\"_blank\" rel=\"noreferrer noopener nofollow\">Reverse Factorization<\/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 Reverse Factorization HackerRank Solution. This problem (Reverse Factorization) 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\/7357"}],"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=7357"}],"version-history":[{"count":3,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts\/7357\/revisions"}],"predecessor-version":[{"id":7360,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts\/7357\/revisions\/7360"}],"wp:attachment":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/media?parent=7357"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/categories?post=7357"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/tags?post=7357"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}