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.

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₁, a₂, . . . , a_k}, 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 = {a₁, a₂, . . . , a_k}.

Constraints

• 1 <= N <= 10⁹
• 1 <= K <= 20
• 2 <= a_i <= 20, where i ∈ [1, K]
• a_i != a_j, where 1 <= i, j <= K AND i != j

Note:

• Lexicographical order: If list1 = [p₁, p₂, . . . , p_m] and list2 = [q₁, q₂, . . . , q_n] are two ordered lists, then list1 is lexicographically smaller than list2 if any one of the following condition satisfies.
  • p_i = q_i, i ∈ [1, m] AND m < n.
  • p_i = q_i, i ∈ [1, k] AND k < min(m, n) AND 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.