1785. Minimum Elements to Add to Form a Given Sum - Solution

The problem

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 <= 10⁵
1 <= limit <= 10⁶
-limit <= nums[i] <= limit
-10⁹ <= goal <= 10⁹

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.

Python

def min_elements(nums, limit, goal):
    current_sum = sum(nums)
    diff = abs(goal - current_sum)
    return (diff + limit - 1) // limit

nums = [1, -1, 1]
limit = 3
goal = -4
print(min_elements(nums, limit, goal))

Java

import java.util.*;

public class MinElements {
    public static int minElements(int[] nums, int limit, long goal) {
        long sum = 0;
        for (int num : nums) sum += num;
        long diff = Math.abs(goal - sum);
        return (int) ((diff + limit - 1) / limit);
    }

    public static void main(String[] args) {
        int[] nums = {1, -1, 1};
        int limit = 3;
        long goal = -4;
        System.out.println(minElements(nums, limit, goal));
    }
}

C++

#include <vector>
#include <cmath>
#include <iostream>

int minElements(std::vector<int>& nums, int limit, long goal) {
    long sum = 0;
    for (int num : nums) sum += num;
    long diff = std::labs(goal - sum);
    return (diff + limit - 1) / limit;
}

int main() {
    std::vector<int> nums = {1, -1, 1};
    int limit = 3;
    long goal = -4;
    std::cout << minElements(nums, limit, goal) << std::endl;
    return 0;
}

JavaScript

function minElements(nums, limit, goal) {
    let sum = nums.reduce((acc, num) => acc + num, 0);
    let diff = Math.abs(goal - sum);
    return Math.ceil(diff / limit);
}

const nums = [1, -1, 1];
const limit = 3;
const goal = -4;
console.log(minElements(nums, limit, goal));

#include <stdio.h>
#include <stdlib.h>

int minElements(int* nums, int numsSize, int limit, long goal) {
    long sum = 0;
    for (int i = 0; i < numsSize; i++) sum += nums[i];
    long diff = labs(goal - sum);
    return (diff + limit - 1) / limit;
}

int main() {
    int nums[] = {1, -1, 1};
    int size = 3;
    int limit = 3;
    long goal = -4;
    printf("%d\n", minElements(nums, size, limit, goal));
    return 0;
}

using System;
class MinElements {
    public static int MinElements(int[] nums, int limit, long goal) {
        long sum = 0;
        foreach (int num in nums) sum += num;
        long diff = Math.Abs(goal - sum);
        return (int)((diff + limit - 1) / limit);
    }

    static void Main(string[] args) {
        int[] nums = { 1, -1, 1 };
        int limit = 3;
        long goal = -4;
        Console.WriteLine(MinElements(nums, limit, goal));
    }
}

In Python, the sum of the array is computed with sum(), and abs() is used to calculate the absolute difference. The method employs integer division with ceiling to find the minimum number of elements.

Complexity

Time Complexity: O(n).
Space Complexity: O(1).

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.

Python

def min_elements_binary(nums, limit, goal):
    current_sum = sum(nums)
    diff = abs(goal - current_sum)

    left, right = 0, (diff // limit) + 1
    while left < right:
        mid = (left + right) // 2
        if mid * limit >= diff:
            right = mid
        else:
            left = mid + 1
    return left

nums = [1, -1, 1]
limit = 3
goal = -4
print(min_elements_binary(nums, limit, goal))

Java

public class MinElementsBinary {
    public static int minElementsBinary(int[] nums, int limit, long goal) {
        long sum = 0;
        for (int num : nums) sum += num;
        long diff = Math.abs(goal - sum);

        int left = 0, right = (int) (diff / limit + 1);
        while (left < right) {
            int mid = left + (right - left) / 2;
            if ((long) mid * limit >= diff)
                right = mid;
            else
                left = mid + 1;
        }
        return left;
    }

    public static void main(String[] args) {
        int[] nums = {1, -1, 1};
        int limit = 3;
        long goal = -4;
        System.out.println(minElementsBinary(nums, limit, goal));
    }
}

#include <stdio.h>
#include <stdlib.h>

int minElementsBinary(int* nums, int numsSize, int limit, long goal) {
    long sum = 0;
    for (int i = 0; i < numsSize; i++) sum += nums[i];
    long diff = labs(goal - sum);

    int left = 0, right = diff / limit + 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if ((long)mid * limit >= diff)
            right = mid;
        else
            left = mid + 1;
    }
    return left;
}

int main() {
    int nums[] = {1, -1, 1};
    int size = 3;
    int limit = 3;
    long goal = -4;
    printf("%d\n", minElementsBinary(nums, size, limit, goal));
    return 0;
}

In Python, the binary search involves checking for the condition mid * limit >= diff to narrow down the possible counts of required additional elements.

Complexity

Time Complexity: O(n + log(diff / limit)).
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.

TypeScript

function minElements(nums: number[], limit: number, goal: number): number {
    const sum = nums.reduce((r, v) => r + v, 0);
    const diff = Math.abs(goal - sum);
    return Math.floor((diff + limit - 1) / limit);
}

func minElements(nums []int, limit int, goal int) int {
	s := 0
	for _, v := range nums {
		s += v
	}
	d := abs(s - goal)
	return (d + limit - 1) / limit
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

Rust

impl Solution {
    pub fn min_elements(nums: Vec<i32>, limit: i32, goal: i32) -> i32 {
        let limit = limit as i64;
        let goal = goal as i64;
        let mut sum = 0;
        for &num in nums.iter() {
            sum += num as i64;
        }
        let diff = (goal - sum).abs();
        ((diff + limit - 1) / limit) as i32
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Simple Calculation Using Greedy Strategy	Time Complexity: O(n). Space Complexity: O(1).
Binary Search Approach	Time Complexity: O(n + log(diff / limit)). Space Complexity: O(1).
Greedy	–

Complexity analysis

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

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

Minimum Elements to Add to Form a Given Sum solution and explanation

The problem

Approach overview

Approach 1: Simple Calculation Using Greedy Strategy

Approach 2: Binary Search Approach

Approach 3: Greedy

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum Elements to Add to Form a Given Sum solution and explanation

The problem

Approach overview

Approach 1: Simple Calculation Using Greedy Strategy

Approach 2: Binary Search Approach

Approach 3: Greedy

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems