minimum-elements-to-add-to-form-a-given-sum

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 an integer array <code>nums</code> and two integers <code>limit</code> and <code>goal</code>. The array <code>nums</code> has an interesting property that <code>abs(nums[i]) &lt;= limit</code>.

Return the minimum number of elements you need to add to make the sum of the array equal to <code>goal</code>. The array must maintain its property that <code>abs(nums[i]) &lt;= limit</code>.

Note that <code>abs(x)</code> equals <code>x</code> if <code>x &gt;= 0</code>, and <code>-x</code> otherwise.

&nbsp;
Example 1:

<pre>
Input: nums = [1,-1,1], limit = 3, goal = -4
Output: 2
Explanation: You can add -2 and -3, then the sum of the array will be 1 - 1 + 1 - 2 - 3 = -4.
</pre>

Example 2:

<pre>
Input: nums = [1,-10,9,1], limit = 100, goal = 0
Output: 1
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= limit &lt;= 106</code></li>
	<li><code>-limit &lt;= nums[i] &lt;= limit</code></li>
	<li><code>-109 &lt;= goal &lt;= 109</code></li>
</ul>

minElements

Minimum Elements to Add to Form a Given Sum

Greedy

Array

给你一个整数数组 <code>nums</code> ，和两个整数 <code>limit</code> 与 <code>goal</code> 。数组 <code>nums</code> 有一条重要属性：<code>abs(nums[i]) <= limit</code> 。

返回使数组元素总和等于 <code>goal</code> 所需要向数组中添加的 最少元素数量 ，添加元素 不应改变 数组中 <code>abs(nums[i]) <= limit</code> 这一属性。

注意，如果 <code>x >= 0</code> ，那么 <code>abs(x)</code> 等于 <code>x</code> ；否则，等于 <code>-x</code> 。

 

示例 1：

<pre>
输入：nums = [1,-1,1], limit = 3, goal = -4
输出：2
解释：可以将 -2 和 -3 添加到数组中，数组的元素总和变为 1 - 1 + 1 - 2 - 3 = -4 。
</pre>

示例 2：

<pre>
输入：nums = [1,-10,9,1], limit = 100, goal = 0
输出：1
</pre>

 

提示：

<ul>
	<li><code>1 <= nums.length <= 105</code></li>
	<li><code>1 <= limit <= 106</code></li>
	<li><code>-limit <= nums[i] <= limit</code></li>
	<li><code>-109 <= goal <= 109</code></li>
</ul>