integer-replacement

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given a positive integer <code>n</code>,&nbsp;you can apply one of the following&nbsp;operations:

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

Return the minimum number of operations needed for <code>n</code> to become <code>1</code>.

&nbsp;
Example 1:

<pre>
Input: n = 8
Output: 3
Explanation: 8 -&gt; 4 -&gt; 2 -&gt; 1
</pre>

Example 2:

<pre>
Input: n = 7
Output: 4
Explanation: 7 -&gt; 8 -&gt; 4 -&gt; 2 -&gt; 1
or 7 -&gt; 6 -&gt; 3 -&gt; 2 -&gt; 1
</pre>

Example 3:

<pre>
Input: n = 4
Output: 2
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 231 - 1</code></li>
</ul>

integerReplacement

Integer Replacement

Greedy

Bit Manipulation

Memoization

Dynamic Programming

给定一个正整数&nbsp;<code>n</code> ，你可以做如下操作：

<ol>
	<li>如果&nbsp;<code>n</code>&nbsp;是偶数，则用&nbsp;<code>n / 2</code>替换&nbsp;<code>n</code> 。</li>
	<li>如果&nbsp;<code>n</code>&nbsp;是奇数，则可以用&nbsp;<code>n + 1</code>或<code>n - 1</code>替换&nbsp;<code>n</code> 。</li>
</ol>

返回 <code>n</code>&nbsp;变为 <code>1</code> 所需的 最小替换次数 。

&nbsp;

示例 1：

<pre>
输入：n = 8
输出：3
解释：8 -&gt; 4 -&gt; 2 -&gt; 1
</pre>

示例 2：

<pre>
输入：n = 7
输出：4
解释：7 -&gt; 8 -&gt; 4 -&gt; 2 -&gt; 1
或 7 -&gt; 6 -&gt; 3 -&gt; 2 -&gt; 1
</pre>

示例 3：

<pre>
输入：n = 4
输出：2
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n &lt;= 231 - 1</code></li>
</ul>