Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1785.html

1785. Minimum Elements to Add to Form a Given Sum

Level

Medium

Description

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^5
  • 1 <= limit <= 10^6
  • -limit <= nums[i] <= limit
  • -10^9 <= goal <= 10^9

Solution

First, calculate sum as the sum of all elements in nums. Next, calculate the absolute difference between goal and sum, and calculate the minimum number of elements to add using a greedy approach, which means consider adding limit or -limit as many as possible and adding one more element if the remaining absolute difference is less than limit.

  • class Solution {
    public int minElements(int[] nums, int limit, int goal) {
        long sum = 0;
        for (int num : nums)
            sum += (long) num;
        long difference = (long) goal - sum;
        if (difference == 0)
            return 0;
        else {
            difference = Math.abs(difference);
            long minAdd = difference / limit;
            if (difference % limit != 0)
                minAdd++;
            return (int) minAdd;
        }
    }
}

############

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);
    }
}

  • // OJ: https://leetcode.com/problems/minimum-elements-to-add-to-form-a-given-sum/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int minElements(vector<int>& A, int limit, int goal) {
        long sum = abs(goal - accumulate(begin(A), end(A), 0L));
        return (sum + limit - 1) / limit;
    }
};

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

############

# 1785. Minimum Elements to Add to Form a Given Sum
# https://leetcode.com/problems/minimum-elements-to-add-to-form-a-given-sum/

class Solution:
    def minElements(self, nums: List[int], limit: int, goal: int) -> int:
        total = sum(nums)
        target = abs(goal - total)
        
        res = target // limit + (1 if target % limit else 0)
        
        return res


  • 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
}

  • 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);
}


  • 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
    }
}

All Problems

All Solutions