How to get the target number with +3 or *5 operations without recursion?
algorithm, recursion
Solution
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
Problem
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?