Average Value of Even Numbers That Are Divisible by Three

Easy

#2239Time: O(N), where N is the number of elements in the input array. The first pass takes O(N) time to filter the numbers. The second pass takes O(K) time, where K is the number of elements satisfying the condition (K <= N). Thus, the total time complexity is O(N) + O(K) which simplifies to O(N).Space: O(K), where K is the number of elements satisfying the condition. In the worst case, all N elements satisfy the condition, leading to a space complexity of O(N) to store the filtered numbers in a separate list.2 companies

Patterns

Math

Data structures

Array

Companies

Accenture IBM

Prompt

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 <= 1000
1 <= nums[i] <= 1000

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves two separate iterations over the data. First, we iterate through the input array to identify and collect all the numbers that are both even and divisible by three. These numbers are stored in an auxiliary data structure, like a list. In the second pass, we iterate over this new list to calculate the sum of its elements. Finally, we compute the average by dividing the total sum by the count of numbers found. If no such numbers are found, the average is 0.

Algorithm

Initialize an empty list, validNumbers, to store integers that meet the criteria.
Iterate through each num in the input array nums.
Inside the loop, check if num is even (num % 2 == 0) and divisible by 3 (num % 3 == 0). A more concise check is num % 6 == 0.
If the condition is true, add num to the validNumbers list.
After the first loop finishes, check if validNumbers is empty. If it is, return 0.
If validNumbers is not empty, initialize a sum variable to 0.
Iterate through each validNum in the validNumbers list and add it to sum.
Finally, calculate the average by dividing sum by the size of validNumbers. The integer division will handle the rounding down.

Walkthrough

This method first filters the array to find all numbers that satisfy the condition and then calculates their average.

We start by creating an empty list, let's call it validNumbers. We then loop through the input nums array. For each number, we check if it's divisible by 6 (which is equivalent to being even and divisible by 3). If it is, we add it to our validNumbers list.

After populating the list, we check if it's empty. An empty list means no numbers satisfied the condition, so we return 0. Otherwise, we proceed to calculate the sum of the elements in validNumbers by iterating through it a second time. The final average is this sum divided by the number of elements in the list.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int averageValue(int[] nums) {6        List<Integer> validNumbers = new ArrayList<>();7        for (int num : nums) {8            // A number is even and divisible by 3 if it's divisible by 6.9            if (num % 6 == 0) {10                validNumbers.add(num);11            }12        }13 14        if (validNumbers.isEmpty()) {15            return 0;16        }17 18        int sum = 0;19        for (int num : validNumbers) {20            sum += num;21        }22 23        return sum / validNumbers.size();24    }25}

Complexity

Time

O(N), where N is the number of elements in the input array. The first pass takes O(N) time to filter the numbers. The second pass takes O(K) time, where K is the number of elements satisfying the condition (K <= N). Thus, the total time complexity is O(N) + O(K) which simplifies to O(N).

Space

O(K), where K is the number of elements satisfying the condition. In the worst case, all N elements satisfy the condition, leading to a space complexity of O(N) to store the filtered numbers in a separate list.

Trade-offs

Pros

Simple to understand and implement as it separates the filtering and calculation logic.

Cons

Uses extra space to store the filtered numbers, which can be significant if many numbers meet the criteria.
Requires two passes over the data (one on the original array, one on the new list), making it less efficient than a single-pass solution.

A more efficient approach is to calculate the sum and count in a single pass through the input array. We initialize a sum and a count variable to zero. Then, we iterate through each number in the array. For each number, we check if it's both even and divisible by three. A number that satisfies both conditions must be divisible by 6. If the condition num % 6 == 0 is met, we add the number to our running sum and increment the count. After checking all numbers, we calculate the average. If the count is zero, we return 0; otherwise, we return the sum divided by the count, which performs integer division as required.

Algorithm

Initialize sum = 0 and count = 0.
For each num in the input array nums:
Check if `num` is divisible by 6 (`num % 6 == 0`).
If it is, add `num` to `sum` and increment `count`.
After the loop, check if count is 0.
If count is 0, return 0.
Otherwise, return sum / count.

Walkthrough

This optimized approach avoids using extra storage and multiple loops by processing the array in a single pass.

We initialize two integer variables: sum = 0 to keep a running total and count = 0 to track the number of valid integers. We then iterate through the input array nums just once. For each number num, we check if it's divisible by 6. This single check (num % 6 == 0) efficiently verifies if the number is both even and divisible by 3. If the condition is true, we add the number to sum and increment count.

After the loop completes, we check if count is 0. If it is, no qualifying numbers were found, so we return 0 to avoid a division-by-zero error. Otherwise, we return the result of sum / count. Since sum and count are integers, this performs integer division, which automatically rounds the result down to the nearest integer as required by the problem.

1class Solution {2    public int averageValue(int[] nums) {3        int sum = 0;4        int count = 0;5        for (int num : nums) {6            // A number is even and divisible by 3 if it's divisible by 6.7            if (num % 6 == 0) {8                sum += num;9                count++;10            }11        }12        13        // If count is 0, return 0 to avoid division by zero.14        // Otherwise, return the integer division of sum by count.15        return count == 0 ? 0 : sum / count;16    }17}

Complexity

Time

O(N), where N is the number of elements in the input array. We iterate through the array only once.

Space

O(1), as we only use a constant amount of extra space for variables like `sum` and `count`, regardless of the input size.

Trade-offs

Pros

Highly efficient in both time and space.
Requires only a single pass over the input array.
Minimal memory usage (O(1) space).

Cons

No significant cons for this problem, as it's the optimal solution.

Solutions

Solution

1class Solution {2public3  int averageValue(int[] nums) {4    int s = 0, n = 0;5    for (int x : nums) {6      if (x % 6 == 0) {7        s += x;8        ++n;9      }10    }11    return n == 0 ? 0 : s / n;12  }13}

1class Solution {2public:3  int averageValue(vector<int> &nums) {4    int s = 0, n = 0;5    for (int x : nums) {6      if (x % 6 == 0) {7        s += x;8        ++n;9      }10    }11    return n == 0 ? 0 : s / n;12  }13};

1class Solution:2    def averageValue(self, nums: List[int]) -> int: s = n = 0 for x in nums: if x % 6 == 0: s += x n += 1 return 0 if n == 0 else s // n

Video 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.

← Previous

Previous problem

Next problem