We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Functional Programming
  3. Memoization and DP
  4. Reverse Factorization
  5. Discussions

Reverse Factorization

  • angad_iitd
     + 1 comment

    Hi, I'm trying to use BFS to solve this, but I'm getting timeouts for test case 11 onwards. Can someone please help me make my solution more efficient? (I'm coding in Scala)

    def main(args: Array[String]) {
    val sc = new java.util.Scanner(System.in)
    val n = sc.nextLong()
    val k = sc.nextInt()
    val a: Array[Int] = Array.ofDim(k)
    for (i <- 0 until k) {
      a(i) = sc.nextInt()
    }
    val s = a.toStream.sorted

    val sol = broaden[(List[Int], Long)](Stream((Nil, n)),
                                         currTarget => s.filter(ai => (currTarget._2 % ai) == 0)
                                                       .map(ai => (ai :: currTarget._1, currTarget._2 / ai)))
              .find(_._2 == 1)
              .map(_._1.reverse)

    if (sol.isEmpty) print("-1")
    else printStates(sol.get, 1)
  }

  def printStates(l: List[Int], current: Long): Unit = l match {
    case Nil => print(current + " ")
    case x :: xs =>
      print(current + " ")
      printStates(xs, current * x)
  }

  def broaden[T](s: Stream[T], f: T => Stream[T]): Stream[T] = {
    if (s.isEmpty) s
    else s.head #:: broaden(s.tail append f(s.head), f)
  }