minimum-operations-to-reduce-an-integer-to-0

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a positive integer <code>n</code>, you can do the following operation any number of times:

<ul>
	<li>Add or subtract a power of <code>2</code> from <code>n</code>.</li>
</ul>

Return the minimum number of operations to make <code>n</code> equal to <code>0</code>.

A number <code>x</code> is power of <code>2</code> if <code>x == 2i</code>&nbsp;where <code>i &gt;= 0</code>.

&nbsp;
Example 1:

<pre>
Input: n = 39
Output: 3
Explanation: We can do the following operations:
- Add 20 = 1 to n, so now n = 40.
- Subtract 23 = 8 from n, so now n = 32.
- Subtract 25 = 32 from n, so now n = 0.
It can be shown that 3 is the minimum number of operations we need to make n equal to 0.
</pre>

Example 2:

<pre>
Input: n = 54
Output: 3
Explanation: We can do the following operations:
- Add 21 = 2 to n, so now n = 56.
- Add 23 = 8 to n, so now n = 64.
- Subtract 26 = 64 from n, so now n = 0.
So the minimum number of operations is 3.
</pre>

&nbsp;
Constraints:

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

minOperations

Minimum Operations to Reduce an Integer to 0

Plus One

plus-one

加一

Greedy

Bit Manipulation

Dynamic Programming

给你一个正整数 <code>n</code> ，你可以执行下述操作 任意 次：

<ul>
	<li><code>n</code> 加上或减去 <code>2</code> 的某个 幂</li>
</ul>

返回使 <code>n</code> 等于 <code>0</code> 需要执行的 最少 操作数。

如果 <code>x == 2i</code> 且其中 <code>i &gt;= 0</code> ，则数字 <code>x</code> 是 <code>2</code> 的幂。

&nbsp;

示例 1：

<pre>
输入：n = 39
输出：3
解释：我们可以执行下述操作：
- n 加上 20 = 1 ，得到 n = 40 。
- n 减去 23 = 8 ，得到 n = 32 。
- n 减去 25 = 32 ，得到 n = 0 。
可以证明使 n 等于 0 需要执行的最少操作数是 3 。
</pre>

示例 2：

<pre>
输入：n = 54
输出：3
解释：我们可以执行下述操作：
- n 加上 21 = 2 ，得到 n = 56 。
- n 加上 23 = 8 ，得到 n = 64 。
- n 减去 26 = 64 ，得到 n = 0 。
使 n 等于 0 需要执行的最少操作数是 3 。 
</pre>

&nbsp;

提示：

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