What is the best approach to solve the "Find Minimum Operations to Make All Elements Divisible by Three" problem?

The optimal approach is to analyze the remainder of each element when divided by 3, then perform minimal operations based on whether the remainder is 1 or 2.

What is the time complexity of solving this problem?

The time complexity is O(n), where n is the length of the input array, because we only need to iterate over the array once.

How do I handle cases where elements are already divisible by 3?

If an element is already divisible by 3, no operation is needed. Simply skip such elements during the counting process.

What happens if the array contains negative numbers?

Negative numbers can also be handled by calculating their remainder when divided by 3, and adjusting them with the appropriate number of additions or subtractions.

Can this problem be solved with a greedy approach?

Yes, this problem can be solved with a greedy approach, as each element can be adjusted independently with minimal steps to make it divisible by 3.

#3190

Easy

auto_awesome数组·数学

LeetCode 题解工作台

使所有元素都可以被 3 整除的最少操作数

给你一个整数数组 nums 。一次操作中，你可以将 nums 中的任意一个元素增加或者减少 1 。请你返回将 nums 中所有元素都可以被 3 整除的最少操作次数。示例 1：输入： nums = [1,2,3,4] 输出： 3 解释：通过以下 3 个操作，数组中的所有元素都可以被 3…

数组数学

题目描述

给你一个整数数组 nums 。一次操作中，你可以将 nums 中的任意一个元素增加或者减少 1 。

请你返回将 nums 中所有元素都可以被 3 整除的最少操作次数。

示例 1：

输入：nums = [1,2,3,4]

输出：3

解释：

通过以下 3 个操作，数组中的所有元素都可以被 3 整除：

将 1 减少 1 。
将 2 增加 1 。
将 4 减少 1 。

示例 2：

输入：nums = [3,6,9]

输出：0

提示：

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

lightbulb

解题思路

方法一：计数

我们直接遍历数组 $\textit{nums}$ ，对于每个元素 $x$ ，如果 $x \bmod 3 \neq 0$ ，那么有两种情况：

如果 $x \bmod 3 = 1$ ，我们可以将 $x$ 减少 $1$ ，使其变为 $x - 1$ ，此时 $x - 1$ 可以被 $3$ 整除。
如果 $x \bmod 3 = 2$ ，我们可以将 $x$ 增加 $1$ ，使其变为 $x + 1$ ，此时 $x + 1$ 可以被 $3$ 整除。

因此，我们只需要统计数组中不能被 $3$ 整除的元素个数，即可得到最少操作次数。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        return sum(x % 3 != 0 for x in nums)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for the candidate's ability to recognize the mod 3 pattern and simplify operations efficiently.
question_mark
Assess how quickly the candidate arrives at an optimal approach without brute force.
question_mark
Evaluate the candidate's approach to handling edge cases, such as when all elements are divisible by 3.

warning

常见陷阱

外企场景

error
Failing to correctly handle numbers that are already divisible by 3, leading to unnecessary operations.
error
Overcomplicating the approach by not recognizing the simple modulo operation as the key to reducing the problem.
error
Missing the importance of minimizing operations, focusing too much on iteration rather than arithmetic steps.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the array contains only zeros?
arrow_right_alt
How would the solution change if elements could be multiplied or divided instead of added/subtracted?
arrow_right_alt
What happens if the array contains negative numbers?

help

常见问题

外企场景

继续练习

#3179 K 秒后第 N 个元素的值 #3153 所有数对中数位差之和 #3232 判断是否可以赢得数字游戏