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.
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 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
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Reverse Factorization
You are viewing a single comment's thread. Return to all 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.
f
of the sorted input, check to see if it divides our target numberf
onto a stack of factors, and push f back onto the front of out sorted list. set the new target number toold_target / f
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