2455. Average Value of Even Numbers That Are Divisible by Three

EasyArrayMath
Leetcode Link

Problem Description

The problem provides an array of positive integers nums and requires us to calculate the average value of all even integers in the array that are also divisible by 3. To satisfy both conditions, an integer must be divisible by 2 and 3, which ultimately means it must be divisible by 6 (since 2 * 3 = 6). The average is calculated by taking the sum of these integers and dividing by their quantity, with the result being rounded down to the nearest integer.

Intuition

To solve this problem, we need to iterate over each integer in the nums array and check if it meets the criteria of being divisible by 6. This check is performed using the modulus operator % - if x % 6 == 0, then the integer x is divisible by 6. For every integer that complies, we add its value to a running sum s and increment a count n. Afterwards, we calculate the average by dividing s by n with integer division to ensure the result is rounded down. If no integers satisfy the condition (which means n is 0), we return 0 as there's nothing to average.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Solution Approach

The implementation of the solution follows a straightforward approach, utilizing a simple loop to iterate over the elements of the array nums and conditional statements to filter out the required integers. Here are the main components of the solution:

  1. Initialization: Two variables are used to store the cumulative sum s of integers satisfying the condition and the count n of such integers.

    • s = 0 initializes the sum to zero.
    • n = 0 initializes the count to zero.

  2. Looping through the array: A for loop iterates over each integer x in the array nums.

  3. Condition check: Inside the loop, an if statement checks whether the current integer x is divisible by 6 using the modulus operation x % 6 == 0.

  4. Updating sum and count: If an integer x satisfies the condition (is divisible by 6), its value is added to the sum s (s += x), and the count n is incremented by 1 (n += 1).

  5. Calculating the average: After the loop, the average is calculated by dividing the sum s by the count n using integer division s // n, which automatically rounds down the result to the nearest integer.

  6. Edge case handling: If no integer met the condition (n == 0), the function returns 0 to avoid division by zero.

The algorithm does not use additional data structures; it only requires a fixed amount of extra space for the sum and count variables, regardless of the input size, making it an O(1) space complexity solution. In terms of time complexity, since it requires a single pass through the array, it operates at O(n), where n is the number of elements in nums.

No particular patterns or advanced algorithms are used; the solution leverages basic arithmetic operations, conditional logic, and a single loop—common constructs for most straightforward array processing tasks in algorithmic problems.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Example Walkthrough

Let's consider an example nums array: [12, 18, 5, 6, 7].

  1. Initialization: Begin by initializing the sum s and count n to 0. At this point, s = 0, n = 0.

  2. Looping through the array:

    • First integer: 12
    • Second integer: 18
    • Third integer: 5
    • Fourth integer: 6
    • Fifth integer: 7

    We will now iterate over each one and perform the necessary checks and operations.

  3. Condition check and updating sum and count:

    • First integer 12: it is divisible by 6, so we add it to the sum and increment the count. Now s = 12 and n = 1.
    • Second integer 18: this is also divisible by 6, hence it is added to the sum and count is incremented. Now s = 30 (12 + 18) and n = 2.
    • Third integer 5: this is not divisible by 6, so no changes are made. The values remain s = 30 and n = 2.
    • Fourth integer 6: it is divisible by 6, so we include it in our sum and increment the count. The updated values become s = 36 (30 + 6) and n = 3.
    • Fifth integer 7: it is not divisible by 6, so no changes are made. We end with s = 36 and n = 3.

  4. Calculating the average: With the final sum being 36 and the count being 3, we divide s by n using integer division to calculate the average: average = s // n = 36 // 3 = 12.

  5. Edge case handling: There is no need for edge case handling in this example, as we have integers that meet the condition.

For this array [12, 18, 5, 6, 7], the average value of all even integers that are also divisible by 3 is 12.

Solution Implementation

1class Solution:
2    def averageValue(self, nums: List[int]) -> int:
3        """
4        This method calculates the average of the numbers in the given list
5        that are divisible by 6. It returns an integer value.
6      
7        :param nums: List[int] - A list of integers
8        :return: The average value as an integer or 0 if no element is divisible by 6
9        """
10      
11        # Initialize the sum and count of numbers divisible by 6
12        total_sum = total_count = 0
13      
14        # Iterate over each number in the list
15        for number in nums:
16            # If the number is divisible by 6
17            if number % 6 == 0:
18                total_sum += number
19                total_count += 1
20      
21        # Calculate average if at least one number is divisible by 6; otherwise, return 0
22        return 0 if total_count == 0 else total_sum // total_count
23
1class Solution {
2    public int averageValue(int[] nums) {
3        int sum = 0; // Initialize sum to store the sum of numbers divisible by 6
4        int count = 0; // Initialize count to store the number of numbers divisible by 6
5      
6        // Iterate over each number in the array
7        for (int number : nums) {
8            // Check if the number is divisible by 6
9            if (number % 6 == 0) {
10                sum += number; // Add the number to the sum
11                ++count; // Increment the count of numbers divisible by 6
12            }
13        }
14        // If count is zero, return 0 as we cannot divide by zero
15        // Otherwise, return the average of the numbers divisible by 6
16        return count == 0 ? 0 : sum / count;
17    }
18}
19
1#include <vector> // Include the vector header for using std::vector
2
3// Solution class that contains the method to calculate the average value.
4class Solution {
5public:
6    // Method to calculate the average of numbers that are divisible by 6 in the vector.
7    int averageValue(std::vector<int>& nums) {
8        int sum = 0; // Variable to hold the sum of numbers divisible by 6.
9        int count = 0; // Variable to count numbers divisible by 6.
10
11        // Loop through all numbers in the input vector.
12        for (int number : nums) {
13            // Check if the number is divisible by 6.
14            if (number % 6 == 0) {
15                sum += number; // Add the number to the sum.
16                ++count; // Increment the count of numbers divisible by 6.
17            }
18        }
19
20        // If no number is divisible by 6, return 0 as the average.
21        if (count == 0) {
22            return 0;
23        }
24
25        // Calculate and return the average of numbers divisible by 6.
26        return sum / count;
27    }
28};
29
1/**
2 * Calculates the average of all numbers divisible by 6 in an array.
3 * Returns 0 if there are no such numbers.
4 *
5 * @param {number[]} numbers - An array of numbers to calculate the average from.
6 * @returns {number}
7 */
8function averageValue(numbers: number[]): number {
9    // Initialize the sum of numbers divisible by 6
10    let sum = 0;
11    // Initialize the count of numbers divisible by 6
12    let count = 0;
13  
14    // Iterate over all numbers in the input array
15    for (const num of numbers) {
16        // Check if number is divisible by 6
17        if (num % 6 === 0) {
18            // Add to the sum
19            sum += num;
20            // Increment the count
21            ++count;
22        }
23    }
24  
25    // If there are no numbers divisible by 6, return 0
26    if (count === 0) return 0;
27  
28    // Calculate the floor of the average value to return an integer result
29    // `~~` is a double bitwise NOT operator which is a quicker substitute for `Math.floor`
30    return ~~(sum / count);
31}
32
Not Sure What to Study? Take the 2-min Quiz：

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Time and Space Complexity

The given Python code iterates through the list nums exactly once. During this iteration, it performs a constant-time operation to check if an element is divisible by 6, and if so, it adds its value to s and increments n by 1. Therefore, the time complexity is linear with respect to the number of elements in the list. In big-O notation, this is O(n) where n is the length of nums.

The space complexity is the amount of extra space or temporary storage that the algorithm uses beyond what is necessary for the input. In this case, the function maintains a fixed number of variables (s and n) regardless of the input size. As a result, the space complexity is constant, denoted as O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following shows the order of node visit in a Breadth-first Search?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫