Find Minimum Operations to Make All Elements Divisible by Three
EasyPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach leverages Java's Stream API to provide a concise, functional solution. The core logic remains the same: count the number of elements not divisible by 3. We create a stream from the input array, filter it to keep only the numbers that require an operation, and then count the size of the resulting stream.
Algorithm
- Convert the input array
numsinto anIntStreamusingArrays.stream(nums). - Apply the
filter()operation to the stream. The predicatenum -> num % 3 != 0keeps only the elements that are not divisible by 3. - Apply the
count()terminal operation, which returns the number of elements in the filtered stream as along. - Cast the
longresult to anintand return it.
Walkthrough
This method provides a modern, declarative way to solve the problem. Instead of explicitly managing a loop and a counter, we describe the sequence of operations to be performed on the collection of data.
For each number n in nums, the minimum operations to make it divisible by 3 is 1 if n % 3 != 0, and 0 otherwise. The total operations is the sum of these individual minimums, which is equivalent to counting how many numbers are not divisible by 3. The Stream API is well-suited for this kind of filter-and-count logic.
import java.util.Arrays; class Solution { public int minimumOperations(int[] nums) { return (int) Arrays.stream(nums) .filter(num -> num % 3 != 0) .count(); }}Complexity
Time
O(N), where N is the number of elements in `nums`. The stream pipeline processes each element once.
Space
O(1). The stream operations in this pipeline (filter and count) are typically fused and do not require intermediate storage proportional to the input size.
Trade-offs
Pros
Concise and highly readable for those familiar with functional programming.
Reduces boilerplate code compared to an explicit loop.
Cons
May introduce a small performance overhead compared to a traditional for-loop, especially for small arrays.
Can be slightly less intuitive for developers not accustomed to Java Streams.
This is the most direct and efficient approach. We iterate through the array a single time, keeping a running count of the required operations. The logic is based on the observation that any number not divisible by 3 requires exactly one operation (either adding or subtracting 1) to reach the nearest multiple of 3.
Algorithm
- Initialize an integer counter,
operations, to zero. - Use an enhanced for-loop to iterate through each
numin thenumsarray. - Inside the loop, calculate the remainder of
numwhen divided by 3 (num % 3). - If the remainder is not 0, it means an operation is required for this number, so increment the
operationscounter. - After the loop finishes, return the final
operationscount.
Walkthrough
This fundamental approach directly implements the logic by manually iterating through the array. It is highly efficient as it avoids the overhead associated with creating and managing streams.
The key insight is that for any number n:
- If
n % 3 == 0, 0 operations are needed. - If
n % 3 == 1, 1 operation (subtract 1) is needed. - If
n % 3 == 2, 1 operation (add 1) is needed. Therefore, we just need to count how many numbers have a non-zero remainder when divided by 3.
class Solution { public int minimumOperations(int[] nums) { int operations = 0; for (int num : nums) { if (num % 3 != 0) { operations++; } } return operations; }}A slightly more verbose but equivalent way to write the condition inside the loop is to check the remainder explicitly:
class Solution { public int minimumOperations(int[] nums) { int operations = 0; for (int num : nums) { int remainder = num % 3; if (remainder == 1 || remainder == 2) { operations++; } } return operations; }}Both implementations are equally efficient.
Complexity
Time
O(N), where N is the length of the `nums` array. We perform a single pass over the array.
Space
O(1). We only use a single integer variable for the counter, requiring constant extra space.
Trade-offs
Pros
Maximum performance with minimal overhead.
Simple, straightforward, and easy for any developer to understand.
Cons
Slightly more verbose than the stream-based approach.
Solutions
Solution
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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.