LeetCode 1295 - Find Numbers with Even Number of Digits

Difficulty: 🟢 Easy
Topics: Array, Math

Solution

Problem Understanding

The problem asks us to determine how many numbers in a given array nums have an even number of digits. The input is an array of integers, and the output is a single integer representing the count of numbers with an even digit length. For example, the number 12 has 2 digits, which is even, while 345 has 3 digits, which is odd.

The constraints indicate that the input array is relatively small (1 <= nums.length <= 500) and each number is positive and bounded (1 <= nums[i] <= 10^5). These constraints imply that performance is not a major concern, and a straightforward approach will work efficiently. We must consider edge cases like single-digit numbers, numbers at the upper bound of the constraint (like 100000), and arrays with only one element. The problem guarantees that all numbers are positive integers, so we do not need to handle zeros or negative numbers.

Approaches

A brute-force approach would involve converting each number to a string and counting its length. If the length is even, we increment a counter. This works because the number of characters in the string representation of a number corresponds to its number of digits.

A slightly more optimal approach avoids string conversion entirely and instead uses mathematical operations. We can repeatedly divide a number by 10 and count the iterations until it becomes zero. If the count is even, we increment our result. This reduces the overhead of string conversion and is purely numeric.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * log10(k))	O(1)	Convert number to string and check length
Optimal	O(n * log10(k))	O(1)	Count digits using division without string conversion

Here, n is the number of elements in the array, and k is the maximum value in nums. Both approaches have similar asymptotic complexity, but the numeric approach avoids string allocation.

Algorithm Walkthrough

Initialize a variable count to zero to keep track of numbers with even digits.
Iterate through each number in nums.
For each number, initialize a digits counter to zero.
Repeatedly divide the number by 10, incrementing digits at each step, until the number becomes zero.
Check if digits is even. If it is, increment count by one.
Continue until all numbers have been processed.
Return count.

Why it works: The algorithm correctly counts digits for each number by leveraging the property that integer division by 10 removes the last digit. Checking for evenness ensures we only count numbers with an even number of digits.

Python Solution

from typing import List

class Solution:
    def findNumbers(self, nums: List[int]) -> int:
        count = 0
        for num in nums:
            digits = 0
            current = num
            while current > 0:
                current //= 10
                digits += 1
            if digits % 2 == 0:
                count += 1
        return count

The implementation initializes a counter count to store the number of even-digit numbers. For each number in nums, it calculates the number of digits using a while loop and integer division. If the digit count is even, it increments the counter. Finally, it returns the total count.

Go Solution

func findNumbers(nums []int) int {
    count := 0
    for _, num := range nums {
        digits := 0
        current := num
        for current > 0 {
            current /= 10
            digits++
        }
        if digits%2 == 0 {
            count++
        }
    }
    return count
}

The Go solution mirrors the Python logic. We initialize count to zero, iterate over the slice nums, and calculate the number of digits for each number using a for loop. Go-specific differences include the use of := for declaration and slice iteration with range.

Worked Examples

Example 1: nums = [12, 345, 2, 6, 7896]

num	digits	even?	count
12	2	yes	1
345	3	no	1
2	1	no	1
6	1	no	1
7896	4	yes	2

Return 2.

Example 2: nums = [555, 901, 482, 1771]

num	digits	even?	count
555	3	no	0
901	3	no	0
482	3	no	0
1771	4	yes	1

Return 1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * log10(k))	Each number is divided by 10 until zero, n numbers processed
Space	O(1)	Only a few integer variables are used, no extra data structures

The time complexity is dominated by the number of digits in each number. The space complexity is constant because we do not store intermediate results.

Test Cases

# Provided examples
assert Solution().findNumbers([12,345,2,6,7896]) == 2  # mix of even and odd digits
assert Solution().findNumbers([555,901,482,1771]) == 1  # only last number even

# Edge cases
assert Solution().findNumbers([1]) == 0  # single-digit number
assert Solution().findNumbers([22]) == 1  # single two-digit number
assert Solution().findNumbers([100000]) == 1  # largest number in range, 6 digits

# Mixed digits
assert Solution().findNumbers([10, 1234, 56789, 2468]) == 3  # 10,1234,2468 even digits
assert Solution().findNumbers([7, 88, 999, 12345, 678901]) == 2  # 88,678901 even

Test	Why
`[12,345,2,6,7896]`	Normal mixed input
`[555,901,482,1771]`	Only one number has even digits
`[1]`	Single-digit, smallest input
`[22]`	Single two-digit number
`[100000]`	Number at upper bound of constraint
`[10,1234,56789,2468]`	Mix of even and odd digits in multiple numbers
`[7,88,999,12345,678901]`	Mix with largest numbers, multiple even-digit counts

Edge Cases

Single-element array: The array may contain only one number. If it is a single-digit number, the count should be zero. Our implementation correctly handles this by iterating over the array regardless of its size.

Maximum number length: Numbers up to 10^5 have up to 6 digits. The algorithm handles this naturally because it counts digits dynamically and does not assume a maximum digit length.

All numbers have odd digits: If every number has an odd number of digits, the count should be zero. The implementation correctly checks the parity of the digit count and does not increment the counter when the digits are odd.