apply-operations-to-make-sum-of-array-greater-than-or-equal-to-k

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>k</code>. Initially, you have an array <code>nums = [1]</code>.

You can perform any of the following operations on the array any number of times (possibly zero):

<ul>
	<li>Choose any element in the array and increase its value by <code>1</code>.</li>
	<li>Duplicate any element in the array and add it to the end of the array.</li>
</ul>

Return the minimum number of operations required to make the sum of elements of the final array greater than or equal to <code>k</code>.

&nbsp;
Example 1:

<div class="example-block">
Input: k = 11

Output: 5

Explanation:

We can do the following operations on the array <code>nums = [1]</code>:

<ul>
	<li>Increase the element by <code>1</code> three times. The resulting array is <code>nums = [4]</code>.</li>
	<li>Duplicate the element two times. The resulting array is <code>nums = [4,4,4]</code>.</li>
</ul>

The sum of the final array is <code>4 + 4 + 4 = 12</code> which is greater than or equal to <code>k = 11</code>. 
The total number of operations performed is <code>3 + 2 = 5</code>.
</div>

Example 2:

<div class="example-block">
Input: k = 1

Output: 0

Explanation:

The sum of the original array is already greater than or equal to <code>1</code>, so no operations are needed.
</div>

&nbsp;
Constraints:

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

minOperations

Apply Operations to Make Sum of Array Greater Than or Equal to k

Greedy

Math

Enumeration

给你一个正整数 <code>k</code> 。最初，你有一个数组 <code>nums = [1]</code> 。

你可以对数组执行以下 任意 操作 任意 次数（可能为零）：

<ul>
	<li>选择数组中的任何一个元素，然后将它的值 增加 <code>1</code> 。</li>
	<li>复制数组中的任何一个元素，然后将它附加到数组的末尾。</li>
</ul>

返回使得最终数组元素之 和 大于或等于 <code>k</code> 所需的 最少 操作次数。

&nbsp;

示例 1：

<div class="example-block">
输入：k = 11

输出：5

解释：

可以对数组 <code>nums = [1]</code> 执行以下操作：

<ul>
	<li>将元素的值增加 <code>1</code> 三次。结果数组为 <code>nums = [4]</code> 。</li>
	<li>复制元素两次。结果数组为 <code>nums = [4,4,4]</code> 。</li>
</ul>

最终数组的和为 <code>4 + 4 + 4 = 12</code> ，大于等于 <code>k = 11</code> 。 
执行的总操作次数为 <code>3 + 2 = 5</code> 。
</div>

示例 2：

<div class="example-block">
输入：k = 1

输出：0

解释：

原始数组的和已经大于等于 <code>1</code> ，因此不需要执行操作。
</div>

&nbsp;

提示：

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