meiniak's blog

By meiniak, history, 13 months ago, In English

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 )

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Constraints?

»
13 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

Ignore

»
13 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why DP, can't you just go greedy?

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.