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:
Example 2:
Input: nums = [3,6,9]
Output: 0
Constraints:
1 <= nums.length <= 501 <= nums[i] <= 50Problem Overview: You get an integer array. In one operation you can increment or decrement any element by 1. The goal is to make every value divisible by 3 using the minimum number of operations.
The key observation: divisibility by 3 depends only on the remainder when dividing by 3. If num % 3 == 0, the element already satisfies the requirement. If the remainder is 1 or 2, you adjust the number by the shortest distance to the nearest multiple of 3.
Approach 1: Modulo and Adjustment (O(n) time, O(1) space)
Iterate through the array and compute r = num % 3. If r == 0, no operation is required. If r == 1, you can subtract 1 to reach the previous multiple of 3. If r == 2, you can add 1 to reach the next multiple of 3. Each non‑zero remainder therefore costs exactly one operation. Accumulate the number of such adjustments while scanning the array once.
This works because multiples of 3 are spaced exactly three units apart. Any number with remainder 1 or 2 is always one step away from some valid multiple. The algorithm uses simple arithmetic and a single pass over the array, which keeps the implementation clean and efficient. Since only a few integer variables are used, the extra space remains constant.
Approach 2: Array to Direct Count (O(n) time, O(1) space)
This approach focuses purely on counting remainders. Traverse the array and classify each element by num % 3. Maintain counters for remainder 1 and remainder 2. Each occurrence contributes one operation because you either decrement a remainder‑1 number or increment a remainder‑2 number.
After processing the entire array, the total operations equal count1 + count2. The logic is slightly more explicit than the previous approach and can be helpful when reasoning about groups of elements rather than individual transformations.
Both approaches rely on modular arithmetic and sequential iteration, common techniques when working with array problems that involve divisibility or remainder patterns in math-based logic.
Recommended for interviews: The modulo adjustment approach. It shows you immediately recognized the remainder pattern and converted the problem into a simple linear scan with constant space. The counting variant demonstrates the same insight but is slightly more verbose. Interviewers typically expect the O(n) pass using num % 3.
This approach involves iterating through the array and checking the remainder when each element is divided by 3.
Count these operations and sum them up to get the total minimum operations required.
The solution loops through each number, checks its remainder when divided by 3, and adjusts the operation count based on whether the remainder is 1 or 2. The function returns the sum of all adjustments needed.
Time Complexity: O(n) where n is the number of elements in nums.
Space Complexity: O(1) as we are using a constant amount of space.
This approach counts how many numbers in the array have remainders of 1 or 2, thus directly determining the operations needed without checking each element individually in a loop, leveraging the properties of remainders.
Keep count of numbers with remainders 1 and 2, which directly translates to required operations.
Time Complexity: O(n)
Space Complexity: O(1)
We directly iterate through the array nums. For each element x, if x bmod 3 neq 0, there are two cases:
x bmod 3 = 1, we can decrease x by 1 to make it x - 1, which is divisible by 3.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 nums. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Modulo and Adjustment | Time Complexity: O(n) where n is the number of elements in nums. |
| Approach 2: Array to Direct Count | Time Complexity: O(n) |
| Counting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Modulo and Adjustment | O(n) | O(1) | General solution. Best when you directly compute remainder and adjust each value. |
| Array to Direct Count | O(n) | O(1) | Useful when reasoning about remainder groups or counting transformations. |
Find Minimum Operations to Make All Elements Divisible by Three - Leetcode 3190 - Python • NeetCodeIO • 4,180 views views
Watch 9 more video solutions →Practice Find Minimum Operations to Make All Elements Divisible by Three with our built-in code editor and test cases.
Practice on FleetCode