Welcome to Subscribe On Youtube
3190. Find Minimum Operations to Make All Elements Divisible by Three
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.
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 <= 501 <= nums[i] <= 50
Solutions
Solution 1: Mathematics
We directly iterate through the array $\text{nums}$. For each element $x$, we calculate the remainder of $x$ divided by 3, $x \bmod 3$. If the remainder is not 0, we need to make $x$ divisible by 3 with the minimum number of operations. Therefore, we can choose to either decrease $x$ by $x \bmod 3$ or increase $x$ by $3 - x \bmod 3$, and we accumulate the minimum of these two values to the answer.
The time complexity is $O(n)$, where $n$ is the length of the array $\text{nums}$. The space complexity is $O(1)$.
-
class Solution { public int minimumOperations(int[] nums) { int ans = 0; for (int x : nums) { int mod = x % 3; if (mod != 0) { ans += Math.min(mod, 3 - mod); } } return ans; } } -
class Solution { public: int minimumOperations(vector<int>& nums) { int ans = 0; for (int x : nums) { int mod = x % 3; if (mod) { ans += min(mod, 3 - mod); } } return ans; } }; -
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 -
func minimumOperations(nums []int) (ans int) { for _, x := range nums { if mod := x % 3; mod > 0 { ans += min(mod, 3-mod) } } return } -
function minimumOperations(nums: number[]): number { let ans = 0; for (const x of nums) { const mod = x % 3; if (mod) { ans += Math.min(mod, 3 - mod); } } return ans; }