"""
<p>
Given a positive integer <i>n</i> and you can do operations as follow:
</p>

<p>
<ol>
<li>If <i>n</i> is even, replace <i>n</i> with <code><i>n</i>/2</code>.</li>
<li>If <i>n</i> is odd, you can replace <i>n</i> with either <code><i>n</i> + 1</code> or <code><i>n</i> - 1</code>.</li>
</ol>
</p>

<p>
What is the minimum number of replacements needed for <i>n</i> to become 1?
</p>

</p>

<p><b>Example 1:</b>
<pre>
<b>Input:</b>
8

<b>Output:</b>
3

<b>Explanation:</b>
8 -> 4 -> 2 -> 1
</pre>
</p>

<p><b>Example 2:</b>
<pre>
<b>Input:</b>
7

<b>Output:</b>
4

<b>Explanation:</b>
7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1
</pre>
</p><p>给定一个正整数&nbsp;<em>n</em>，你可以做如下操作：</p>

<p>1. 如果&nbsp;<em>n&nbsp;</em>是偶数，则用&nbsp;<code>n / 2</code>替换&nbsp;<em>n</em>。<br />
2. 如果&nbsp;<em>n&nbsp;</em>是奇数，则可以用&nbsp;<code>n + 1</code>或<code>n - 1</code>替换&nbsp;<em>n</em>。<br />
<em>n&nbsp;</em>变为 1 所需的最小替换次数是多少？</p>

<p><strong>示例 1:</strong></p>

<pre>
<strong>输入:</strong>
8

<strong>输出:</strong>
3

<strong>解释:</strong>
8 -&gt; 4 -&gt; 2 -&gt; 1
</pre>

<p><strong>示例 2:</strong></p>

<pre>
<strong>输入:</strong>
7

<strong>输出:</strong>
4

<strong>解释:</strong>
7 -&gt; 8 -&gt; 4 -&gt; 2 -&gt; 1
或
7 -&gt; 6 -&gt; 3 -&gt; 2 -&gt; 1
</pre>
<p>给定一个正整数&nbsp;<em>n</em>，你可以做如下操作：</p>

<p>1. 如果&nbsp;<em>n&nbsp;</em>是偶数，则用&nbsp;<code>n / 2</code>替换&nbsp;<em>n</em>。<br />
2. 如果&nbsp;<em>n&nbsp;</em>是奇数，则可以用&nbsp;<code>n + 1</code>或<code>n - 1</code>替换&nbsp;<em>n</em>。<br />
<em>n&nbsp;</em>变为 1 所需的最小替换次数是多少？</p>

<p><strong>示例 1:</strong></p>

<pre>
<strong>输入:</strong>
8

<strong>输出:</strong>
3

<strong>解释:</strong>
8 -&gt; 4 -&gt; 2 -&gt; 1
</pre>

<p><strong>示例 2:</strong></p>

<pre>
<strong>输入:</strong>
7

<strong>输出:</strong>
4

<strong>解释:</strong>
7 -&gt; 8 -&gt; 4 -&gt; 2 -&gt; 1
或
7 -&gt; 6 -&gt; 3 -&gt; 2 -&gt; 1
</pre>
"""


class Solution(object):
    def integerReplacement(self, n):
        """
        :type n: int
        :rtype: int
        """
        