Abstract / Summary

Given an array and a target sum, determine the fewest non negative integers needed to add so the array sum reaches the target.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 45% (60k+ submissions).

Typical patterns to solve this problem:

• Array
• Greedy

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a single method minElements inside a Solution class. Its purpose is to compute the smallest number of additional elements, each bounded by a given absolute value limit, that must be introduced to an existing integer array nums so that the total sum reaches a target value goal. The algorithm follows a straightforward arithmetic approach: it first determines the current sum of the array, calculates the difference needed to achieve the goal, and then derives the minimal count of bounded elements required to bridge that gap.

Key Steps and Corresponding Code

The core logic unfolds in three distinct statements, each performing a specific transformation.

The first statement aggregates the values already present in the input list:

have = sum(nums)

By invoking Python’s built-in sum, the code leverages a highly optimized C implementation to traverse nums once and produce the cumulative total.

The second statement isolates the shortfall (or surplus) relative to the desired target:

need = goal - have

This subtraction yields a signed integer that represents how much the current sum deviates from goal. A positive result indicates a deficit, while a negative result signals an excess that must be offset.

The final statement converts the magnitude of the deviation into the minimal count of permissible elements:

return ceil(abs(need) / limit)

Here abs extracts the absolute magnitude of need, ensuring the calculation works uniformly for both deficits and surpluses. Division by limit computes the exact fractional number of elements required, and ceil rounds this fraction up to the nearest whole integer, guaranteeing that the returned count is sufficient to cover the entire gap.

Edge Cases Handled

When the existing sum already matches the target (need equals zero), the absolute value is zero, division yields zero, and ceil returns zero. Consequently, the method correctly reports that no additional elements are necessary.

If the required adjustment is not an exact multiple of limit, the division produces a fractional value. The use of ceil ensures that the method rounds up, thereby accounting for the remainder and preventing an underestimation of the needed elements.

The combination of abs and ceil also accommodates scenarios where need is negative. By taking the absolute value before division, the algorithm treats a surplus as a deficit that must be neutralized with elements of opposite sign, preserving correctness across sign variations.

Performance Optimizations Observed

The implementation relies on Python’s native sum function, which is implemented in C and executes with minimal overhead compared to a manual loop. This choice reduces interpreter-level iteration costs and benefits from internal optimizations such as loop unrolling.

All subsequent operations-subtraction, absolute value, division, and ceiling-are constant-time arithmetic operations. By avoiding any additional data structures or iterative constructs beyond the initial sum, the method maintains a tight execution path and low memory footprint.

The use of ceil from the math module (implicitly assumed to be imported) provides a fast, hardware-accelerated rounding operation, further contributing to the method’s efficiency. The overall design therefore achieves the desired result with the fewest possible computational steps.

Imagine you have a big treasure chest of numbers and you want to reach a special target number. First, all the numbers you already have are added together to see what the total is. Next, you look at the difference between what you have and the target goal. This difference tells you how much more you are missing. Since you have a special limit on how large each new number can be, you figure out how many pieces of that size are needed to fill the gap. By using the distance away from the goal and dividing it by the limit, the math shows exactly how many extra numbers you need to add to reach the target.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Python	Java					TS
	WalkCCC	C++			Java
	leetcode.ca	C++		Python	Java		C	Go	Rust	TS
	Progiez	C++		Python	Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	fsq	C++
	haoel	C++
	JoshCrozier		JS
	lkwq007			Python
	suxrobGM					C#
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C, C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
haoel	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality