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] <= 50To solve #3190 Find Minimum Operations to Make All Elements Divisible by Three, observe how divisibility by 3 depends on the remainder of each number when divided by 3. Instead of trying multiple operations blindly, you can evaluate how far each element is from the nearest multiple of three.
For every element in the array, compute its remainder = value % 3. If the remainder is 0, the number is already divisible by three and requires no operation. Otherwise, determine the minimum number of single-step adjustments needed to convert it to the closest multiple of three. This converts the problem into a simple arithmetic check for each element.
By iterating through the array once and summing the minimal adjustments, you can efficiently compute the total number of operations required. Since each element is processed independently, the approach runs in linear time and uses constant extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Remainder-based arithmetic check for each element | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
If <code>x % 3 != 0</code> we can always increment or decrement <code>x</code> such that we only need 1 operation.
Add <code>min(nums[i] % 3, 3 - (num[i] % 3))</code> to the count of operations.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Modulo 3 reveals how far a number is from being divisible by three. A remainder of 0 means the number already satisfies the condition, while other remainders indicate how many minimal adjustments are needed to reach the nearest multiple.
Easy array and math problems like this are common in coding interviews because they test understanding of modulo arithmetic and basic iteration. While the exact question may vary, the underlying concept often appears in technical screening rounds.
The problem mainly relies on simple array traversal. No advanced data structures are required because each element can be evaluated independently using basic arithmetic operations.
The optimal approach is to analyze each number using modulo arithmetic. By computing the remainder when dividing by 3, you can determine how many small adjustments are needed to reach the nearest multiple of three. Summing these adjustments across the array gives the total operations.