integer-replacement

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

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

&#32473;&#23450;&#19968;&#20010;&#27491;&#25972;&#25968;&nbsp;<code>n</code> &#65292;&#20320;&#21487;&#20197;&#20570;&#22914;&#19979;&#25805;&#20316;&#65306;

<ol>
	<li>&#22914;&#26524;&nbsp;<code>n</code>&nbsp;&#26159;&#20598;&#25968;&#65292;&#21017;&#29992;&nbsp;<code>n / 2</code>&#26367;&#25442;&nbsp;<code>n</code> &#12290;</li>
	<li>&#22914;&#26524;&nbsp;<code>n</code>&nbsp;&#26159;&#22855;&#25968;&#65292;&#21017;&#21487;&#20197;&#29992;&nbsp;<code>n + 1</code>&#25110;<code>n - 1</code>&#26367;&#25442;&nbsp;<code>n</code> &#12290;</li>
</ol>

&#36820;&#22238; <code>n</code>&nbsp;&#21464;&#20026; <code>1</code> &#25152;&#38656;&#30340; &#26368;&#23567;&#26367;&#25442;&#27425;&#25968; &#12290;

&nbsp;

&#31034;&#20363; 1&#65306;

<pre>
&#36755;&#20837;&#65306;n = 8
&#36755;&#20986;&#65306;3
&#35299;&#37322;&#65306;8 -&gt; 4 -&gt; 2 -&gt; 1
</pre>

&#31034;&#20363; 2&#65306;

<pre>
&#36755;&#20837;&#65306;n = 7
&#36755;&#20986;&#65306;4
&#35299;&#37322;&#65306;7 -&gt; 8 -&gt; 4 -&gt; 2 -&gt; 1
&#25110; 7 -&gt; 6 -&gt; 3 -&gt; 2 -&gt; 1
</pre>

&#31034;&#20363; 3&#65306;

<pre>
&#36755;&#20837;&#65306;n = 4
&#36755;&#20986;&#65306;2
</pre>

&nbsp;

&#25552;&#31034;&#65306;

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

Sunbelt Computer Software

PL/B Language Development and Support