Problem

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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

1
2
3
4


Input: nums = [3,6,9]

Output: 0

Constraints

  • 1 <= nums.length <= 50
  • 1 <= nums[i] <= 50

Solution

Method 1 – Greedy Modulo Operations

Intuition

For each number, the minimum number of operations to make it divisible by 3 is the minimum of its remainder and (3 - remainder). Summing this for all numbers gives the answer.

Approach

  1. For each number in nums, compute rem = num % 3.
  2. For each, add min(rem, 3 - rem) to the total operations.
  3. Return the total sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int ans = 0;
        for (int n : nums) {
            int r = n % 3;
            ans += min(r, 3 - r);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func minOperations(nums []int) int {
    ans := 0
    for _, n := range nums {
        r := n % 3
        if r < 3 - r {
            ans += r
        } else {
            ans += 3 - r
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int minOperations(int[] nums) {
        int ans = 0;
        for (int n : nums) {
            int r = n % 3;
            ans += Math.min(r, 3 - r);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun minOperations(nums: IntArray): Int {
        var ans = 0
        for (n in nums) {
            val r = n % 3
            ans += minOf(r, 3 - r)
        }
        return ans
    }
}
1
2
3
4
5
6
7

class Solution:
    def minOperations(self, nums: list[int]) -> int:
        ans = 0
        for n in nums:
            r = n % 3
            ans += min(r, 3 - r)
        return ans
1
2
3
4
5
6
7
8

impl Solution {
    pub fn min_operations(nums: Vec<i32>) -> i32 {
        nums.into_iter().map(|n| {
            let r = n % 3;
            r.min(3 - r)
        }).sum()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    minOperations(nums: number[]): number {
        let ans = 0;
        for (const n of nums) {
            const r = n % 3;
            ans += Math.min(r, 3 - r);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. Each number is processed once.
  • 🧺 Space complexity: O(1), only a constant number of variables are used.