Minimum Operations to Make Array Sum Divisible by K

Difficulty: Easy | Acceptance: 92.30% | Paid: No Topics: Array, Math

You are given an array nums and an integer k. You can perform the following operation any number of times: Choose an element from nums and remove it. Return the minimum number of operations to make the sum of the remaining elements divisible by k.

It is guaranteed that it is always possible to make the sum of the remaining elements divisible by k.

• Examples
• Constraints
• Dynamic Programming
• Brute Force

Examples

Example 1

Input:

nums = [3,9,7], k = 5

Output:

4

Explanation: Perform 4 operations on nums[1] = 9. Now, nums = [3, 5, 7].

The sum is 15, which is divisible by 5.

Example 2

Input:

nums = [4,1,3], k = 4

Output:

0

Explanation: The sum is 8, which is already divisible by 4. Hence, no operations are needed.

Example 3

Input:

nums = [3,2], k = 6

Output:

5

Explanation: Perform 3 operations on nums[0] = 3 and 2 operations on nums[1] = 2. Now, nums = [0, 0].

The sum is 0, which is divisible by 6.

Constraints

- 1 <= nums.length <= 1000
- 1 <= nums[i] <= 1000
- 1 <= k <= 100

Dynamic Programming

Intuition We need to find the smallest subset of elements to remove such that the sum of the removed elements has a remainder equal to the total sum’s remainder when divided by k. This is a variation of the 0/1 Knapsack problem where we minimize the count of items to achieve a specific remainder.

Steps

• Calculate the total sum of nums and the target remainder target = total % k.
• If target is 0, return 0.
• Initialize a DP array dp of size k with infinity, where dp[r] represents the minimum number of elements needed to achieve a sum with remainder r. Set dp[0] = 0.
• Iterate through each number in nums. For each number, calculate its remainder rem.
• Update the dp array in reverse order (from k-1 down to 0) to ensure each number is only used once. For each remainder j, update dp[(j + rem) % k] with min(dp[(j + rem) % k], dp[j] + 1).
• The answer will be dp[target].

class Solution:
    def minOperations(self, nums: list[int], k: int) -> int:
        total = sum(nums)
        target = total % k
        if target == 0:
            return 0
        
        # dp[r] = min elements to achieve remainder r
        dp = [float('inf')] * k
        dp[0] = 0
        
        for num in nums:
            rem = num % k
            # Iterate backwards to avoid using the same element multiple times
            for j in range(k - 1, -1, -1):
                if dp[j] != float('inf'):
                    new_rem = (j + rem) % k
                    dp[new_rem] = min(dp[new_rem], dp[j] + 1)
        
        return dp[target]

Complexity

• Time: O(n * k)
• Space: O(k)
• Notes: Efficient for small values of k.

Brute Force

Intuition Since the constraints on the array length are small (n <= 50), we can check every possible subset of elements to see if removing that subset results in a sum divisible by k. We iterate through all possible non-empty subsets using bitmasking.

Steps

• Calculate the total sum of nums and the target remainder target = total % k.
• If target is 0, return 0.
• Initialize min_ops to n (maximum possible operations).
• Iterate through all bitmasks from 1 to 2ⁿ - 1. Each bit in the mask represents whether an element is included in the subset to be removed.
• For each mask, calculate the sum of the selected elements and the count of elements (number of set bits).
• If sum % k == target, update min_ops with the minimum count found.
• Return min_ops.

class Solution:
    def minOperations(self, nums: list[int], k: int) -> int:
        total = sum(nums)
        target = total % k
        if target == 0:
            return 0
        
        n = len(nums)
        min_ops = n
        
        # Iterate through all possible non-empty subsets
        for mask in range(1, 1 << n):
            current_sum = 0
            count = 0
            for i in range(n):
                if mask & (1 << i):
                    current_sum += nums[i]
                    count += 1
            
            if current_sum % k == target:
                min_ops = min(min_ops, count)
                
        return min_ops

Complexity

• Time: O(n * 2ⁿ)
• Space: O(1)
• Notes: Simple to implement but exponential time complexity. Only suitable for very small n.