1785. Minimum Elements to Add to Form a Given Sum
SourceWeekly Contest 231 Q2DifficultyMediumRating1432
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 <= 1051 <= limit <= 106-limit <= nums[i] <= limit-109 <= goal <= 109
Solutions
Solution 1: Greedy
Thinking
We may append integers of absolute value at most \(\textit{limit}\) so the sum becomes \(\textit{goal}\), using as few appends as possible.
The gap \(d=|\sum \textit{nums}-\textit{goal}|\) shrinks by at most \(\textit{limit}\) each time, so the fewest appends are \(\lceil d/\textit{limit}\rceil\).
First, we calculate the sum of the array elements \(s\), and then calculate the difference \(d\) between \(s\) and \(\textit{goal}\).
The number of elements to be added is the absolute value of \(d\) divided by \(\textit{limit}\) and rounded up, that is, \(\lceil \frac{|d|}{\textit{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)\), where \(n\) is the length of the array \(\textit{nums}\).
1 2 3 4 | |
1 2 3 4 5 6 7 8 9 10 11 | |
1 2 3 4 5 6 7 8 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | |
1 2 3 4 5 | |
1 2 3 4 5 6 7 8 9 10 11 12 | |
1 2 3 4 5 6 7 8 | |