Minimum Elements to Add to Form a Given Sum

Minimum Elements to Add to Form a Given Sum - Problem

Array Greedy Medium

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,-1,1], limit = 3, goal = -4

› Output: 2

💡 Note: Current sum is 1-1+1 = 1. Need to reach -4, so gap is 5. Using elements of size ≤3, we need at least ceil(5/3) = 2 elements, like adding [-3, -2].

Example 2 — Already at Goal

$ Input: nums = [1,-10,9,1], limit = 100, goal = 1

› Output: 0

💡 Note: Current sum is 1-10+9+1 = 1, which equals the goal. No elements need to be added.

Example 3 — Large Gap

$ Input: nums = [1,2], limit = 2, goal = 10

› Output: 4

💡 Note: Current sum is 3, goal is 10, gap is 7. Using max elements of size 2, we need ceil(7/2) = 4 elements.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ limit ≤ 10⁶
-10⁹ ≤ nums[i] ≤ 10⁹
-10⁹ ≤ goal ≤ 10⁹

Visualization

Tap to expand

Asked in

G Google 12 a Amazon 8 f Meta 6 M Microsoft 5

The key insight is that to minimize the number of elements added, we should use the largest possible elements within the limit constraint. The optimal approach calculates the absolute difference between the current sum and goal, then divides by the limit (rounding up) to get the minimum count. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(2^k)	O(k)	Try all possible combinations of elements to add
Greedy Mathematical Approach	O(n)	O(1)	Use largest possible elements to minimize count

Brute Force Simulation — Algorithm Steps

Calculate current sum of array
Find difference needed to reach goal
Try all combinations of valid elements
Return minimum count that achieves goal

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Gap

Find difference between current sum and goal

Try Combinations

Recursively try all valid elements within limit

Find Minimum

Return the combination with minimum count

Code -

solution.c — C

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

int minElements(int remaining, int count, int limit) {
    if (remaining == 0) return count;
    if (count > abs(remaining)) return INT_MAX;
    
    int minCount = INT_MAX;
    for (int val = -limit; val <= limit; val++) {
        if (val != 0) {
            int result = minElements(remaining - val, count + 1, limit);
            if (result != INT_MAX && result < minCount) {
                minCount = result;
            }
        }
    }
    return minCount;
}

int solution(int* nums, int numsSize, int limit, int goal) {
    int currentSum = 0;
    for (int i = 0; i < numsSize; i++) {
        currentSum += nums[i];
    }
    int diff = goal - currentSum;
    
    if (diff == 0) return 0;
    
    return minElements(diff, 0, limit);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[100];
    int numsSize = 0;
    
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int limit, goal;
    scanf("%d", &limit);
    scanf("%d", &goal);
    
    printf("%d\n", solution(nums, numsSize, limit, goal));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^k)

Where k is the difference divided by limit, we try all combinations

✓ Linear Growth

Space Complexity

O(k)

Recursion stack depth for trying combinations

✓ Linear Space

18.5K Views

Medium Frequency

~15 min Avg. Time

654 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler