Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Changing one element does not affect any other element, so minimize the operations for each value separately. Its remainder modulo three tells us its distance from the nearest multiples of three.

Approach

For each value, compute remainder = value % 3. Decreasing it to the previous multiple costs remainder operations; increasing it to the next costs 3 - remainder. Add the smaller cost to the answer.

A remainder of zero contributes zero. A remainder of one or two contributes one, by subtracting or adding one respectively. Summing these independent minimum costs is optimal because every nondivisible element needs at least one operation and no operation can fix two different elements at once.

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        res = 0

        for x in nums:
            rem = x % 3
            res += min(rem, 3 - rem)

        return res

Complexity analysis

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