minimum-one-bit-operations-to-make-integers-zero

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 an integer <code>n</code>, you must transform it into <code>0</code> using the following operations any number of times:

<ul>
	<li>Change the rightmost (<code>0th</code>) bit in the binary representation of <code>n</code>.</li>
	<li>Change the <code>ith</code> bit in the binary representation of <code>n</code> if the <code>(i-1)th</code> bit is set to <code>1</code> and the <code>(i-2)th</code> through <code>0th</code> bits are set to <code>0</code>.</li>
</ul>

Return the minimum number of operations to transform <code>n</code> into <code>0</code>.

&nbsp;
Example 1:

<pre>
Input: n = 3
Output: 2
Explanation: The binary representation of 3 is &quot;11&quot;.
&quot;11&quot; -&gt; &quot;01&quot; with the 2nd operation since the 0th bit is 1.
&quot;01&quot; -&gt; &quot;00&quot; with the 1st operation.
</pre>

Example 2:

<pre>
Input: n = 6
Output: 4
Explanation: The binary representation of 6 is &quot;110&quot;.
&quot;110&quot; -&gt; &quot;010&quot; with the 2nd operation since the 1st bit is 1 and 0th through 0th bits are 0.
&quot;010&quot; -&gt; &quot;011&quot; with the 1st operation.
&quot;011&quot; -&gt; &quot;001&quot; with the 2nd operation since the 0th bit is 1.
&quot;001&quot; -&gt; &quot;000&quot; with the 1st operation.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>0 &lt;= n &lt;= 109</code></li>
</ul>

第 209 场周赛

weekly-contest-209

minimumOneBitOperations

Minimum One Bit Operations to Make Integers Zero

Minimum Number of Operations to Make Array Continuous

minimum-number-of-operations-to-make-array-continuous

使数组连续的最少操作数

Apply Bitwise Operations to Make Strings Equal

apply-bitwise-operations-to-make-strings-equal

执行逐位运算使字符串相等

Bit Manipulation

Memoization

Dynamic Programming

给你一个整数 <code>n</code>，你需要重复执行多次下述操作将其转换为 <code>0</code> ：

<ul>
	<li>翻转 <code>n</code> 的二进制表示中最右侧位（第 <code>0</code> 位）。</li>
	<li>如果第 <code>(i-1)</code> 位为 <code>1</code> 且从第 <code>(i-2)</code> 位到第 <code>0</code> 位都为 <code>0</code>，则翻转 <code>n</code> 的二进制表示中的第 <code>i</code> 位。</li>
</ul>

返回将 <code>n</code> 转换为 <code>0</code> 的最小操作次数。

&nbsp;

示例 1：

<pre>
输入：n = 3
输出：2
解释：3 的二进制表示为 "11"
"11" -&gt; "01" ，执行的是第 2 种操作，因为第 0 位为 1 。
"01" -&gt; "00" ，执行的是第 1 种操作。
</pre>

示例 2：

<pre>
输入：n = 6
输出：4
解释：6 的二进制表示为 "110".
"110" -&gt; "010" ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。
"010" -&gt; "011" ，执行的是第 1 种操作。
"011" -&gt; "001" ，执行的是第 2 种操作，因为第 0 位为 1 。
"001" -&gt; "000" ，执行的是第 1 种操作。
</pre>

&nbsp;

提示：

<ul>
	<li><code>0 &lt;= n &lt;= 109</code></li>
</ul>