# Minimum Elements to Add to Form a Given Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-elements-to-add-to-form-a-given-sum)
Canonical: https://scaleengineer.com/dsa/problems/minimum-elements-to-add-to-form-a-given-sum
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [X](https://scaleengineer.com/companies/x)
---
## 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 <= 105`
* `1 <= limit <= 106`
* `-limit <= nums[i] <= limit`
* `-109 <= goal <= 109`

# Approaches
## Iterative Subtraction (Greedy Simulation)
This approach simulates the process of adding elements one by one. It first calculates the total difference required to reach the `goal`. Then, in a loop, it repeatedly subtracts `limit` from this difference, incrementing a counter each time. This process continues until the difference is covered. This is a direct simulation of a greedy strategy where we add the largest possible value (`limit`) in each step.
**Time:** O(N + abs(goal - sum) / limit), where N is the number of elements in `nums`. The initial summation takes O(N) time. The `while` loop can take a very long time if the difference is large and the limit is small, making this approach inefficient for the given constraints. · **Space:** O(1) extra space, as we only use a few variables to store the sum and the count.
**Pros:** The logic is straightforward and easy to understand as it directly models the problem statement.
**Cons:** This approach can be very slow if the difference `diff` is much larger than the `limit`. The number of iterations is proportional to `diff / limit`, which can lead to a 'Time Limit Exceeded' error on large inputs.
### Explanation
First, we need to determine the total value we need to add to the array. This is the difference between the `goal` and the current sum of the array's elements. We calculate the current sum by iterating through the `nums` array. It's crucial to use a `long` variable for the sum to avoid potential integer overflow, given the problem's constraints.

Let `diff = goal - currentSum`. The absolute value of this difference, `abs(diff)`, is the total magnitude we need to add. To minimize the number of elements, we should greedily add elements with the maximum allowed magnitude, which is `limit`.

We can simulate this process. We initialize a counter for the number of new elements to 0. We then loop as long as the remaining difference is greater than 0. In each iteration, we subtract `limit` from the remaining difference and increment our counter. This loop effectively counts how many times we need to add an element of magnitude `limit` to cover the total required difference. The final value of the counter is the minimum number of elements required.

```java
class Solution {
    public int minElements(int[] nums, int limit, int goal) {
        long sum = 0;
        for (int num : nums) {
            sum += num;
        }

        long diff = Math.abs(goal - sum);
        if (diff == 0) {
            return 0;
        }

        int count = 0;
        while (diff > 0) {
            diff -= limit;
            count++;
        }
        return count;
    }
}
```
### Algorithm
- Calculate the sum of all elements in the `nums` array. Use a `long` data type to prevent potential integer overflow.
- Determine the difference between the `goal` and the calculated `sum`. Let this be `diff = goal - sum`.
- Take the absolute value of the difference, let's call it `remaining = abs(diff)`.
- If `remaining` is 0, the sum is already at the goal, so return 0.
- Initialize a counter for the number of added elements, `count = 0`.
- Start a loop that continues as long as `remaining > 0`.
- Inside the loop, subtract `limit` from `remaining` and increment `count`.
- This simulates adding one element of the maximum possible magnitude (`limit`) in each step.
- Once the loop finishes, `count` will hold the minimum number of elements required. Return `count`.

## Direct Mathematical Calculation (Optimal)
This is the most efficient approach, which solves the problem using a direct mathematical formula. It avoids any time-consuming loops for calculating the number of elements. After finding the total difference needed to reach the `goal`, it uses a single arithmetic expression to determine the minimum number of elements. The core idea is that to minimize the count of added elements, each element should have the maximum possible magnitude, which is `limit`.
**Time:** O(N), where N is the length of `nums`. This is dominated by the initial loop to calculate the sum of the array. The rest of the calculation is O(1). · **Space:** O(1) extra space. We only use a few variables to store the sum and the difference.
**Pros:** Extremely efficient. After the initial sum calculation, the result is found in constant time.; Handles all edge cases and constraints correctly, provided `long` is used for calculations.
**Cons:** Requires careful handling of data types. Using a standard 32-bit integer for the sum will lead to overflow and incorrect results for large inputs.
### Explanation
This optimal approach calculates the result directly without any simulation. The first step is to find the current sum of the elements in the `nums` array. As the sum can exceed the capacity of a 32-bit integer, we must use a 64-bit integer (`long` in Java) to store it.

Next, we calculate the difference between the `goal` and the `currentSum`. Let this be `diff = goal - currentSum`. This `diff` represents the total value that needs to be added to the array by the new elements. If `diff` is zero, the sum is already equal to the goal, and we need to add 0 elements.

Otherwise, we need to cover a total difference of `abs(diff)`. To do this with the minimum number of elements, each element we add should have the largest possible magnitude, which is `limit`. The problem then becomes: how many numbers of value `limit` are needed to sum up to at least `abs(diff)`? This is a classic division problem that can be solved with the ceiling function: `ceil(abs(diff) / limit)`.

In integer arithmetic, the ceiling of `a / b` (for positive `a`, `b`) can be calculated as `(a + b - 1) / b`. This avoids floating-point arithmetic and potential precision issues. So, the final answer is `(Math.abs(diff) + limit - 1) / limit`.

```java
class Solution {
    public int minElements(int[] nums, int limit, int goal) {
        // Use long for sum to avoid overflow
        long sum = 0;
        for (int num : nums) {
            sum += num;
        }

        // Calculate the absolute difference needed
        long diff = Math.abs(goal - sum);

        // If the sum is already the goal, no elements are needed
        if (diff == 0) {
            return 0;
        }

        // Calculate how many elements of size 'limit' are needed to cover the difference.
        // This is equivalent to ceil(diff / limit).
        // Using integer arithmetic: (diff + limit - 1) / limit
        return (int)((diff + limit - 1) / limit);
    }
}
```
### Algorithm
- Calculate the sum of all elements in the `nums` array. It is essential to use a `long` data type for the sum to prevent integer overflow.
- Calculate the difference required to reach the goal: `diff = goal - sum`.
- If `diff` is 0, the sum is already correct. Return 0.
- The total magnitude that needs to be covered by new elements is `abs(diff)`.
- To use the minimum number of elements, each new element should contribute the maximum possible magnitude, which is `limit`.
- The problem reduces to finding how many elements of size `limit` are needed to cover a total of `abs(diff)`. This is a division problem that requires finding the ceiling of the division.
- The number of elements is `ceil(abs(diff) / limit)`.
- This ceiling operation can be performed using integer arithmetic to avoid floating-point issues: `(abs(diff) + limit - 1) / limit`.
- Return the result of this calculation.

# Solutions
### Java

```java
class Solution { public int minElements ( int [] nums , int limit , int goal ) { // long s = Arrays.stream(nums).asLongStream().sum(); long s = 0 ; for ( int v : nums ) { s += v ; } long d = Math . abs ( s - goal ); return ( int ) (( d + limit - 1 ) / limit ); } }
```

### CPP

```cpp
class Solution { public: int minElements ( vector < int >& nums , int limit , int goal ) { long long s = accumulate ( nums . begin (), nums . end (), 0ll ); long long d = abs ( s - goal ); return ( d + limit - 1 ) / limit ; } };
```

### Python

```python
class Solution : def minElements ( self , nums : List [ int ], limit : int , goal : int ) -> int : d = abs ( sum ( nums ) - goal ) return ( d + limit - 1 ) // limit
```