# Reverse Factorization

# Reverse Factorization

glionnet + 1 comment Since with the actual test case, this challenge is quite easy, would it possible to downgrade the difficulty of this challenge and add a new challenge that would be the same, but with more advanced test-cases as the one mentioned here ?

RossStory + 1 comment Or, better yet, simply update the test cases to include things like:

24 3

4 6 8

glionnet + 0 comments just adding test case will generate an issue that some people have validate the challenge but haven't really solved the new test-case. Write the same challenge but with this tricky test-case will permit to have a sort of "two-steps" challenge, if we do so, people that have already solve the full challenge will be able to solve the two challenge, and people that have only solved the easy start will have a new challenge to do ! :)

jm3chevarria + 0 comments I meant to submit my solutions until I found there is no C++ option in the languages combo box. Is there a way to submit a C++ coded solution?

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) }

angad_iitd + 0 comments Nevermind. I just needed to filter out cases that I had already seen before.

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 visited: scala.collection.mutable.Set[Long] = scala.collection.mutable.Set() val sol = broaden[(List[Int], Long)](Stream((Nil, n)), currTarget => s.filter(ai => (currTarget._2 % ai) == 0) .filter(ai => !visited.contains(currTarget._2 / ai)) .map(ai => { visited.add(currTarget._2 / 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) }

maruks + 2 comments Why is this challenge under "Memoization And Dynamic Programming"? Most solutions don't use either of those techniques.

abhiranjanChallenge Author + 0 comments Maybe because author's solution uses this :)

quick_dudley + 0 comments I used dynamic programming: almost the same algorithm as I used in "Dice Path"

modenl + 1 comment I found some solutions got 50 points but actually failed to handle a case like:

`16 2 4 8`

abhiranjanChallenge Author + 0 comments Yes @modenl, I missed this test case while designing test cases.

andrevm + 4 comments I don't think a graph search is completely necessary to find a solution to this problem. I solved it in what I believe is a simpler way. Do not continue reading if you do not want to see my solution.

- Sort the input descending
- For each element
`f`

of the sorted input, check to see if it divides our target number- if it does, push
`f`

onto a stack of factors, and push f back onto the front of out sorted list. set the new target number to`old_target / f`

- if it does not, then move on to the next element

- if it does, push
- If at the end our target number is > 1, then we have not completely factored the original target, so output -1
- Otherwise, perform a prefix multiply/scan of the factor stack to generate a list of numbers to output

This solution is O(n log n) to sort the input. If already sorted, it's O(n + k) where k is the number of factors found

abhiranjanChallenge Author + 0 comments Great. Please check this.

andrevm + 0 comments Very cool, thanks!

yaray + 0 comments The greedy approach does not work on this test case:

`36 3 18 9 4`

abhiranjanChallenge Author + 1 comment Hi @yaray, thanks for pointing that out. It seems I have missed this case while designing test cases. I am removing above part of from editorial section.

jsc + 0 comments Actually, a similar solution works fine, without any need for DP, memoization, or graph search. Filter array for actual factors of n, reverse sort. Then try them one by one, rejecting any that don't lead to a solution:

def factors(a: List[Int], n: Int): List[Int] = { a match { case Nil => Nil case d :: t if n == d => List(n) case d :: t if n % d == 0 => val sol = factors(a, n / d) if (sol.isEmpty) factors(t, n) else d :: sol case d :: t => factors(t, n) } }

Then format the result to give the desired answer. The first valid solution found will be the shortest lexicographically due to the reverse sort.

No more comments

Sort 6 Discussions, By:

Please Login in order to post a comment