Problem Informations

• Problem Index: 1295
• Problem Link: Find Numbers with Even Number of Digits
• Topics: Array, Math

Problem Description

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

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.

Constraints:

• $1 \leq nums.length \leq 500$
• $1 \leq nums[i] \leq 10^5$

Intuition

The problem asks us to determine the number of integers in a given array that have an even number of digits. The key to solving this problem is to accurately calculate the number of digits for each integer in the array. If an integer has an even number of digits, we increase our count. The intuitive approach is to traverse through each integer in the list and assess its digit count.

Approach

To address the problem, we implement the following approach:

1. Initialize a Counter: We start by declaring a variable evenDigitCount and initializing it to zero. This variable will store the count of numbers with an even number of digits.

2. Iterate through the Array: We loop through each integer num within the array nums.

3. Calculate Number of Digits: For each integer num, determine the number of digits it contains. We can find this by utilizing the base-10 logarithm function log10(num) which effectively returns the number of digits minus one. We add 1 to this result to get the accurate number of digits, thus the expression int(log10(num)) + 1 gives the full digit count.

4. Check Evenness of the Digit Count: We then check if this digit count is even by evaluating numDigits % 2 == 0. If this condition holds true, it indicates that the digit count is even.

5. Increment the Counter: If numDigits is even, we increment evenDigitCount.

6. Return the Result: After iterating through all numbers in the array, the value of evenDigitCount is returned, representing the total count of numbers containing an even number of digits.

This solution efficiently iterates over each number and uses mathematics via logarithms to determine digit counts, ensuring that we adhere to constraints optimally.

Code

C++

class Solution {
public:
    int findNumbers(vector<int>& nums) {
        int evenDigitCount = 0; // Initialize counter for numbers with an even number of digits
        
        for (int num : nums) {
            // Check if the number of digits is even. 
            // log10(num) gives the number of digits minus one.
            // Adding 1 makes it the exact number of digits.
            // If the result is even, (numDigits % 2 == 0) holds true.
            int numDigits = int(log10(num)) + 1;
            if (numDigits % 2 == 0) {
                evenDigitCount++; // Increment count if the condition is met
            }
        }
        
        return evenDigitCount; // Return the total count of numbers with even digits
    }
};

Python

class Solution:
    def findNumbers(self, nums):
        evenDigitCount = 0  # Initialize counter for numbers with an even number of digits
        
        for num in nums:
            # Check if the number of digits is even. 
            # log10(num) gives the number of digits minus one.
            # Adding 1 makes it the exact number of digits.
            # If the result is even, (numDigits % 2 == 0) holds true.
            numDigits = int(log10(num)) + 1
            if numDigits % 2 == 0:
                evenDigitCount += 1  # Increment count if the condition is met
        
        return evenDigitCount  # Return the total count of numbers with even digits

Complexity

• Time complexity: $O(n \cdot \log_{10}(k))$

  The time complexity primarily involves iterating through each element in the array nums of size $n$. For each number, a logarithmic calculation, specifically $\log_{10}$, is performed to determine the number of digits in the number. Given that $k$ is the maximum value possible for each element in nums ($k = 10^5$), the complexity for determining the number of digits in a number is $O(\log_{10}(k))$. Therefore, the overall time complexity for the algorithm is $O(n \cdot \log_{10}(k))$.

• Space complexity: $O(1)$

  The space complexity is constant, $O(1)$, because the algorithm only uses a fixed amount of additional memory, regardless of the size of the input. This includes storage for the evenDigitCount integer and the loop variable. The space usage does not scale with the input size $n$.