# Solution: Primitive Calculator

Solve the Primitive Calculator Problem.

We'll cover the following

## Solution

Let $calculator(n)$ be the minimum number of operations needed to get $n$ from $1$. Since the last operation in an optimum sequence of operations is “$+1$,” “$×2$,” or “$×3$,” we get the following recurrence relation, for $n ≥ 1$:

$calculator(n) = 1 + min \begin{cases} calculator(n-1) \\ calculator(n/2) & \text{if }~~ n~~ \text{is divisible by}~~ 2, \\ calculator(n/3) & \text{if }~~ n~~ \text{is divisible by}~~ 3. \end{cases}$

This recurrence relation, together with the base case $calculator(1) = 1$, can be mechanically converted into a recursive and then an iterative algorithm.

$Calculator(n)$:
$table[1..n] ← [+∞, . . . , +∞]$
$table[1] ← 0$
for $k$ from $2$ to $n$:
$table[k] = 1 + table[k − 1]$
if $n$ is divisible by $2$:
$table[k]=min(table[k],1+table[k/2])$
if $n$ is divisible by $3$:
$table[k]=min(table[k],1+table[k/3])$
return $table[n]$

Recall, however, that besides the optimum value, we are asked to output an optimum sequence of operations. To do this, notice that we can find the last operation as follows:

• it is “$+1$,” if $calculator(n)=1+calculator(n−1)$;
• it is “$×2$,” if $n$ is divisible by $2$ and $calculator(n) = 1 + calculator(n/ 2)$;
• it is “$×3$,” if $n$ is divisible by $3$ and $calculator(n) = 1 + calculator(n/ 3)$.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.