3512. Minimum Operations to Make Array Sum Divisible by K

Problem Description

You are given an integer array nums and an integer k. You can perform the following operation any number of times:

Select an index i and replace nums[i] with nums[i] - 1.

Return the minimum number of operations required to make the sum of the array divisible by k.

Intuition

The core idea of this problem is to adjust the array nums such that its sum becomes divisible by k. To solve this, consider the sum S of all elements in nums. If S is already divisible by k (i.e., S % k == 0), then no operation is required. However, if S % k is not zero, this means the remainder r = S % k indicates how far S is from being divisible by k.

To make the sum divisible by k, we need to perform a number of operations that collectively decrease the sum by r. Since each operation reduces an element by 1, you need at least r operations to achieve this condition where (S - r) % k == 0. Thus, the minimum number of operations required is directly equal to the current remainder when the sum is divided by k, which is r = S % k.

Learn more about Math patterns.

Solution Approach

To solve this problem, we leverage the properties of the modulo operation. The goal is to modify the elements of nums such that the sum is divisible by k. Here's the step-by-step approach:

Calculate the Current Sum: Start by calculating the sum of all elements in the array nums. Let's denote this sum as S.
Determine the Remainder: Find the remainder of this sum when divided by k using the expression S % k. This gives us the r, the excess amount by which the current sum is not divisible by k.
Operations Required: The minimum number of operations required to adjust the sum to be divisible by k is exactly equal to r. This is because each operation reduces an element by 1 and effectively reduces the sum by 1.

The algorithm can be implemented simply:

def minOperations(nums: List[int], k: int) -> int:
    # Calculate the sum of the array
    total_sum = sum(nums)
    # Determine the excess remainder when sum is divided by k
    remainder = total_sum % k
    # The remainder indicates the minimum operations needed
    return remainder

In this approach, we efficiently calculate the remainder with respect to k using the properties of arithmetic operations. This makes the solution both elegant and optimal.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's go through a small example to illustrate the solution approach.

Suppose we have the array nums = [4, 5, 6] and k = 5.

Calculate the Current Sum: First, determine the sum of all elements in nums. [ S = 4 + 5 + 6 = 15 ]
Determine the Remainder: Next, find the remainder of this sum when divided by k. [ r = S % k = 15 % 5 = 0 ]
Operations Required: Since the remainder r is 0, the sum 15 is already divisible by 5, meaning no operations are needed.

Thus, the minimum number of operations required to make the sum of the array divisible by 5 is 0.

This simple example illustrates that when the initial sum of the array is already divisible by k, no adjustment operations are necessary.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minOperations(self, nums: List[int], k: int) -> int:
5        # Calculate the sum of elements in the list 'nums'
6        total_sum = sum(nums)
7
8        # Return the remainder when 'total_sum' is divided by 'k'
9        return total_sum % k
10

1import java.util.Arrays;
2
3class Solution {
4    public int minOperations(int[] nums, int k) {
5        // Calculate the total sum of the elements in the array 'nums'
6        int totalSum = Arrays.stream(nums).sum();
7      
8        // Return the remainder when 'totalSum' is divided by 'k'
9        return totalSum % k;
10    }
11}
12

1#include <vector>
2#include <numeric> // Include this header for the std::accumulate function
3
4class Solution {
5public:
6    int minOperations(std::vector<int>& nums, int k) {
7        // Calculate the sum of all elements in the vector nums
8        int totalSum = std::accumulate(nums.begin(), nums.end(), 0);
9      
10        // Return the remainder of the sum when divided by k
11        return totalSum % k;
12    }
13};
14

1/**
2 * Calculates the minimum number of operations needed
3 * to make the sum of the given array `nums` divisible by `k`.
4 * 
5 * @param nums - An array of numbers for which the operations are calculated.
6 * @param k - The divisor to determine divisibility.
7 * @returns The remainder of the sum of `nums` when divided by `k`.
8 */
9function minOperations(nums: number[], k: number): number {
10    // Calculate the sum of all elements in the array `nums`
11    const totalSum = nums.reduce((accumulator, currentValue) => accumulator + currentValue, 0);
12  
13    // Return the remainder of the total sum when divided by `k`
14    return totalSum % k;
15}
16

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the list nums. This is because the function sum(nums) iterates through the entire list once to calculate the total sum. The space complexity is O(1), as no additional space proportional to the input size is used, aside from the input itself and a constant amount for storing the sum and the result.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: