problemmediumalgorithmsleetcode-1785leetcode 1785leetcode1785

Minimum Elements to Add to Form a Given Sum

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

You are given an integer array nums and two integers limit and goal. The array nums has an interesting property that abs(nums[i]) <= limit.

Return the minimum number of elements you need to add to make the sum of the array equal togoal. The array must maintain its property that abs(nums[i]) <= limit.

Note that abs(x) equals x if x >= 0, and -x otherwise.

Examples

Example 1

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.

Example 2

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

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= limit <= 10^6
  • -limit <= nums[i] <= limit
  • -10^9 <= goal <= 10^9

Solution

Method 1 – Greedy Absolute Difference

Intuition

To reach the goal sum, we can add elements with the maximum allowed absolute value (limit) in the direction needed (positive or negative). The minimum number of elements is the ceiling of the absolute difference between the current sum and the goal divided by limit.

Approach

  1. Calculate the current sum of the array.
  2. Compute the absolute difference between the current sum and the goal.
  3. Divide the difference by limit and round up to get the minimum number of elements needed.
  4. Return the result.

Code

C++
class Solution {
public:
    int minElements(vector<int>& nums, int limit, int goal) {
        long long s = 0;
        for (int x : nums) s += x;
        long long diff = abs(goal - s);
        return (diff + limit - 1) / limit;
    }
};
Go
func minElements(nums []int, limit int, goal int) int {
    s := 0
    for _, x := range nums {
        s += x
    }
    diff := goal - s
    if diff < 0 { diff = -diff }
    return (diff + limit - 1) / limit
}
Java
class Solution {
    public int minElements(int[] nums, int limit, int goal) {
        long s = 0;
        for (int x : nums) s += x;
        long diff = Math.abs(goal - s);
        return (int)((diff + limit - 1) / limit);
    }
}
Kotlin
class Solution {
    fun minElements(nums: IntArray, limit: Int, goal: Int): Int {
        var s = 0L
        for (x in nums) s += x
        val diff = kotlin.math.abs(goal - s)
        return ((diff + limit - 1) / limit).toInt()
    }
}
Python
def min_elements(nums: list[int], limit: int, goal: int) -> int:
    s = sum(nums)
    diff = abs(goal - s)
    return (diff + limit - 1) // limit
Rust
impl Solution {
    pub fn min_elements(nums: Vec<i32>, limit: i32, goal: i32) -> i32 {
        let s: i64 = nums.iter().map(|&x| x as i64).sum();
        let diff = (goal as i64 - s).abs();
        ((diff + limit as i64 - 1) / limit as i64) as i32
    }
}
TypeScript
class Solution {
    minElements(nums: number[], limit: number, goal: number): number {
        let s = nums.reduce((a, b) => a + b, 0);
        let diff = Math.abs(goal - s);
        return Math.floor((diff + limit - 1) / limit);
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. We sum the array once.
  • 🧺 Space complexity: O(1), only a few variables are used for tracking the answer.

Comments