Given a number N (1<= N <= 10^9) Find minimum number of operations to reduce N to 1. The allowed operations being
- Division by 2
- Division by 3
- Subtracting 1
All intermediate values of N should also be integers. I have tried dynamic programming approach, but it consumes more than 3 seconds. Can anyone suggest a fast algorithm for this problem ?