Minimum Steps to One

Given an integer \(N\), your task is to compute the minimum number of operations required to reduce \(N\) to 1. In each step, you can perform one of the following operations:

• Subtract 1: \(N \leftarrow N - 1\)
• If \(N\) is divisible by 2: \(N \leftarrow \frac{N}{2}\)
• If \(N\) is divisible by 3: \(N \leftarrow \frac{N}{3}\)

The recurrence relation for the dynamic programming solution is given by:

\(dp[i] = \min\bigl(dp[i-1] + 1,\; dp[i/2] + 1 \text{ (if } 2\mid i\text{)},\; dp[i/3] + 1 \text{ (if } 3\mid i\text{)}\bigr)\)

You need to implement an efficient algorithm that computes \(dp[N]\) for a given \(N\).

inputFormat

The input consists of a single integer \(N\) \( (1 \leq N \leq 10^6) \) provided via standard input (stdin).

outputFormat

Output a single integer, the minimum number of operations required to reduce \(N\) to 1. The result should be printed to standard output (stdout).

1

0