Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Every allowed operation decreases the array sum by exactly one. Therefore the identities of the modified elements do not affect the number of operations needed; only the total sum's remainder modulo k matters.

Approach

Sum the array and return sum % k. If the remainder is zero, the sum is already divisible and no operation is needed. Otherwise subtracting that remainder reaches the greatest multiple of k below the current sum.

Fewer operations cannot work because every smaller decrease leaves the sum strictly between those consecutive multiples. The remainder is less than k and at most the nonnegative total sum, so the required decreases can be distributed across the array's available values. No simulation or mutation of the array is necessary.

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        return sum(nums) % k

Complexity analysis

Let n = nums.length. Time: O(n). Auxiliary space: O(1) in both versions.