Skip to content

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 <= 50
  • 1 <= nums[i] <= 50

Solutions

Solution 1: Counting

We directly iterate through the array \(\textit{nums}\). For each element \(x\), if \(x \bmod 3 \neq 0\), there are two cases:

  • If \(x \bmod 3 = 1\), we can decrease \(x\) by \(1\) to make it \(x - 1\), which is divisible by \(3\).
  • If \(x \bmod 3 = 2\), we can increase \(x\) by \(1\) to make it \(x + 1\), which is divisible by \(3\).

Therefore, we only need to count the number of elements in the array that are not divisible by \(3\) to get the minimum number of operations.

The time complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums}\). The space complexity is \(O(1)\).

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

1
2
3
4
5
6
7
8
9
class Solution {
    public int minimumOperations(int[] nums) {
        int ans = 0;
        for (int x : nums) {
            ans += x % 3 != 0 ? 1 : 0;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int ans = 0;
        for (int x : nums) {
            ans += x % 3 != 0 ? 1 : 0;
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
func minimumOperations(nums []int) (ans int) {
    for _, x := range nums {
        if x%3 != 0 {
            ans++
        }
    }
    return
}

1
2
3
function minimumOperations(nums: number[]): number {
    return nums.reduce((acc, x) => acc + (x % 3 !== 0 ? 1 : 0), 0);
}

1
2
3
4
5
impl Solution {
    pub fn minimum_operations(nums: Vec<i32>) -> i32 {
        nums.iter().filter(|&&x| x % 3 != 0).count() as i32
    }
}

Comments