### meiniak's blog

By meiniak, history, 13 months ago,

Given a set of integers A = { a1,a2,a3,...an } and an integer N. You need to find a way to reach N, starting from 1 and at each step multiplying current value by any element of A. Repetition of element is allowed. Since there may be many solutions having the minimum number of states to reach N you can print the lexicographically smallest series among the solutions which contains the least number of states.

For eg: N = 12 , A = [ 2,3,4 ]

a) 1 — > 2 — > 2 — > 3

b) 1 — > 4 -> 3

c) 1 — > 3 -> 4 ( This is the best solution )

• 0

 » 13 months ago, # |   0 Constraints?
 » 13 months ago, # | ← Rev. 5 →   0 Ignore
 » 13 months ago, # | ← Rev. 2 →   0 You can solve this using DP. In each state you either choose or not choose the element at the current position. And continue doing so until your value equals N (base case), if it becomes greater than N, then simply return. Whenever you chose an element, add this element to your checker string, if the products equates N in the base case, you check if the string formed is lexicographically smallest.
•  » » 13 months ago, # ^ |   0 Why DP, can't you just go greedy?
•  » » » 13 months ago, # ^ |   0 Since repetition of elements are also allowed in this case, I don't think greedy approach will work efficiently. If it was not allowed, it would be good. Correct me if I am wrong.