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

**Task**

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 = {a_{1}, a_{2}, . . . , a_{k}}**, and an integer

*. They need to find the a way to reach*

**N***, starting from*

**N****1**, and at each step multiplying current value by any element of

*. But soon they realised that there may exist more than one way to reach*

**A***. 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.*

**N**For example, if ** N = 12** and

**then following ways exists**

*A*= 2, 3, 4```
(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

*, representing the final value to reach and the size of set*

**K***, respectively. Next line contains*

**A**`K`

space integers representing the set **.**

*A*= {a_{1}, a_{2}, . . . , a_{k}}**Constraints**

**1 <=***N*<= 10^{9}**1 <=***K*<= 20**2 <=**where*a*_{i}<= 20,*i*∈ [1,*K*]where*a*_{i}!=*a*_{j},**1 <=**AND*i*,*j*<=*K**i*!=*j*

**Note:**

*Lexicographical order:*Ifand*list*1 = [*p*_{1},*p*_{2}, . . . ,*p*_{m}]are two ordered lists, then*list*2 = [*q*_{1},*q*_{2}, . . . ,*q*_{n}]is lexicographically smaller than*list*1if any one of the following condition satisfies.*list*2AND*p*_{i}=*q*_{i},*i*∈ [1,*m*].*m*<*n*AND*p*_{i}=*q*_{i},*i*∈ [1,*k*]AND*k*<*min*(*m*,*n*)<*p*_{k+1}.*q*_{k+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) if (answer.isEmpty) List(-1) else answer.foldLeft(List(1))((acc, v) => v * acc.head :: acc).reverse } }

**Note:** This problem **(Reverse Factorization)** is generated by **HackerRank** but the solution is provided by **CodingBroz**. This tutorial is only for **Educational** and **Learning** purpose.