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

1
2
3

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

1
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
  • -109 <= 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

1
2
3
4
5
6
7
8
9

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;
    }
};
1
2
3
4
5
6
7
8
9

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
}
1
2
3
4
5
6
7
8

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);
    }
}
1
2
3
4
5
6
7
8

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()
    }
}
1
2
3
4

def min_elements(nums: list[int], limit: int, goal: int) -> int:
    s = sum(nums)
    diff = abs(goal - s)
    return (diff + limit - 1) // limit
1
2
3
4
5
6
7

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
    }
}
1
2
3
4
5
6
7

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.