Minimum Elements to Add to Form a Given Sum

Medium
1144.

Minimum Elements to Add to Form a Given Sum

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.

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^4
  • 1 <= limit <= 10^5
  • -limit <= nums[i] <= limit
  • -10^9 <= goal <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} limit
 * @param {number} goal
 * @return {number}
 */
var minElements = function(nums, limit, goal) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^4
  • 1 <= limit <= 10^5
  • -limit <= nums[i] <= limit
  • -10^9 <= goal <= 10^9

Hints for Minimum Elements to Add to Form a Given Sum

  1. Hint 1

    Only the gap |goal - sum(nums)| matters, not the individual elements.

  2. Hint 2

    Each appended number can close at most limit of the gap.

  3. 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

  1. Compute the current sum (in 64-bit if your bounds allow larger values).
  2. Let d = |goal - sum|.
  3. Return (d + limit - 1) / limit using 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 (n up to 10^5, limit up 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) // limit

Java

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