LeetCode 2455 - Average Value of Even Numbers That Are Divisible by Three

The problem asks us to calculate the average of all integers in an array nums that satisfy two conditions simultaneously: they must be even and divisible by 3.

leetcodeeasyarraymath

LeetCode Problem 2455

Difficulty: 🟢 Easy
Topics: Array, Math

Solution

Problem Understanding

The problem asks us to calculate the average of all integers in an array nums that satisfy two conditions simultaneously: they must be even and divisible by 3. In other words, we only consider numbers that are multiples of 6, because a number divisible by both 2 and 3 is divisible by 6.

The input is a list of positive integers with length ranging from 1 to 1000, and each integer is between 1 and 1000. The output is a single integer representing the average of the selected numbers, rounded down to the nearest integer using floor division. If there are no numbers meeting the criteria, we return 0.

Key points from the constraints:

  • The array is relatively small (nums.length <= 1000), so even a simple linear scan will be efficient.
  • All numbers are positive, so we do not need to handle negative numbers or zeros.
  • There is a possibility that no number meets the criteria, which is an important edge case.

Potential edge cases:

  • An array where no numbers are even and divisible by 3 (should return 0).
  • An array where all numbers meet the condition.
  • An array with a single element that meets or does not meet the condition.

Approaches

The brute-force approach is straightforward: iterate through the array, check each number for being even and divisible by 3, sum them up, and count how many meet the criteria. At the end, divide the sum by the count, returning 0 if the count is zero. This is simple and efficient enough given the constraints, because we only have to make a single pass over at most 1000 elements.

The key observation for optimality is that there is no more efficient method than a single pass, because we must examine each number at least once to verify if it is even and divisible by 3. Thus, the brute-force approach is actually the optimal solution here.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Iterate once, sum numbers divisible by 6, count them, compute average
Optimal O(n) O(1) Same as brute-force; single pass is already optimal

Algorithm Walkthrough

  1. Initialize two variables: total_sum to 0 and count to 0. These will store the sum of numbers divisible by 6 and the number of such numbers, respectively.
  2. Iterate through each number num in the array nums.
  3. For each num, check if it is divisible by 6 (i.e., num % 6 == 0). This ensures it is both even and divisible by 3.
  4. If num satisfies the condition, add it to total_sum and increment count by 1.
  5. After iterating through the array, check if count is greater than 0. If it is, return the integer division total_sum // count. If no numbers met the criteria, return 0.

Why it works: At each step, we maintain the invariant that total_sum contains the sum of all numbers divisible by 6 encountered so far and count contains the number of such numbers. Dividing the sum by the count after iteration gives the average, correctly rounded down due to integer division.

Python Solution

from typing import List

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

Implementation walkthrough: We define two variables, total_sum and count. We loop through nums, checking if each number is divisible by 6. If so, we update our sum and count. After the loop, we use integer division to return the floored average, or 0 if no number met the criteria. This directly implements the algorithm discussed above.

Go Solution

func averageValue(nums []int) int {
    totalSum := 0
    count := 0
    for _, num := range nums {
        if num % 6 == 0 {
            totalSum += num
            count++
        }
    }
    if count == 0 {
        return 0
    }
    return totalSum / count
}

Go-specific notes: We use range to iterate over the slice nums. The integer division in Go automatically floors the result, similar to Python. Edge cases such as an empty count are handled explicitly with an if check.

Worked Examples

Example 1: nums = [1,3,6,10,12,15]

num divisible by 6? total_sum count
1 no 0 0
3 no 0 0
6 yes 6 1
10 no 6 1
12 yes 18 2
15 no 18 2

Average = 18 // 2 = 9

Example 2: nums = [1,2,4,7,10]

num divisible by 6? total_sum count
1 no 0 0
2 no 0 0
4 no 0 0
7 no 0 0
10 no 0 0

No numbers satisfy the condition, return 0

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the array of length n to check each element
Space O(1) Only two integer variables used, no additional data structures

The algorithm scales linearly with input size, and the space usage is constant, making it very efficient for the problem constraints.

Test Cases

# Provided examples
assert Solution().averageValue([1,3,6,10,12,15]) == 9  # multiple numbers divisible by 6
assert Solution().averageValue([1,2,4,7,10]) == 0       # no numbers divisible by 6

# Boundary cases
assert Solution().averageValue([6]) == 6                # single number divisible by 6
assert Solution().averageValue([1]) == 0                # single number not divisible by 6
assert Solution().averageValue([6,12,18,24]) == 15     # all numbers divisible by 6
assert Solution().averageValue([1,2,3,4,5]) == 0       # none divisible by 6
assert Solution().averageValue([6,7,8,9,12]) == 9      # mix of numbers
assert Solution().averageValue([1000]) == 0            # large number not divisible by 6
assert Solution().averageValue([996]) == 996           # large number divisible by 6
Test Why
[1,3,6,10,12,15] Multiple numbers divisible by 6; tests normal calculation
[1,2,4,7,10] No number divisible by 6; tests returning 0
[6] Single number divisible by 6; tests smallest array edge case
[1] Single number not divisible by 6; tests smallest array edge case with 0
[6,12,18,24] All numbers divisible by 6; tests average computation
[1,2,3,4,5] No numbers divisible by 6; tests larger array with 0 result
[6,7,8,9,12] Mixed array; tests selective inclusion
[1000] Large number not divisible by 6; tests handling high values
[996] Large number divisible by 6; tests handling high values

Edge Cases

  1. Empty qualifying numbers: When the array has no numbers divisible by 6, we must return 0. This is correctly handled by checking if count is 0 before division.
  2. Single-element arrays: Both cases where the single element is divisible by 6 or not are edge cases. The implementation works correctly, either returning the element itself or 0.
  3. Large numbers near 1000: The input allows numbers up to 1000, and since we sum them, we must ensure that integer overflow does not occur. In Python, integers can grow arbitrarily large, so this is safe. In Go, integer overflow is not an issue for numbers up to 1000 in a 32-bit or 64-bit int.

This solution is robust for all inputs within the problem constraints.