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:*Â IfÂÂ andÂ*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*1Â if any one of the following condition satisfies.*list*2Â ANDÂ*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.