# Reverse Factorization – HackerRank Solution

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

Contents

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,Â Reverse Factorization. They were given a set of integer,Â A = {a1, a2, . . . , ak}, and an integerÂ N. They need to find the a way to reachÂ N, starting fromÂ 1, and at each step multiplying current value by any element ofÂ A. But soon they realised that there may exist more than one way to reachÂ N. 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.

For example, ifÂ N = 12Â andÂ A = 2, 3, 4Â then following ways exists

``````(a) 1  ->  2  ->  4  ->  12
x2     x2     x3

(b) 1  ->  4  ->  12
x4     x3

(c) 1  ->  3  ->  12
x3     x4``````

HereÂ `(a)`Â is not the minimal state, as it hasÂ 4Â states in total. WhileÂ `(b)`Â andÂ `(c)`Â are contenders for answer, both having 3 states,Â `(c)`Â is lexicographically smaller thanÂ `(b)`Â so it is the answer. In this case you have to printÂ `1 3 12`. If there exists no way to reachÂ NÂ printÂ `-1`.

## Input Format

Input contains two lines where first line contains two space separated integer,Â NÂ andÂ K, representing the final value to reach and the size of setÂ A, respectively. Next line containsÂ `K`Â space integers representing the setÂ A = {a1, a2, . . . , ak}.

## Constraints

• 1 <= N <= 109
• 1 <= K <= 20
• 2 <= ai <= 20, where i âˆˆ [1, K]
• ai != aj, where 1 <= i, j <= K AND i != j

Note:

• Lexicographical order:Â IfÂ list1 = [p1, p2, . . . , pm]Â andÂ list2 = [q1, q2, . . . , qn]Â are two ordered lists, thenÂ list1Â is lexicographically smaller thanÂ list2Â if any one of the following condition satisfies.
• pi = qi, i âˆˆ [1, m]Â ANDÂ m < n.
• pi = qi, i âˆˆ [1, k]Â ANDÂ k < min(m, n)Â ANDÂ pk+1 < qk+1.
• You need to find theÂ lexigraphically smallestÂ series among those solutions which contains the least number of states.

## Output Format

Print the steps to reachÂ NÂ if it exists. Otherwise printÂ `-1`.

Sample Input 0

``````12 3
2 3 4``````

Sample Output 0

``1 3 12``

Explanation 0

This is the same case which is explaned above.

Sample Input 1

``````15 5
2 10 6 9 11``````

Sample Output 1

``-1``

Explanation 1

Here no way exists so that we can reachÂ 15Â starting fromÂ 1.

Sample Input 2

``````72 9
2 4 6 9 3 7 16 10 5
``````

Sample Output 2

``1 2 8 72``

Explanation 2

There are multiple ways to reachÂ `72`Â using these 8 numbers. Out of which following 6 ways consists of minimal states (4).

``````States          =>  Multiplication operation
1   9  18  72  =>      (x9, x2, x4)
1   4  36  72  =>      (x4, x9, x2)
1   2   8  72  =>      (x2, x4, x9)
1   2  18  72  =>      (x2, x9, x4)
1   4   8  72  =>      (x4, x2, x9)
1   9  36  72  =>      (x9, x4, x2)``````

As seriesÂ `1 2 8 72`Â is lexicographically smallest, it is the answer.

## Solution – Reverse Factorization – HackerRank Solution

Scala

```import java.util.Scanner

import scala.collection.mutable

object Solution {
private val data = mutable.Map[(Int, List[Int]), List[Int]]()

def main(args: Array[String]): Unit = {
val sc = new Scanner(System.in)

val n = sc.nextInt
val k = sc.nextInt
val a = (0 until k).map(_ => sc.nextInt).sortBy(-_).toList

println(solve(n, a).mkString(" "))
}

def solve(n: Int, a: List[Int]): List[Int] = {
def inner(n: Int, a: List[Int], acc: List[Int]): List[Int] = data.getOrElseUpdate((n, a), if (n == 1) acc
else a match {
case Nil => Nil
case v :: vs =>
val first = if (n % v == 0) inner(n / v, a, v :: acc) else Nil
val second = inner(n, vs, acc)
if (first.isEmpty || second.nonEmpty && second.size < first.size) second else first
})

val answer = inner(n, a, Nil)