#3190

Easy

LeetCode Problem Workspace

Find Minimum Operations to Make All Elements Divisible by Three

Find the minimum number of operations to make all elements in an array divisible by three.

Problem Statement

You are given an integer array nums. In each operation, you can add or subtract 1 from any element of the array. Your goal is to find the minimum number of operations needed to make all elements divisible by 3.

Return the minimum number of operations to make all elements in nums divisible by 3. For example, for the array nums = [1,2,3,4], you need 3 operations to make all elements divisible by 3.

Examples

Example 1

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

Output: 3

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

Example 2

Input: nums = [3,6,9]

Output: 0

Example details omitted.

Constraints

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

Solution Approach

Modulo Operation Insight

The key insight is to check the remainder when each number is divided by 3. If the remainder is 1, one subtraction will make the number divisible by 3, and similarly for remainder 2, one addition will suffice. Count the number of operations required for all elements based on their mod 3 results.

Count Modulo Results

First, classify each element in the array by its remainder when divided by 3. For each element, you will either subtract 1 or add 1 depending on whether the remainder is 1 or 2. Sum these operations for all elements to find the total number of steps needed.

Edge Case Handling

If all elements are already divisible by 3, no operations are needed. Handle this edge case by first checking if any number requires modification before proceeding with the counting of operations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n), where n is the length of the input array nums, as we are iterating over each element once to compute the remainder. The space complexity is O(1), since we only need a few variables to store remainders and operation counts.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Counting

We directly iterate through the array $\textit{nums}$. For each element $x$, if $x \bmod 3 \neq 0$, there are two cases:

1

2

3

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

Continue Practicing

#3179 find the n th value after k seconds #3153 sum of digit differences of all pairs #3232 find if digit game can be won