[Solved]: Efficient algorithm for getting from 1 to n with 3 specific operations

Problem Detail: 

The question:

Given those 3 valid operations over numbers and an integer $n$:

• add $1$ to the number
• multiply the number by $2$
• multiply the number by $3$

describe an efficient algorithm for the minimal number of operations of getting from $1$ to $n$ with the 3 operations mentioned above.

For example for $n=28$ the answer is $4$ : $1\times 3\times 3\times 3+1=27+1=28$.

My approach:

I noticed that there is a recursive algorithm that will provide the answer but even when I used memoization the algorithm took a lot of time to end with $n\geq 1000$. I thought of a way to start with $n$ instead and try to reduce it to $1$ with the inverse operations of subtracting $1$ dividing by $2$ or by $3$ and trying to get it to be devisible by $3$ or by $2$ by subtracting $1$'s and checking the mod. But my second approach had some (more than some) mistakes where It stated that the smallest number of operations is more than it is. Please help or give a hint I clearly missing some kay fact about the nature of such operations.

Edit:

def ToN(n):

d=dict() def to(x,num,di):     if (num==x):         return 0     elif (num>x):         return num     elif num in di:         return di[num]     else:         if num+1 not in di:             di[num+1]=to(x,num+1,di)         if num*2 not in di:             di[num*2]=to(x,num*2,di)         if num*3 not in di:             di[num*3]=to(x,num*3,di)         di[num]=min(di[num+1],di[num*2],di[num*3])+1         return di[num] return to(n,1,d) 

I wrote the code above in python and it takes a lot of time to end for num=1000. Can you help me understand what is wrong w.r.t. efficiency.

Asked By : Lior

Answered By : David Richerby

Find the shortest path from $1$ to $n$ on an appropriate graph on vertices $\{1, \dots, n\}$. This approach will work whenever it's guaranteed that intermediate values in the calculations will lie within some bounded range.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/59429

3.2K people like this

 Download Related Notes/Documents