LeetCode 3190 - Find Minimum Operations to Make All Elements Divisible by Three

The problem gives us an integer array nums. In one operation, we are allowed to either increase or decrease any single element by exactly 1. Our goal is to make every number in the array divisible by 3, while using the smallest possible number of operations.

leetcodeeasyarraymath

LeetCode Problem 3190

Difficulty: 🟢 Easy
Topics: Array, Math

Solution

Problem Understanding

The problem gives us an integer array nums. In one operation, we are allowed to either increase or decrease any single element by exactly 1. Our goal is to make every number in the array divisible by 3, while using the smallest possible number of operations.

In other words, for each number, we want to determine how many +1 or -1 adjustments are needed before the number becomes a multiple of 3. Since operations on one element do not affect any other element, we can solve the problem independently for each value and sum the costs together.

The input represents a list of integers:

  • nums[i] is the current value of the i-th element.
  • We may repeatedly modify any element by adding or subtracting 1.
  • The final array must contain only values divisible by 3.

The output is a single integer representing the minimum total number of operations required.

The constraints are very small:

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

These limits tell us that performance is not a major concern. Even inefficient solutions would still run comfortably within limits. However, the problem is designed to test observation and mathematical reasoning rather than brute computational power.

There are several important edge cases to consider:

  • Arrays where every number is already divisible by 3, since the answer should be 0.
  • Numbers with remainder 1 when divided by 3, because subtracting 1 or adding 2 are both possible, but subtracting 1 is optimal.
  • Numbers with remainder 2 when divided by 3, because adding 1 or subtracting 2 are both possible, but adding 1 is optimal.
  • Arrays with only one element, where the answer depends entirely on that single value.

Because the problem guarantees all numbers are positive integers and relatively small, we do not need to worry about overflow or invalid inputs.

Approaches

Brute Force Approach

A brute force approach would try different sequences of additions and subtractions for every number until it becomes divisible by 3. For example, for a value like 4, we could explore:

  • 4 - 1 = 3
  • 4 + 1 = 5, then 5 + 1 = 6

We could use breadth first search or repeated simulation to determine the minimum number of operations for each number.

This approach is correct because it explores all possible ways to transform a number into a multiple of 3 and eventually finds the minimum distance.

However, it is unnecessarily complicated and inefficient. The divisibility rule for 3 gives us a much simpler observation. A number's remainder when divided by 3 completely determines the minimum work needed.

Key Insight

Every integer falls into one of three categories:

  • num % 3 == 0
  • num % 3 == 1
  • num % 3 == 2

If the remainder is:

  • 0, the number is already divisible by 3, so no operations are needed.
  • 1, we can subtract 1 once to reach a multiple of 3.
  • 2, we can add 1 once to reach a multiple of 3.

This means the minimum operations for each number are simply:

  • 0 if remainder is 0
  • 1 if remainder is 1
  • 1 if remainder is 2

Equivalently, the answer for each element is:

min(remainder, 3 - remainder)

Since each element can be processed independently, we simply compute the minimum operations for every number and sum them.

Approach Time Complexity Space Complexity Notes
Brute Force O(n × k) O(1) Simulates operations until divisibility is reached
Optimal O(n) O(1) Uses modulo arithmetic to compute minimum operations directly

Here, k represents the number of simulated operations per element.

Algorithm Walkthrough

  1. Initialize a variable called operations to 0.

This variable stores the running total of operations needed for the entire array. 2. Iterate through each number in nums.

Since each element can be modified independently, we process one value at a time. 3. Compute the remainder when the current number is divided by 3.

remainder = num % 3

The remainder tells us how far the number is from the nearest multiple of 3. 4. Compute the minimum operations needed for this number.

We have two possible directions:

  • Move downward by remainder
  • Move upward by 3 - remainder

So the minimum cost is:

min(remainder, 3 - remainder)
  1. Add this value to operations.

This accumulates the minimum operations across all elements. 6. After processing the entire array, return operations.

Why it works

A number's divisibility by 3 depends only on its remainder modulo 3. For every remainder, the shortest path to a multiple of 3 is either moving downward to the previous multiple or upward to the next multiple. Since operations on one element do not affect others, independently minimizing each element also minimizes the global total.

Python Solution

from typing import List

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        operations = 0
        
        for num in nums:
            remainder = num % 3
            operations += min(remainder, 3 - remainder)
        
        return operations

The implementation begins by initializing a variable called operations, which keeps track of the total number of required changes.

We then iterate through every value in nums. For each number, we compute its remainder when divided by 3 using the modulo operator.

The expression:

min(remainder, 3 - remainder)

calculates the shortest distance to a multiple of 3. If the remainder is small, subtracting is cheaper. Otherwise, adding is cheaper.

Finally, we accumulate these costs into operations and return the total after the loop completes.

The implementation directly follows the mathematical observation from the algorithm walkthrough, which keeps the code concise and efficient.

Go Solution

func minimumOperations(nums []int) int {
    operations := 0

    for _, num := range nums {
        remainder := num % 3
        
        if remainder < 3-remainder {
            operations += remainder
        } else {
            operations += 3 - remainder
        }
    }

    return operations
}

The Go implementation mirrors the Python logic closely. The main difference is that Go does not provide a built in min function for integers, so we manually compare the two values using an if statement.

The function iterates through the slice using Go's range syntax, computes the remainder for each number, and accumulates the minimum adjustment cost into operations.

There are no overflow concerns because the constraints are extremely small. The implementation also handles empty style edge behavior naturally, although the problem guarantees at least one element.

Worked Examples

Example 1

Input:

nums = [1, 2, 3, 4]

We process each element independently.

Number Remainder (num % 3) Minimum Operations Running Total
1 1 min(1, 2) = 1 1
2 2 min(2, 1) = 1 2
3 0 min(0, 3) = 0 2
4 1 min(1, 2) = 1 3

Final answer:

3

The transformations are:

  • 1 -> 0
  • 2 -> 3
  • 3 -> 3
  • 4 -> 3

Example 2

Input:

nums = [3, 6, 9]
Number Remainder (num % 3) Minimum Operations Running Total
3 0 0 0
6 0 0 0
9 0 0 0

Final answer:

0

All numbers are already divisible by 3, so no changes are needed.

Complexity Analysis

Measure Complexity Explanation
Time O(n) We scan the array once
Space O(1) Only a few variables are used

The algorithm performs constant work for each element in the array. Since there are n elements, the total running time is linear.

The space usage is constant because we only maintain a few integer variables regardless of input size.

Test Cases

from typing import List

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        operations = 0
        
        for num in nums:
            remainder = num % 3
            operations += min(remainder, 3 - remainder)
        
        return operations

sol = Solution()

assert sol.minimumOperations([1, 2, 3, 4]) == 3  # Provided example
assert sol.minimumOperations([3, 6, 9]) == 0  # Already divisible

assert sol.minimumOperations([1]) == 1  # Single element, remainder 1
assert sol.minimumOperations([2]) == 1  # Single element, remainder 2
assert sol.minimumOperations([3]) == 0  # Single element already divisible

assert sol.minimumOperations([4, 7, 10]) == 3  # All remainder 1
assert sol.minimumOperations([2, 5, 8]) == 3  # All remainder 2

assert sol.minimumOperations([1, 1, 1, 1]) == 4  # Multiple small adjustments
assert sol.minimumOperations([50]) == 1  # Largest value in constraints

assert sol.minimumOperations([12, 15, 18, 21]) == 0  # All multiples of 3
assert sol.minimumOperations([14, 17, 20]) == 3  # Mixed values requiring one operation each
Test Why
[1, 2, 3, 4] Validates the provided example
[3, 6, 9] Ensures zero operations are handled correctly
[1] Tests single value with remainder 1
[2] Tests single value with remainder 2
[3] Tests single divisible value
[4, 7, 10] Every element requires subtracting 1
[2, 5, 8] Every element requires adding 1
[1, 1, 1, 1] Repeated adjustments across multiple elements
[50] Tests upper bound value
[12, 15, 18, 21] Larger divisible values
[14, 17, 20] Mixed numbers requiring uniform cost

Edge Cases

One important edge case is when all numbers are already divisible by 3. A careless implementation might still attempt unnecessary operations or miscalculate costs. In this situation, every remainder is 0, so the formula correctly contributes zero operations for every element.

Another important case is numbers with remainder 2. A naive approach might always subtract the remainder value, which would require two operations for numbers like 2 or 5. However, adding 1 is cheaper. The implementation handles this correctly using:

min(remainder, 3 - remainder)

This guarantees the shorter path is always chosen.

A third edge case is arrays containing only a single element. Some implementations accidentally assume multiple values exist or rely on aggregate behavior. Since this solution processes elements independently in a simple loop, single element arrays work naturally without any special handling.

Finally, the maximum constraint values such as 50 should also be considered. Although the numbers are small, this confirms the modulo arithmetic works consistently across the full range of inputs. Since 50 % 3 == 2, the algorithm correctly determines that only one operation is needed.