number-of-steps-to-reduce-a-number-in-binary-representation-to-one

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 the binary representation of an integer as a string <code>s</code>, return the number of steps to reduce it to <code>1</code> under the following rules:

<ul>
	<li>
	If the current number is even, you have to divide it by <code>2</code>.
	</li>
	<li>
	If the current number is odd, you have to add <code>1</code> to it.
	</li>
</ul>

It is guaranteed that you can always reach one for all test cases.

&nbsp;
Example 1:

<pre>
Input: s = &quot;1101&quot;
Output: 6
Explanation: &quot;1101&quot; corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14.&nbsp;
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.&nbsp; 
Step 5) 4 is even, divide by 2 and obtain 2.&nbsp;
Step 6) 2 is even, divide by 2 and obtain 1.&nbsp; 
</pre>

Example 2:

<pre>
Input: s = &quot;10&quot;
Output: 1
Explanation: &quot;10&quot; corresponds to number 2 in their decimal representation.
Step 1) 2 is even, divide by 2 and obtain 1.&nbsp; 
</pre>

Example 3:

<pre>
Input: s = &quot;1&quot;
Output: 0
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= s.length&nbsp;&lt;= 500</code></li>
	<li><code>s</code> consists of characters &#39;0&#39; or &#39;1&#39;</li>
	<li><code>s[0] == &#39;1&#39;</code></li>
</ul>

numSteps

Number of Steps to Reduce a Number in Binary Representation to One

Minimum Moves to Reach Target Score

minimum-moves-to-reach-target-score

得到目标值的最少行动次数

Bit Manipulation

String

给你一个以二进制形式表示的数字 <code>s</code> 。请你返回按下述规则将其减少到 1 所需要的步骤数：

<ul>
	<li>
	如果当前数字为偶数，则将其除以 <code>2</code> 。
	</li>
	<li>
	如果当前数字为奇数，则将其加上 <code>1</code> 。
	</li>
</ul>

题目保证你总是可以按上述规则将测试用例变为 1 。

&nbsp;

示例 1：

<pre>
输入：s = "1101"
输出：6
解释："1101" 表示十进制数 13 。
Step 1) 13 是奇数，加 1 得到 14&nbsp;
Step 2) 14 是偶数，除 2 得到 7
Step 3) 7 是奇数，加 1 得到 8
Step 4) 8 是偶数，除 2 得到 4&nbsp; 
Step 5) 4 是偶数，除 2 得到 2&nbsp;
Step 6) 2 是偶数，除 2 得到 1&nbsp; 
</pre>

示例 2：

<pre>
输入：s = "10"
输出：1
解释："10" 表示十进制数 2 。
Step 1) 2 是偶数，除 2 得到 1 
</pre>

示例 3：

<pre>
输入：s = "1"
输出：0
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= s.length&nbsp;&lt;= 500</code></li>
	<li><code>s</code> 由字符 <code>'0'</code> 或 <code>'1'</code> 组成。</li>
	<li><code>s[0] == '1'</code></li>
</ul>