Given an array where elements are multiples of 3 and some elements are not, if an element is not a multiple of 3, either add to or subtract from it to make it a multiple of 3. Return the minimum number of times you need to add or subtract from a number to make all elements multiples of 3. Function Description Complete the function minimizeMultiplesOfThree in the editor. minimizeMultiplesOfThree has the following parameter:

• int arr[]: an array of integers Returns int: the minimum number of operations required

Example 1

Input:

arr = [12, 21, 3, 4]

Output:

1

Explanation: 12, 21, and 3 are all multiples of 3, but 4 is not. To make 4 a multiple of 3, subtract 1 from it to get 3. The total number of operations made is 1 (by subtracting 1 from 4).

Example 2

Input:

arr = [4, 5]

Output:

2

Explanation:

解法

对每个元素求 x mod 3：若余 0 无需操作；余 1 或余 2 都只需 1 次(要么 ±1 要么 ±2 在题面允许下，但取最小 min(r, 3 - r)，对于 r=1 或 r=2 都等于 1)。所以答案 = 不能被 3 整除的元素个数。复杂度 O(n)，空间 O(1)。

from typing import List

def minimize_multiples_of_three(arr: List[int]) -> int:
    return sum(1 for x in arr if x % 3 != 0)

class Solution {
    int minimizeMultiplesOfThree(int[] arr) {
        int cnt = 0;
        for (int x : arr) if (((x % 3) + 3) % 3 != 0) cnt++;
        return cnt;
    }
}

class Solution {
public:
    int minimizeMultiplesOfThree(vector<int>& arr) {
        int cnt = 0;
        for (int x : arr) if (((x % 3) + 3) % 3 != 0) ++cnt;
        return cnt;
    }
};