1295. Find Numbers with Even Number of Digits

EasyArray
Leetcode Link

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.

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

Which of these properties could exist for a graph but not a tree?

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:

  1. Iterate through each number in the input list nums with a for loop embedded in a list comprehension.

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

  3. Use the len() function to count the number of characters, which represent the digits, in the string.

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

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

  6. 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:

1return 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.

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

Which technique can we use to find the middle of a linked list?

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.

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

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

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

  4. 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:

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

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

  2. With our example array, the condition yields False for 555 and 3, and True for 8001 and 22.

  3. 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
Not Sure What to Study? Take the 2-min Quiz：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following array represent a max heap?

Recommended Readings

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

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

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 👨‍🏫