Minimum Operations to Reduce a Number to 1

Given a positive integer \(N\), your task is to compute the minimum number of operations needed to reduce \(N\) to 1. In each operation, you are allowed to do one of the following:

• If \(N\) is divisible by 2, you may divide \(N\) by 2.
• If \(N\) is divisible by 3, you may divide \(N\) by 3.
• You may subtract 1 from \(N\).

The challenge is to find the minimum number of operations required to arrive at 1.

Examples:

• For \(N = 10\), the answer is 3.
• For \(N = 7\), the answer is 3.
• For \(N = 100\), the answer is 7.

inputFormat

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

outputFormat

Output a single integer representing the minimum number of operations required to reduce \(N\) to 1 on standard output.

10

3