Watch 10 video solutions for Average Value of Even Numbers That Are Divisible by Three, a easy level problem involving Array, Math. This walkthrough by Mastering Programming has 4,897 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer array nums of positive integers, return the average value of all even integers that are divisible by 3.
Note that the average of n elements is the sum of the n elements divided by n and rounded down to the nearest integer.
Example 1:
Input: nums = [1,3,6,10,12,15] Output: 9 Explanation: 6 and 12 are even numbers that are divisible by 3. (6 + 12) / 2 = 9.
Example 2:
Input: nums = [1,2,4,7,10] Output: 0 Explanation: There is no single number that satisfies the requirement, so return 0.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 1000Problem Overview: Given an integer array, compute the average of values that are both even and divisible by three. If no such numbers exist, return 0. The task reduces to filtering numbers divisible by 6, tracking their sum and count, then returning sum / count.
Approach 1: Recursive Approach with Memoization (O(n) time, O(n) space)
This approach processes the array using recursion. At each index, check whether the current value is divisible by 6. If it is, update the running sum and count. The recursive function moves to the next index until the end of the array. Memoization stores intermediate states such as (index) to avoid recomputation if the recursion revisits the same position.
The key idea is breaking the problem into smaller subproblems: compute the valid sum and count from the remaining suffix of the array. After recursion finishes, calculate the average using the aggregated values. Time complexity is O(n) since each element is processed once, while recursion and memo storage require O(n) space. This method demonstrates recursive problem decomposition on array traversal.
Approach 2: Iterative Dynamic Programming Approach (O(n) time, O(1) space)
The optimal solution uses a single pass through the array. Maintain two variables: sum for the total of qualifying numbers and count for how many satisfy the condition. During iteration, check num % 6 == 0. This works because a number divisible by both 2 and 3 must be divisible by 6.
Each valid number updates sum += num and count++. After finishing the loop, return sum / count if count > 0; otherwise return 0. This approach leverages basic properties of math and linear scanning of an array. Since only two variables are maintained, space complexity remains constant at O(1) while time complexity is O(n).
Recommended for interviews: The iterative single-pass solution is what interviewers expect. It demonstrates that you recognize the mathematical shortcut (divisible by 6) and can compute aggregates in one traversal. Mentioning the recursive variant shows understanding of alternative traversal strategies, but the constant-space iterative approach is the most practical and efficient.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Approach with Memoization | O(n) | O(n) | Useful for practicing recursive array traversal or when extending the problem to more complex state tracking |
| Iterative Dynamic Programming (Single Pass) | O(n) | O(1) | Best general solution; minimal memory and fastest implementation for scanning arrays |