Leetcode 3190: Find Minimum Operations to Make All Elements Divisible by Three
You are given an array of integers
nums. In each operation, you can either add or subtract 1 from any element in nums. Your task is to determine the minimum number of operations required to make all elements of nums divisible by 3.Problem
Approach
Steps
Complexity
Input: The input consists of an integer array `nums` containing `n` elements.
Example: Example 1:
Input: nums = [2, 5, 8, 11]
Output: 6
Explanation: You need 6 operations to make each number divisible by 3: subtract 1 from 2, subtract 1 from 5, subtract 1 from 8, and subtract 1 from 11.
Constraints:
• 1 <= nums.length <= 50
• 1 <= nums[i] <= 50
Output: Return the minimum number of operations to make all elements of `nums` divisible by 3.
Example: Example 2:
Input: nums = [3, 6, 9]
Output: 0
Explanation: All numbers are already divisible by 3, so no operations are needed.
Constraints:
• The result is a non-negative integer.
Goal: To find the minimum number of operations to make each number divisible by 3.
Steps:
• For each element in the array, calculate the remainder when divided by 3 (i.e., `num % 3`).
• If the remainder is 1, one operation is needed to either add or subtract 1 to make the number divisible by 3.
• If the remainder is 2, two operations are needed (either subtract 2 or add 1).
• Sum all the operations for the entire array and return the total.
Goal: The input array will always contain integers between 1 and 50, inclusive, and the length of the array will not exceed 50.
Steps:
• 1 <= nums.length <= 50
• 1 <= nums[i] <= 50
Assumptions:
• All array elements are between 1 and 50.
• The minimum number of operations will be calculated based on how much each element deviates from being divisible by 3.
• Input: Example 1:
• Explanation: For `nums = [2, 5, 8, 11]`, the remainders when divided by 3 are [2, 2, 2, 2]. Each element needs 2 operations (subtracting 1) to become divisible by 3. Therefore, the total number of operations is 2 + 2 + 2 + 2 = 8.
• Input: Example 2:
• Explanation: For `nums = [3, 6, 9]`, all elements are already divisible by 3. Thus, no operations are needed, and the result is 0.
Approach: The solution can be efficiently implemented by iterating through the array, calculating the remainder of each element when divided by 3, and applying the necessary number of operations based on the remainder.
Observations:
• The remainder of each number when divided by 3 determines how many operations are required to make it divisible by 3.
• A straightforward approach will be to iterate over the array, sum up the required operations for each number, and return the total.
Steps:
• Iterate through each element of the array `nums`.
• For each element, calculate its remainder when divided by 3.
• If the remainder is 1, add 1 to the operation count.
• If the remainder is 2, add 2 to the operation count.
• Return the total operation count.
Empty Inputs:
• There are no empty inputs in this problem, as `nums.length >= 1`.
Large Inputs:
• The approach should handle the maximum input size efficiently.
Special Values:
• When all elements are already divisible by 3 (i.e., when `nums[i] % 3 == 0`), no operations are needed.
Constraints:
• The solution must work for arrays of size up to 50 and for numbers between 1 and 50.
int minimumOperations(vector<int>& nums) {
int ans = 0;
for(int i=0;i<nums.size();i++) ans+=min(3-(nums[i]%3),nums[i]%3);
return ans;
}
1 : Function Definition
int minimumOperations(vector<int>& nums) {
The function `minimumOperations` is defined, taking a reference to a vector of integers `nums` as its parameter.
2 : Variable Initialization
int ans = 0;
The variable `ans` is initialized to `0` to store the total number of operations.
3 : Loop Start
for(int i=0;i<nums.size();i++) ans+=min(3-(nums[i]%3),nums[i]%3);
A loop iterates over the elements of `nums`. For each element, the number of operations required to make it divisible by 3 is calculated and added to `ans`. The minimum between adding the difference to 3 or subtracting the element's remainder when divided by 3 is considered.
4 : Return Statement
return ans;
The function returns the total number of operations stored in `ans`.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the length of the array `nums`. We perform a constant-time operation for each element in the array.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1), as we only need a few variables to track the total number of operations.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus