Minimum Elements to Add to Form a Given Sum — Solution
Minimum Elements to Add to Form a Given Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Elements to Add to Form a Given Sum is a medium coding problem on arrays and greedy, asked in Amazon, Microsoft and Twitter interviews.
- Difficulty: Medium
- Topics: Arrays, Greedy
- Asked at: Amazon, Microsoft, Twitter
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Every element of nums satisfies |nums[i]| <= limit.
You may append new integers to nums, each of which must also satisfy |x| <= limit. Return the minimum number of integers you need to append so that the sum of the array equals goal.
CodeKairo bounds: the array and value limits are smaller than in the original problem so that the answer and every intermediate sum fit in a 32-bit integer.
Example 1
Input: nums = [2,-3,4], limit = 2, goal = 10
Output: 4
Explanation: The sum is 3 and 7 more is needed: `2 + 2 + 2 + 1`.
Example 2
Input: nums = [5,-5], limit = 5, goal = 0
Output: 0
Example 3
Input: nums = [-1,1,-1], limit = 1, goal = -6
Output: 5
Explanation: The sum is -1, so five more `-1`s are needed.
Constraints
1 <= nums.length <= 10^41 <= limit <= 10^5-limit <= nums[i] <= limit-10^9 <= goal <= 10^9
Hints for Minimum Elements to Add to Form a Given Sum
Hint 1
Only the gap
|goal - sum(nums)|matters, not the individual elements.Hint 2
Each appended number can close at most
limitof the gap.Hint 3
So the answer is the gap divided by
limit, rounded up.
How to solve Minimum Elements to Add to Form a Given Sum
Each new element moves the sum by at most limit, so closing a gap of d needs at least ceil(d / limit) elements — and that many always suffice.
Approach
- Compute the current sum (in 64-bit if your bounds allow larger values).
- Let
d = |goal - sum|. - Return
(d + limit - 1) / limitusing integer division.
Why it works
Fewer than ceil(d / limit) elements can move the sum by less than d. With exactly that many, use limit (with the sign of the gap) for all but the last one and the remainder for the last, which is at most limit in absolute value.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- With the original bounds (
nup to 10^5,limitup to 10^6) the sum and the gap overflow 32 bits — accumulate in 64 bits. - Use integer ceiling division; floating point can round wrongly for large values.
- A gap of zero needs zero elements.
Reference solution
Python
from typing import List
def minElements(nums: List[int], limit: int, goal: int) -> int:
d = abs(goal - sum(nums))
return (d + limit - 1) // limitJava
public static int minElements(int[] nums, int limit, int goal) {
long sum = 0;
for (int v : nums) sum += v;
long d = Math.abs((long) goal - sum);
return (int) ((d + limit - 1) / limit);
}C++
int minElements(vector<int>& nums, int limit, int goal) {
long long sum = 0;
for (int v : nums) sum += v;
long long d = llabs((long long)goal - sum);
return (int)((d + limit - 1) / limit);
}JavaScript
var minElements = function(nums, limit, goal) {
var sum = 0;
for (var i = 0; i < nums.length; i++) sum += nums[i];
var d = Math.abs(goal - sum);
return Math.floor((d + limit - 1) / limit);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms