No.2241 Reach 1
Problem Statement
You are given an integer $N$ greater than or equal to $2$. There is a variable $m$, initially $m=N$.
In $1$ operation, you can perform one of the following on this variable.
- Choose a non-negative integer $k$ such that $m/2^k$ is an integer, and replace $m$ with $m/2^k$.
- Choose a positive integer $k$, and replace $m$ with $mk+1$.
Your goal is to get from the state $m=N$ to $m=1$ with as few operations as possible. Find the minimum number of operations required to achieve the goal.
Constraints
- $2 \le N \le 10^9$
Input
$N$
Output
Output the minimum number of operations required to get from $m=N$ to $m=1$.
Under these constraints, it is guaranteed that the goal can always be achieved and that the answer is at most $2^{31}-1$.
Sample
Sample 1
Input
4
Output
1
Initially, $m=4$.
Choosing $k=2$ in operation 1. gives $m=4/2^2=1$.
It is impossible to use fewer than $1$ operation, so the answer is $1$.
Sample 2
Input
3
Output
2
Initially, $m=3$.
First, choosing $k=1$ in operation 2. gives $m=3\times 1+1 = 4$.
Next, choosing $k=2$ in operation 1. gives $m=4/2^2=1$.
It is impossible to reach $m=1$ in fewer than $2$ operations, so the answer is $2$.
Sample 3
Input
6
Output
3
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2
Nachia