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

Problem 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.

Intuition

To solve this problem, our goal is to make each element in the array nums divisible by 3 with the smallest number of operations. For each element x in the array, we first compute the modulus x % 3, which gives us the remainder when x is divided by 3.

If the result of x % 3 is 0, the number is already divisible by 3, and no operations are needed. Otherwise, we have two options to make x divisible by 3:

Decrease x by x % 3. This removes the remainder and makes x divisible by 3.
Increase x by 3 - (x % 3). This increment will bridge the gap needed to reach the next multiple of 3.

The minimum number of operations needed is the smaller of these two options. We accumulate these operations for each element in the array, resulting in the total minimum number of operations needed to make all elements of nums divisible by 3.

Learn more about Math patterns.

Solution Approach

The solution is implemented using a simple iteration through the array nums, making use of mathematical properties of division by 3. Here's the breakdown:

Initialize a variable ans to store the total number of operations needed.
Iterate through each element x in the array nums.
For each element, calculate the remainder when divided by 3 using the expression x % 3.
- If x % 3 results in a non-zero value, it indicates that x is not divisible by 3, and operations are needed.
Calculate two possible operations to make x divisible by 3:
- Decrease x by x % 3: This requires x % 3 operations.
- Increase x by 3 - (x % 3): This requires 3 - (x % 3) operations.
The minimum of the two operations (min(x % 3, 3 - (x % 3))) is added to ans.
After processing all elements, ans contains the minimum number of operations required.

The solution code:

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

This approach leverages the mathematical properties of modular arithmetic to efficiently compute the minimal number of operations needed.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach. Consider the array nums = [4, 7, 9].

Initial Setup:
- Start with ans = 0 to keep track of the total operations needed.
Process each element:
- Element: 4
  - Calculate the remainder when divided by 3: 4 % 3 = 1.
  - Possible operations:
    1. Decrease 4 by 1 (as 4 % 3 = 1): The result is 3, a multiple of 3. Operations needed: 1.
    2. Increase 4 by 2 (as 3 - (4 % 3) = 2): The result is 6, another multiple of 3. Operations needed: 2.
  - Minimum operations: min(1, 2) = 1.
  - Update ans: ans += 1 resulting in ans = 1.
- Element: 7
  - Calculate the remainder: 7 % 3 = 1.
  - Possible operations:
    1. Decrease 7 by 1: The result is 6. Operations needed: 1.
    2. Increase 7 by 2: The result is 9. Operations needed: 2.
  - Minimum operations: min(1, 2) = 1.
  - Update ans: ans += 1 resulting in ans = 2.
- Element: 9
  - Calculate the remainder: 9 % 3 = 0.
  - Number is already divisible by 3, so no operations needed.
Final Result:
- The minimum number of operations needed to make all elements of nums divisible by 3 is ans = 2.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minimumOperations(self, nums: List[int]) -> int:
5        # Initialize a counter for operations needed
6        operations_count = 0
7      
8        # Iterate over each number in the input list
9        for number in nums:
10            # Calculate the remainder when dividing the number by 3
11            modulo_result = number % 3
12          
13            # If the remainder is not zero, we need to adjust the number
14            if modulo_result:
15                # Increment the operation count by the minimum of the 
16                # remainder or the difference to the next multiple of 3
17                operations_count += min(modulo_result, 3 - modulo_result)
18      
19        # Return the total number of operations needed
20        return operations_count
21

1class Solution {
2    public int minimumOperations(int[] nums) {
3        int totalOperations = 0; // Initialize a counter for the minimum operations required
4
5        // Iterate through each number in the array
6        for (int number : nums) {
7            int remainder = number % 3; // Compute the remainder of the division by 3
8
9            // If the number is not divisible by 3, calculate the minimum steps to make it divisible
10            if (remainder != 0) {
11                // Add the minimum operations needed (either subtract `remainder` or add `(3 - remainder)`)
12                totalOperations += Math.min(remainder, 3 - remainder);
13            }
14        }
15      
16        return totalOperations; // Return the total minimum operations needed
17    }
18}
19

1#include <vector>
2#include <algorithm> // For std::min
3
4class Solution {
5public:
6    // This function calculates the minimum operations needed to make
7    // each element in the array divisible by 3.
8    int minimumOperations(std::vector<int>& nums) {
9        int operations = 0;
10      
11        // Iterate over each element in the nums vector
12        for (int number : nums) {
13            int remainder = number % 3; // Calculate the remainder when divided by 3
14          
15            // If remainder is not zero, calculate the minimum operations
16            // needed to make this number divisible by 3.
17            if (remainder != 0) {
18                operations += std::min(remainder, 3 - remainder);
19            }
20        }
21      
22        return operations; // Return the total number of operations
23    }
24};
25

1function minimumOperations(nums: number[]): number {
2    // Initialize a counter for the minimum operations needed
3    let ans = 0;
4
5    // Iterate through each number in the given array
6    for (const num of nums) {
7        // Calculate the modulo of the current number by 3
8        const mod = num % 3;
9
10        // If the modulo is not zero, we need an operation
11        if (mod !== 0) {
12            // Increment ans by the minimum of mod and 3 - mod
13            // This calculates the minimal steps to make the number divisible by 3
14            ans += Math.min(mod, 3 - mod);
15        }
16    }
17  
18    // Return the total number of operations needed
19    return ans;
20}
21

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the array nums. This is because the code iterates through each element in nums exactly once, performing a constant amount of work (calculations and condition checks) for each element.

The space complexity is O(1) because the code only uses a fixed amount of extra space regardless of the size of the input list nums. The variables ans and mod do not require additional space that scales with the input size.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don’t know