algorithm - How to get the target number with +3 or *5 operations without recursion? -

this interview problem came across yesterday, can think of recursive solution wanna know if there's non-recursive solution.

given number n, starting number 1, can multiply result 5 or add 3 result. if there's no way n through method, return "can't generate it".

ex:

input: 23 output: (1+3)*5+3 input: 215 output: ((1*5+3)*5+3)*5 input: 12 output: can't generate it. 

the recursive method can obvious , intuitive, there non-recursive methods?

i think quickest, non recursive solution (for n > 2):

• if n mod 3 == 1, can generated 1 + 3*k.
• if n mod 3 == 2, can generated 1*5 + 3*k
• if n mod 3 == 0, cannot generated

the last statement comes fact starting 1 (= 1 mod 3) can reach numbers equals 1 or 2 mod 3:

• when add 3, don't change value mod 3
• a number equals 1 mod 3 multiplied 5 gives number equals 2 mod 3
• a number equals 2 mod 3 multiplied 5 gives number equals 1 mod 3