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

Intuition

The problem requires making all elements of the array divisible by 3 using the minimum number of operations. Each operation allows us to either add or subtract 1 from any element, making it possible to adjust elements until they become divisible by 3.

The key insight is to recognize that any integer can be one of three possible remainders when divided by 3: 0, 1, or 2. The goal is to convert every element of the array such that it has a remainder of 0 when divided by 3. This can be achieved by:

• Subtracting 1 from elements with remainder 1 (1 operation).
• Adding 1 to elements with remainder 2 (1 operation).

Approach

1. Initialize a counter operations to count the total number of operations required.
2. Iterate through each element in the array: - If the element's remainder when divided by 3 is 1, increment the operations counter by 1 (since subtracting 1 will make it divisible by 3). - If the element's remainder when divided by 3 is 2, increment the operations counter by 1 (since adding 1 will make it divisible by 3).
3. Return the total count of operations.

This approach ensures that we handle each element independently, adjusting it to meet the requirement efficiently.

Complexity

• Time Complexity: O(n) We iterate through the array once, performing a constant-time operation for each element.
• Space Complexity: O(1) The algorithm uses a fixed amount of extra space regardless of the input size.

Code

C++

class Solution {
public:
    int minimumOperations(std::vector& nums) {
        int count = 0;
        for (int num : nums) {
            if (num % 3 != 0) {
                count++;
            }
        }
        return count;
    }
};

Python

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

Java

cpublic class Solution {
    public int minimumOperations(int[] nums) {
        int count = 0;
        for (int num : nums) {
            if (num % 3 != 0) {
                count++;
            }
        }
        return count;
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumOperations = function (nums) {
  return nums.reduce((a, b) => a + (b % 3 !== 0), 0);
};

Go

func minimumOperations(nums []int) int {
    count := 0
    for _, num := range nums {
        if num % 3 != 0 {
            count++
        }
    }
    return count
}

C#

public class Solution {
    public int MinimumOperations(int[] nums) {
        int count = 0;
        foreach (int num in nums) {
            if (num % 3 != 0) {
                count++;
            }
        }
        return count;
    }
}