Skip to main content
Talentd

Minimum Elements to Add to Form a Given Sum - Solution & Explanation

MediumArrayGreedy16 min readAsked at: Twitter
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an integer array nums, a maximum allowed absolute value limit, and a target goal. You can append numbers between -limit and limit. The task is to compute the minimum number of elements required so the final array sum becomes exactly goal.

Approach 1: Simple Calculation Using Greedy Strategy (Time: O(n), Space: O(1))

First compute the current sum of the array using a single pass. The difference between the target and current sum is diff = |goal - sum(nums)|. Each number you add can contribute at most limit toward reducing this difference because its absolute value cannot exceed limit. The optimal strategy is greedy: always use the maximum allowed magnitude to close the gap as quickly as possible. The number of elements required is therefore ceil(diff / limit). This works because using smaller values would only increase the count of elements needed. The algorithm only scans the array once to compute the sum and then performs constant-time math.

This method relies on a greedy observation rather than exploring combinations. Since each inserted element contributes independently to reducing the remaining difference, maximizing each contribution minimizes the number of operations. The approach fits naturally into problems tagged with Greedy and basic Array processing.

Approach 2: Binary Search on Number of Added Elements (Time: O(n + log(diff)), Space: O(1))

Instead of computing the answer directly, you can frame the problem as searching for the smallest k such that k * limit ≥ diff. Start by calculating the same difference diff = |goal - sum(nums)|. Then perform Binary Search over the possible number of added elements. For a candidate value k, check if the maximum achievable adjustment (k * limit) is sufficient to cover diff. If it is, try smaller values; otherwise increase k. This approach is more algorithmic but ultimately arrives at the same answer as the greedy formula.

The binary search formulation can help when reasoning about feasibility conditions or when constraints become more complex in follow‑up problems. However, the mathematical greedy calculation is simpler and faster in practice.

Recommended for interviews: The greedy calculation is the expected solution. Interviewers typically want to see the observation that each added number can reduce the difference by at most limit, which immediately leads to ceil(diff / limit). Explaining the reasoning clearly demonstrates stronger problem‑solving skills than implementing a heavier search approach.

Approach 1: Simple Calculation Using Greedy Strategy

First, calculate the sum of the existing nums array. The target sum needed is given by the goal. To determine how much more (or less) we need to add, find the absolute difference between the current sum and the goal value. The key insight here is that to reduce the number of new elements required, each added element should be as large as possible, constrained by the limit parameter. Therefore, the minimum number of elements we need is the ceiling of the division of the absolute difference by limit.

The solution first calculates the sum of the array, determines the difference to the goal, and computes the minimum number of elements needed using integer division. This is implemented using the formula (diff + limit - 1) / limit to perform ceiling division.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of elements in nums.
Space Complexity: O(1), as no extra space is used apart from variables.

Try this approach in the editor →

Approach 2: Binary Search Approach

Use a binary search to find the minimum number of elements needed. First compute the difference between the current sum and the goal. Using binary search, check if it is possible to reach the goal by adding a certain number of elements, considering their limits. This approach is not more efficient than the greedy method above but offers a different perspective to the problem.

This C implementation uses binary search to identify the minimum number of elements required to adjust the array sum to match goal. It tests potential solutions by checking if multiplying potential counts by limit covers the required diff.

Code

CJavaPython

C

Java

Python

Complexity

Time Complexity: O(n + log(diff / limit)), where n is the length of nums.
Space Complexity: O(1).

Try this approach in the editor →

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

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Simple Calculation Using Greedy Strategy

Time Complexity: O(n), where n is the number of elements in nums.
Space Complexity: O(1), as no extra space is used apart from variables.

Binary Search Approach

Time Complexity: O(n + log(diff / limit)), where n is the length of nums.
Space Complexity: O(1).

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy CalculationO(n)O(1)Best general solution. Direct mathematical insight using ceil(diff/limit).
Binary Search on AnswerO(n + log(diff))O(1)Useful when modeling the problem as a feasibility check or extending to more complex constraints.

Video Solution

Minimum Elements to Add to Form a Given Sum | leetcode 1785 • Coding Decoded • 771 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Minimum Elements to Add to Form a Given Sum easy or hard?
The problem is classified as Medium on LeetCode because it requires recognizing the greedy insight behind the formula ceil(diff / limit). Once the observation is made, the implementation becomes straightforward.
Minimum Elements to Add to Form a Given Sum Python/Java solution
In both Python and Java, compute the array sum, calculate diff = Math.abs(goal - sum), and return (diff + limit - 1) // limit in Python or (diff + limit - 1) / limit in Java for integer ceiling. The implementation is only a few lines and runs in O(n) time.
How to solve Minimum Elements to Add to Form a Given Sum in O(n)?
First compute the sum of the array. Calculate the absolute difference between the goal and this sum. Since each added number can contribute at most limit toward the difference, divide the difference by limit and round up using ceil. This greedy calculation produces the minimal number of elements.
What is the best approach for Minimum Elements to Add to Form a Given Sum?
The optimal approach uses a greedy mathematical observation. Compute the current array sum, calculate diff = |goal − sum|, and note that each added element can change the sum by at most limit. The minimum count is ceil(diff / limit). This runs in O(n) time for the initial sum and O(1) extra space.
Is Minimum Elements to Add to Form a Given Sum asked at Google/Amazon/Meta?
This problem follows a classic greedy and arithmetic reasoning pattern commonly seen in interviews at companies like Amazon and Google. Variations often appear where you must minimize operations while respecting value constraints.
What data structure is used in Minimum Elements to Add to Form a Given Sum?
No advanced data structure is required. The solution only iterates through the input array to compute its sum and then performs a mathematical calculation. The core technique is greedy reasoning rather than structural manipulation.
What is the time complexity of Minimum Elements to Add to Form a Given Sum?
The optimal greedy solution runs in O(n) time because you must iterate through the array once to compute the sum. After that, the answer is calculated with a constant-time formula ceil(diff / limit). Space complexity is O(1).

Ready to solve this problem?

Practice Minimum Elements to Add to Form a Given Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays