minimum-moves-to-reach-target-score

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 playing a game with integers. You start with the integer <code>1</code> and you want to reach the integer <code>target</code>.

In one move, you can either:

<ul>
	<li>Increment the current integer by one (i.e., <code>x = x + 1</code>).</li>
	<li>Double the current integer (i.e., <code>x = 2 * x</code>).</li>
</ul>

You can use the increment operation any number of times, however, you can only use the double operation at most <code>maxDoubles</code> times.

Given the two integers <code>target</code> and <code>maxDoubles</code>, return the minimum number of moves needed to reach <code>target</code> starting with <code>1</code>.

&nbsp;
Example 1:

<pre>
Input: target = 5, maxDoubles = 0
Output: 4
Explanation: Keep incrementing by 1 until you reach target.
</pre>

Example 2:

<pre>
Input: target = 19, maxDoubles = 2
Output: 7
Explanation: Initially, x = 1
Increment 3 times so x = 4
Double once so x = 8
Increment once so x = 9
Double again so x = 18
Increment once so x = 19
</pre>

Example 3:

<pre>
Input: target = 10, maxDoubles = 4
Output: 4
Explanation: Initially, x = 1
Increment once so x = 2
Double once so x = 4
Increment once so x = 5
Double again so x = 10
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= target &lt;= 109</code></li>
	<li><code>0 &lt;= maxDoubles &lt;= 100</code></li>
</ul>

minMoves

Minimum Moves to Reach Target Score

Number of Steps to Reduce a Number to Zero

number-of-steps-to-reduce-a-number-to-zero

将数字变成 0 的操作次数

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

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

将二进制表示减到 1 的步骤数

Greedy

Math

你正在玩一个整数游戏。从整数 <code>1</code> 开始，期望得到整数 <code>target</code> 。

在一次行动中，你可以做下述两种操作之一：

<ul>
	<li>递增，将当前整数的值加 1（即， <code>x = x + 1</code>）。</li>
	<li>加倍，使当前整数的值翻倍（即，<code>x = 2 * x</code>）。</li>
</ul>

在整个游戏过程中，你可以使用 递增 操作 任意 次数。但是只能使用 加倍 操作 至多 <code>maxDoubles</code> 次。

给你两个整数 <code>target</code> 和 <code>maxDoubles</code> ，返回从 1 开始得到 <code>target</code> 需要的最少行动次数。

&nbsp;

示例 1：

<pre>输入：target = 5, maxDoubles = 0
输出：4
解释：一直递增 1 直到得到 target 。
</pre>

示例 2：

<pre>输入：target = 19, maxDoubles = 2
输出：7
解释：最初，x = 1 。
递增 3 次，x = 4 。
加倍 1 次，x = 8 。
递增 1 次，x = 9 。
加倍 1 次，x = 18 。
递增 1 次，x = 19 。
</pre>

示例 3：

<pre>输入：target = 10, maxDoubles = 4
输出：4
解释：
最初，x = 1 。 
递增 1 次，x = 2 。 
加倍 1 次，x = 4 。 
递增 1 次，x = 5 。 
加倍 1 次，x = 10 。 
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= target &lt;= 109</code></li>
	<li><code>0 &lt;= maxDoubles &lt;= 100</code></li>
</ul>