README_EN.md

comments	difficulty	edit_url	rating	source	tags
true	Easy	https://github.com/doocs/leetcode/edit/main/solution/3100-3199/3190.Find%20Minimum%20Operations%20to%20Make%20All%20Elements%20Divisible%20by%20Three/README_EN.md	1139	Biweekly Contest 133 Q1	Array Math

3190. Find Minimum Operations to Make All Elements Divisible by Three

中文文档

Description

You are given an integer array nums. In one operation, you can add or subtract 1 from any element of nums.

Return the minimum number of operations to make all elements of nums divisible by 3.

 

Example 1:

Input: nums = [1,2,3,4]

Output: 3

Explanation:

All array elements can be made divisible by 3 using 3 operations:

• Subtract 1 from 1.
• Add 1 to 2.
• Subtract 1 from 4.

Example 2:

Input: nums = [3,6,9]

Output: 0

 

Constraints:

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 50

Solutions

Solution 1: Mathematics

We directly iterate through the array $\textit{nums}$. For each element $x$, we calculate the remainder of $x$ divided by 3, $x \bmod 3$. If the remainder is not 0, we need to make $x$ divisible by 3 with the minimum number of operations. Therefore, we can choose to either decrease $x$ by $x \bmod 3$ or increase $x$ by $3 - x \bmod 3$, and we accumulate the minimum of these two values to the answer.

The time complexity is $O(n)$, where $n$ is the length of the array $\textit{nums}$. The space complexity is $O(1)$.

Python3

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        ans = 0
        for x in nums:
            if mod := x % 3:
                ans += min(mod, 3 - mod)
        return ans

Java

class Solution {
    public int minimumOperations(int[] nums) {
        int ans = 0;
        for (int x : nums) {
            int mod = x % 3;
            if (mod != 0) {
                ans += Math.min(mod, 3 - mod);
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int ans = 0;
        for (int x : nums) {
            int mod = x % 3;
            if (mod) {
                ans += min(mod, 3 - mod);
            }
        }
        return ans;
    }
};

Go

func minimumOperations(nums []int) (ans int) {
	for _, x := range nums {
		if mod := x % 3; mod > 0 {
			ans += min(mod, 3-mod)
		}
	}
	return
}

TypeScript

function minimumOperations(nums: number[]): number {
    let ans = 0;
    for (const x of nums) {
        const mod = x % 3;
        if (mod) {
            ans += Math.min(mod, 3 - mod);
        }
    }
    return ans;
}