Formatted question description: https://leetcode.ca/all/1785.html
1785. Minimum Elements to Add to Form a Given Sum
Level
Medium
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 <= 10^51 <= limit <= 10^6-limit <= nums[i] <= limit-10^9 <= goal <= 10^9
Solution
First, calculate sum as the sum of all elements in nums. Next, calculate the absolute difference between goal and sum, and calculate the minimum number of elements to add using a greedy approach, which means consider adding limit or -limit as many as possible and adding one more element if the remaining absolute difference is less than limit.
class Solution {
public int minElements(int[] nums, int limit, int goal) {
long sum = 0;
for (int num : nums)
sum += (long) num;
long difference = (long) goal - sum;
if (difference == 0)
return 0;
else {
difference = Math.abs(difference);
long minAdd = difference / limit;
if (difference % limit != 0)
minAdd++;
return (int) minAdd;
}
}
}