1295. Find Numbers with Even Number of Digits

Problem Description

The goal of this problem is to find out how many numbers in a given array nums have an even number of digits. To clarify, a number like 1234 has 4 digits, which is even, while a number like 123 has 3 digits, which is odd. So in the list [12, 123, 1234, 12345], there would be two numbers (12 and 1234) that have an even number of digits.

Intuition

The intuition behind the solution is based on understanding that the number of digits in a number can be determined by converting the number into a string and counting the length of that string. Once the number is converted to a string, it's straightforward to check if the length is even by using the modulo operator %. The modulo operation len(str(v)) % 2 will be equal to 0 for numbers with an even number of digits, as any even number divided by 2 leaves a remainder of 0.

We can iterate over each number in the array, convert it to a string, check the length, and then sum up all instances where the length modulo 2 is 0. This sum represents the count of numbers with an even number of digits because we're effectively adding 1 for each number that meets the criteria and 0 for each that does not.

Solution Approach

The solution involves a simple and efficient approach that relies on Python's list comprehension and built-in functions. Here is a breakdown of the implementation:

Iterate through each number in the input list nums with a for loop embedded in a list comprehension.
Convert each number to a string by using the str() constructor. This is because the length of a number (how many digits it has) can be easily obtained from its string representation.
Use the len() function to count the number of characters, which represent the digits, in the string.
Check if the number of digits is even by applying the % (modulus) operator to len(str(v)). If the length modulo 2 is equal to 0, it means the number has an even number of digits.
The result of this check (len(str(v)) % 2 == 0) will be either True or False. In Python, True is equivalent to the integer 1, and False is equivalent to 0.
Use sum() to add up all the True values from the list comprehension, which corresponds to counting the numbers with an even number of digits.

No additional data structures or complex algorithms are necessary for this solution, as it's a straightforward application of string conversion and arithmetic operations to check the digit count.

Here is the single line of code implementing this approach:

return sum(len(str(v)) % 2 == 0 for v in nums)

This single line performs all the above steps, elegantly returning the count of numbers with an even number of digits in the input list nums.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using a smaller example. Consider the array nums with the following numbers: [555, 8001, 22, 3].

We want to count how many of these numbers have an even number of digits.

Let's start by looking at the first number in the array, which is 555. Converting 555 to a string gives us '555', which has 3 characters. The length of this string is odd because 3 % 2 is equal to 1.
We then look at the second number, 8001. As a string, it's '8001', which has 4 characters. The length of this string is even because 4 % 2 equals 0.
Moving to the third number, 22, we convert it to a string to get '22'. This string has 2 characters, which is even since 2 % 2 equals 0.
Lastly, we have the number 3. This becomes '3' as a string, which consists of only 1 character. The length is odd here because 1 % 2 equals 1.

Now, let's apply the short line of Python code from the given solution:

return sum(len(str(v)) % 2 == 0 for v in nums)

For each number in nums, we convert it to a string, count the length, and check if the length is even using the condition len(str(v)) % 2 == 0.
With our example array, the condition yields False for 555 and 3, and True for 8001 and 22.
When we sum up these boolean values (False being 0 and True being 1), we get 0 (for 555) + 1 (for 8001) + 1 (for 22) + 0 (for 3), which equals 2.

Therefore, the function will return 2, indicating that there are two numbers in the array [555, 8001, 22, 3] that have an even number of digits.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findNumbers(self, nums: List[int]) -> int:
5        # Initialize a variable to count the even number of digits
6        even_digit_count = 0
7
8        # Iterate over each number in the nums list
9        for number in nums:
10            # Convert the current number to string to count digits
11            digit_str = str(number)
12          
13            # Check if the length of digit_str is even
14            if len(digit_str) % 2 == 0:
15                # If it is even, increment the even_digit_count
16                even_digit_count += 1
17      
18        # Return the total count of numbers with even number of digits
19        return even_digit_count
20

1class Solution {
2
3    // Function to count numbers with even number of digits
4    public int findNumbers(int[] nums) {
5        int countEvenDigits = 0; // Counter for numbers with even number of digits
6      
7        // Iterate through each number in the array
8        for (int num : nums) {
9            // Check if the length of the number's string representation is even
10            if (String.valueOf(num).length() % 2 == 0) {
11                countEvenDigits++; // If even, increment the counter
12            }
13        }
14      
15        // Return the total count of numbers with even number of digits
16        return countEvenDigits;
17    }
18}
19

1#include <vector>
2#include <string> // Include string library to use to_string function
3
4class Solution {
5public:
6    // Function to find the count of numbers with an even number of digits
7    int findNumbers(vector<int>& nums) {
8        int evenDigitCount = 0; // Initialize the count of even digit numbers to 0
9
10        // Loop through each number in the vector
11        for (int num : nums) {
12            // Convert the current number to a string
13            string numAsString = to_string(num);
14            // Check if the length of the string (number of digits) is even
15            if (numAsString.size() % 2 == 0) {
16                // If even, increment the count of even digit numbers
17                ++evenDigitCount;
18            }
19        }
20      
21        // Return the total count of numbers with an even number of digits
22        return evenDigitCount;
23    }
24};
25

1/**
2 * Finds the number of elements in an array that have an even number of digits.
3 * @param {number[]} nums - The array of numbers to check.
4 * @return {number} The count of elements with an even number of digits.
5 */
6const findNumbers = (nums: number[]): number => {
7    let countEvenDigits = 0; // Initialize count of numbers with even digits
8
9    // Iterate through each number in the provided array
10    for (const num of nums) {
11        // Convert the number to a string and check if its length is even
12        if (String(num).length % 2 === 0) {
13            countEvenDigits++; // Increment the count if the number has even digits
14        }
15    }
16
17    // Return the total count of numbers with even digits
18    return countEvenDigits;
19};
20

Time and Space Complexity

Time Complexity:

The time complexity of the function is O(n*k), where n is the number of elements in the nums list and k is the average number of digits in the numbers. The reason for this is that for each number in the array, we convert it to a string (to count the number of digits). The string conversion operation is dependent on the number of digits in the number, hence the time complexity is a product of these two factors.

Space Complexity:

The space complexity is O(1). This is because we only use a fixed amount of extra space: the space for the counter that the sum() function keeps accumulating. There are no additional data structures used that grow with the input size. The string representations of the numbers are temporary and not stored, so they do not add to the space complexity.

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

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

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know