Minimum Operations to Zero

Given a non-negative integer \(n\), determine the minimum number of operations required to reduce it to zero.

You are allowed to subtract either 1, 2, or 3 from \(n\) in each operation. Formally, let \(dp[i]\) represent the minimum number of operations needed to reduce \(i\) to 0. Then, the recurrence relation is given by:

\(dp[i] = \min(dp[i-1],\; dp[i-2],\; dp[i-3]) + 1\)

Your task is to compute \(dp[n]\).

inputFormat

The input consists of a single integer \(n\) (where \(0 \leq n \leq 10^5\)). It is read from standard input (stdin).

outputFormat

The output should be a single integer representing the minimum number of operations required to reduce \(n\) to zero. Output the result to standard output (stdout).

0

0