LeetCode 1295: Find Numbers with Even Number of Digits

Difficulty: Easy

Topics: Arrays, Digit Counting, Math

Companies: Google, Amazon, Microsoft

Pro Tip: This problem is excellent for practicing different approaches to digit counting in numbers. The optimal solution runs in O(n) time with O(1) space.

The problem "Find Numbers with Even Number of Digits" (LeetCode 1295) requires us to count how many numbers in an array have an even number of digits. This problem tests our ability to work with digits of numbers and efficiently count them.

Problem Statement

Given an array nums of integers, return how many of them contain an even number of digits.

Constraints

1 ≤ nums.length ≤ 500
1 ≤ nums[i] ≤ 10⁵

Problem Link

View on LeetCode ↗

Example 1

Input: nums = [12,345,2,6,7896]
Output: 2
Explanation: 
12 contains 2 digits (even number of digits). 
345 contains 3 digits (odd number of digits). 
2 contains 1 digit (odd number of digits). 
6 contains 1 digit (odd number of digits). 
7896 contains 4 digits (even number of digits). 
Therefore only 12 and 7896 contain an even number of digits.

Example 2

Input: nums = [555,901,482,1771]
Output: 1 
Explanation: 
Only 1771 contains an even number of digits.

Note: The key insight is recognizing that we can count digits either mathematically or by converting numbers to strings.

Approach 1: Mathematical Digit Counting

This approach counts the digits of each number mathematically by repeatedly dividing the number by 10 until it becomes 0. The number of divisions gives us the digit count.

Algorithm Steps

Initialize a counter to 0
Iterate through each number in the array
For each number:
- Initialize digit count to 0
- While number > 0:
  - Increment digit count
  - Divide number by 10 (integer division)
- If digit count is even, increment counter
Return the counter

Complexity Analysis

Time Complexity	Space Complexity
O(n*d)	O(1)

Where n is the number of elements and d is the average number of digits

Implementation


class Solution {
public:
    int findNumbers(vector<int>& nums) {
        int count = 0;
        for(int num : nums) {
            int digitCount = 0;
            while(num > 0) {
                digitCount++;
                num /= 10;
            }
            if(digitCount % 2 == 0) count++;
        }
        return count;
    }
};


class Solution {
    public int findNumbers(int[] nums) {
        int count = 0;
        for(int num : nums) {
            int digitCount = 0;
            while(num > 0) {
                digitCount++;
                num /= 10;
            }
            if(digitCount % 2 == 0) count++;
        }
        return count;
    }
}


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

Advantage: This approach doesn't require any additional space beyond the counter variable, making it very space-efficient.

Approach 2: String Conversion Method

This approach converts each number to a string and checks the length of the string to determine if it has an even number of digits.

Algorithm Steps

Initialize a counter to 0
Iterate through each number in the array
Convert the number to a string
Check if the string length is even
Increment counter if length is even
Return the counter

Complexity Analysis

Time Complexity	Space Complexity
O(n*d)	O(d)

Where n is the number of elements and d is the average number of digits

Implementation


class Solution {
public:
    int findNumbers(vector<int>& nums) {
        int count = 0;
        for(int num : nums) {
            string s = to_string(num);
            if(s.length() % 2 == 0) count++;
        }
        return count;
    }
};


class Solution {
    public int findNumbers(int[] nums) {
        int count = 0;
        for(int num : nums) {
            String s = Integer.toString(num);
            if(s.length() % 2 == 0) count++;
        }
        return count;
    }
}


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

Note: While this approach is more readable, it uses additional space for string conversion. The mathematical approach is more space-efficient.

Approach 3: Logarithmic Approach (Optimal)

This approach uses mathematical properties to count digits in constant time using logarithms. The number of digits in a number n is floor(log10(n)) + 1.

Algorithm Steps

Initialize a counter to 0
Iterate through each number in the array
Calculate digit count using log10
Check if digit count is even
Increment counter if even
Return the counter

Complexity Analysis

Time Complexity	Space Complexity
O(n)	O(1)

Implementation


#include <cmath>

class Solution {
public:
    int findNumbers(vector<int>& nums) {
        int count = 0;
        for(int num : nums) {
            int digitCount = log10(num) + 1;
            if(digitCount % 2 == 0) count++;
        }
        return count;
    }
};


class Solution {
    public int findNumbers(int[] nums) {
        int count = 0;
        for(int num : nums) {
            int digitCount = (int)(Math.log10(num)) + 1;
            if(digitCount % 2 == 0) count++;
        }
        return count;
    }
}


import math

class Solution:
    def findNumbers(self, nums: List[int]) -> int:
        count = 0
        for num in nums:
            digit_count = math.floor(math.log10(num)) + 1
            if digit_count % 2 == 0:
                count += 1
        return count

Optimal Solution: This approach is both time and space efficient, as it calculates digit count in constant time without additional space.

Approach 4: Range-Based Digit Counting

This approach leverages the constraint that numbers are between 1 and 10⁵ to determine digit count by checking number ranges.

Algorithm Steps

Initialize a counter to 0
Define ranges for numbers with even digits:
- 10-99 (2 digits)
- 1000-9999 (4 digits)
- 100000 (6 digits)
Iterate through each number
Check if number falls in any even-digit range
Increment counter if it does
Return the counter

Complexity Analysis

Time Complexity	Space Complexity
O(n)	O(1)

Implementation


class Solution {
public:
    int findNumbers(vector<int>& nums) {
        int count = 0;
        for(int num : nums) {
            if((num >= 10 && num <= 99) || 
               (num >= 1000 && num <= 9999) || 
               num == 100000) {
                count++;
            }
        }
        return count;
    }
};


class Solution {
    public int findNumbers(int[] nums) {
        int count = 0;
        for(int num : nums) {
            if((num >= 10 && num <= 99) || 
               (num >= 1000 && num <= 9999) || 
               num == 100000) {
                count++;
            }
        }
        return count;
    }
}


class Solution:
    def findNumbers(self, nums: List[int]) -> int:
        count = 0
        for num in nums:
            if (10 <= num <= 99) or (1000 <= num <= 9999) or num == 100000:
                count += 1
        return count

Note: This approach is very efficient for this specific problem due to the constrained input range, but wouldn't work for arbitrary number ranges.

Comparison of Approaches

Approach	Time Complexity	Space Complexity	When to Use	Pros	Cons
Mathematical	O(n*d)	O(1)	General case	Space efficient	Slightly slower
String Conversion	O(n*d)	O(d)	Readability	Easy to understand	Uses extra space
Logarithmic	O(n)	O(1)	Optimal solution	Fast and efficient	Math library needed
Range-Based	O(n)	O(1)	Constrained inputs	Very fast	Not generalizable

Interview Tip: The mathematical approach is generally preferred in interviews as it demonstrates understanding of number manipulation without relying on string conversion.

Frequently Asked Questions

1. Why does the mathematical approach work for counting digits?

The mathematical approach works because each division by 10 effectively removes the last digit of the number. By counting how many times we can divide the number by 10 before it becomes 0, we're counting its digits.

2. Is the string conversion method slower than the mathematical approach?

Both methods have similar time complexity (O(n*d)), but the string conversion method uses additional space for the string representations. The mathematical approach is generally more space-efficient.

3. How does the logarithmic approach count digits?

The logarithmic approach uses the mathematical property that floor(log10(n)) + 1 gives the number of digits in n. For example, log10(100) = 2, so floor(2) + 1 = 3 digits.

4. What's the advantage of the range-based approach?

The range-based approach is extremely fast (O(n) time) because it only needs to check number ranges rather than count digits. However, it only works for the specific input constraints of this problem.

5. How would you handle negative numbers in these solutions?

For negative numbers, you would first take the absolute value before counting digits. All given solutions can be easily modified to handle negatives by adding abs() or similar functions.

6. Which approach is best for very large numbers?

For very large numbers (beyond 10¹⁸), the logarithmic approach is most reliable as it maintains O(1) time complexity per number, while the mathematical approach would take longer with more digits.

7. Can these solutions be optimized further?

The logarithmic and range-based approaches are already optimal for this problem. The mathematical approach could be optimized with loop unrolling for small digit counts, but the improvement would be minimal.

8. How would you test these solutions?

Test cases should include: single-digit numbers, numbers with exactly 2/4 digits, the maximum value (100000), edge cases like 10, 99, 100, 9999, and random numbers in between.

9. What's the space complexity of the string conversion method?

The string conversion method has O(d) space complexity where d is the number of digits, as it needs to store the string representation of each number temporarily.

10. How does this problem relate to real-world applications?

Digit counting is fundamental in data validation, formatting numbers for display, and in algorithms that need to process numbers digit-by-digit (like checksum calculations).

Final Thoughts: This problem demonstrates multiple approaches to digit counting, each with different trade-offs. While the string conversion method is most readable, the mathematical and logarithmic approaches are more efficient. The range-based solution shows how constraints can be leveraged for optimal performance.