Skip to content

1785. Minimum Elements to Add to Form a Given Sum

Description

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 to goal. The array must maintain its property that abs(nums[i]) <= limit.

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

 

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 <= 105
  • 1 <= limit <= 106
  • -limit <= nums[i] <= limit
  • -109 <= goal <= 109

Solutions

Solution 1: Greedy

First, we calculate the sum of the array elements \(s\), and then calculate the difference \(d\) between \(s\) and \(goal\).

The number of elements to be added is the absolute value of \(d\) divided by \(limit\) and rounded up, that is, \(\lceil \frac{|d|}{limit} \rceil\).

Note that in this problem, the data range of array elements is \([-10^6, 10^6]\), the maximum number of elements is \(10^5\), the total sum \(s\) and the difference \(d\) may exceed the range of 32-bit integers, so we need to use 64-bit integers.

The time complexity is \(O(n)\), and the space complexity is \(O(1)\). Here, \(n\) is the length of the array \(nums\).

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int minElements(int[] nums, int limit, int goal) {
        // long s = Arrays.stream(nums).asLongStream().sum();
        long s = 0;
        for (int v : nums) {
            s += v;
        }
        long d = Math.abs(s - goal);
        return (int) ((d + limit - 1) / limit);
    }
}

1
2
3
4
5
6
7
8
class Solution {
public:
    int minElements(vector<int>& nums, int limit, int goal) {
        long long s = accumulate(nums.begin(), nums.end(), 0ll);
        long long d = abs(s - goal);
        return (d + limit - 1) / limit;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func minElements(nums []int, limit int, goal int) int {
    s := 0
    for _, v := range nums {
        s += v
    }
    d := abs(s - goal)
    return (d + limit - 1) / limit
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

1
2
3
4
5
function minElements(nums: number[], limit: number, goal: number): number {
    const sum = nums.reduce((r, v) => r + v, 0);
    const diff = Math.abs(goal - sum);
    return Math.floor((diff + limit - 1) / limit);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
impl Solution {
    pub fn min_elements(nums: Vec<i32>, limit: i32, goal: i32) -> i32 {
        let limit = limit as i64;
        let goal = goal as i64;
        let mut sum = 0;
        for &num in nums.iter() {
            sum += num as i64;
        }
        let diff = (goal - sum).abs();
        ((diff + limit - 1) / limit) as i32
    }
}

1
2
3
4
5
6
7
8
int minElements(int* nums, int numsSize, int limit, int goal) {
    long long sum = 0;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
    }
    long long diff = labs(goal - sum);
    return (diff + limit - 1) / limit;
}

Comments