Difficulty: Easy | Acceptance: 90.80% | Paid: No Topics: Array, Math
You are given an integer array nums. In one operation, you can add 1 or subtract 1 from any element of nums.
Return the minimum number of operations to make all elements of nums divisible by 3.
- Examples
- Constraints
- Direct Counting
- Mathematical Formula
- Functional Programming
Examples
Example 1
Input: nums = [1,2,3,4]
Output: 3
Explanation:
- All array elements can be made divisible by 3 using 3 operations:
Subtract 1 from 1
Add 1 to 2
Subtract 1 from 4
Example 2
Input: nums = [3,6,9]
Output: 0
Constraints
1 <= nums.length <= 50
1 <= nums[i] <= 50
Direct Counting
Intuition For each element, if it’s not divisible by 3, we need exactly 1 operation (either add or subtract 1 to reach the nearest multiple of 3).
Steps
- Iterate through each element in the array
- Check if the element is divisible by 3
- If not, increment the operation count
- Return the total count
python
from typing import List
class Solution:
def minimumOperations(self, nums: List[int]) -> int:
return sum(1 for num in nums if num % 3 != 0)
Complexity
- Time: O(n) where n is the length of the array
- Space: O(1) constant extra space
- Notes: Simple and efficient approach
Mathematical Formula
Intuition The minimum operations for each element is min(remainder, 3 - remainder) where remainder is num % 3.
Steps
- Iterate through each element in the array
- Calculate the remainder when divided by 3
- Add min(remainder, 3 - remainder) to the total
- Return the total
python
from typing import List
class Solution:
def minimumOperations(self, nums: List[int]) -> int:
return sum(min(num % 3, 3 - num % 3) for num in nums)
Complexity
- Time: O(n) where n is the length of the array
- Space: O(1) constant extra space
- Notes: More mathematical formulation, same complexity as direct counting
Functional Programming
Intuition Use functional programming constructs like map, reduce, or accumulate to process the array in a declarative style.
Steps
- Use reduce/accumulate to sum up the operations needed
- For each element, add 1 if not divisible by 3, else add 0
- Return the accumulated result
python
from typing import List
from functools import reduce
class Solution:
def minimumOperations(self, nums: List[int]) -> int:
return reduce(lambda acc, num: acc + (1 if num % 3 != 0 else 0), nums, 0)
Complexity
- Time: O(n) where n is the length of the array
- Space: O(1) constant extra space
- Notes: Declarative style, may have slight overhead in some languages