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

Question

This is an interview problem I came across yesterday, I can think of a recursive solution but I wanna know if there's a non-recursive solution.

Given a number N, starting with number 1, you can only multiply the result by 5 or add 3 to the result. If there's no way to get N through this 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 be obvious and intuitive, but are there any non-recursive methods?

Answer 1

I think the quickest, non recursive solution is (for N > 2):

• if N mod 3 == 1, it can be generated as 1 + 3*k.
• if N mod 3 == 2, it can be generated as 1*5 + 3*k
• if N mod 3 == 0, it cannot be generated

The last statement comes from the fact that starting with 1 (= 1 mod 3) you can only reach numbers which are equals to 1 or 2 mod 3:

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