What is the main idea in Minimum Elements to Add to Form a Given Sum?

Compute the current array sum, find the absolute gap to goal, and divide that gap by limit with ceiling division. The greedy step is valid because each added element can fix at most limit, so using smaller magnitudes cannot reduce the number of additions.

Why does the greedy choice work in this problem?

The invariant is that after adding k elements, the most total correction you can make is k * limit in absolute value. That means any solution needs at least ceil(diff / limit) elements, and that bound is reachable by taking values in the needed direction with magnitude limit except possibly the last one.

Do I need to construct the elements I add?

No. The problem only asks for the minimum count. Once you know the remaining difference, the exact values are only a witness that the count is achievable, not something you need to enumerate in code.

What is the most common bug for this greedy choice plus invariant validation pattern?

The usual mistake is using integer division without rounding up. If diff is 5 and limit is 3, floor division gives 1, but one element can correct at most 3, so you actually need 2.

Why is this tagged Array and Greedy instead of math only?

You still need one pass over the array to compute the starting sum, and the interview-worthy part is recognizing the greedy trade-off created by the per-element limit. The math formula comes directly from that Array scan plus the greedy bound.

#1785

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

构成特定和需要添加的最少元素

给你一个整数数组 nums ，和两个整数 limit 与 goal 。数组 nums 有一条重要属性： abs(nums[i]) 。返回使数组元素总和等于 goal 所需要向数组中添加的最少元素数量，添加元素不应改变数组中 abs(nums[i]) 这一属性。注意，如果 x >= 0 ，…

数组贪心

题目描述

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

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

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

示例 1：

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

示例 2：

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

提示：

1 <= nums.length <= 10⁵
1 <= limit <= 10⁶
-limit <= nums[i] <= limit
-10⁹ <= goal <= 10⁹

lightbulb

解题思路

方法一：贪心

我们先计算数组元素总和 $s$ ，然后计算 $s$ 与 $goal$ 的差值 $d$ 。

那么需要添加的元素数量为 $d$ 的绝对值除以 $limit$ 向上取整，即 $\lceil \frac{|d|}{limit} \rceil$ 。

注意，本题中数组元素的数据范围为 $[-10^6, 10^6]$ ，元素个数最大为 $10^5$ ，总和 $s$ 以及差值 $d$ 可能会超过 $32$ 位整数的表示范围，因此需要使用 $64$ 位整数。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

class Solution:
    def minElements(self, nums: List[int], limit: int, goal: int) -> int:
        d = abs(sum(nums) - goal)
        return (d + limit - 1) // limit

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The interviewer keeps pointing back to the target sum instead of asking which exact numbers you would add.
question_mark
They ask what changes if you imagine nums starts empty, which hints that only the remaining gap matters.
question_mark
They focus on the bound abs(x) <= limit, signaling a greedy maximum-contribution argument rather than subset reasoning.

warning

常见陷阱

外企场景

error
Trying to build the added numbers one by one instead of directly dividing the remaining gap by limit.
error
Forgetting the absolute value on goal - sum(nums), which breaks cases where the array sum is already above the target.
error
Using floor division instead of ceiling division, which undercounts whenever the gap is not a multiple of limit.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Ask for the actual values to append, not just the minimum count; the same greedy idea works by filling with +/-limit and one remainder.
arrow_right_alt
Change the bound so each added element comes from a custom allowed set; then the simple ceiling formula may fail and the greedy proof must be revisited.
arrow_right_alt
Ask whether exactly k additions can reach goal; this becomes a feasibility check using whether k * limit can cover the remaining gap.

help

常见问题

外企场景

继续练习

#1792 最大平均通过率 #1775 通过最少操作次数使数组的和相等 #1798 你能构造出连续值的最大数目