Find Numbers with Even Number of Digits

Problem

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

Examples

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.

Solution

Method 1 - Extracting the digits by division by 10

The number of digits in an integer can be determined by repeatedly extracting individual digits using division until the number reduces to 0:

1. Start by initialising a counter for digits (digit_count = 0).
2. For each number n, repeatedly divide n by 10 until it becomes 0, while incrementing the counter in each iteration.
3. After counting the digits, check if the count is even.
4. Increment the total count whenever a number has an even number of digits.

Advantages of Using Division

• No dependency on additional libraries: Only basic arithmetic operations are involved, like division and modulo.
• Space efficiency: No conversion to strings or use of logarithms.

Code

Java

class Solution {
    public int findNumbers(int[] nums) {
        int ans = 0;
        for (int n : nums) {
            int digitCount = 0;
            while (n > 0) {
                n /= 10;  // Reduce the number by dividing it by 10
                digitCount++;  // Increase digit count for every division
            }
            if (digitCount % 2 == 0) {  // Check if the digit count is even
                ans++;
            }
        }
        return ans;
    }
}

Python

class Solution:
    def findNumbers(self, nums: List[int]) -> int:
        ans: int = 0
        for n in nums:
            digit_count = 0
            while n > 0: 
                n //= 10  # Reduce the number by dividing it by 10
                digit_count += 1  # Increase digit count for every division
            if digit_count % 2 == 0:  # Check if the digit count is even
                ans += 1
        return ans

Complexity

• ⏰ Time complexity: O(n*d). Each division reduces the number by a factor of 10, so the number of divisions is proportional to the number of digits d. For an array of size n, it’s O(n * d) where d is the average number of digits.
• 🧺 Space complexity: O(1)

Method 2 - Convert numbers to string

Here is what we can do:

• To determine the number of digits in a number, convert it to a string and check its length, as this is straightforward and avoids mathematical complexity.
• Check if the length of the string representation of each number is even.
• Increment the count whenever a number satisfies the condition.

Code

Java

class Solution {
    public int findNumbers(int[] nums) {
        int ans = 0;
        for (int n : nums) {
            if (String.valueOf(n).length() % 2 == 0) {
                ans++;
            }
        }
        return ans;
    }
}

Python

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

Complexity

• ⏰ Time complexity: O(n*d), where n is the length of the array and d is the number of digits in the number. For each number, it takes O(d) time to count, hence O(n*d) in total.
• 🧺 Space complexity: O(1), as we are not using additional space proportional to the input size, aside from the space required for the count and temporary variables.

Method 3 - Using the logarithm

When working with numbers, finding their digit count can be efficiently determined using logarithm properties. For a positive integer n, the number of digits is calculated as:

This formula works because logarithm base 10 gives the exponent required to express n as 10^k.

Using this, we can:

1. For each number in the array, calculate the digit count using logarithms.
2. Check if the digit count is even.
3. Increment the count when the condition is satisfied.

Code

Java

class Solution {

    public int findNumbers(int[] nums) {
        int ans = 0;
        for (int n : nums) {
            // Calculate number of digits via logarithm
            if (n > 0 && ((int) Math.log10(n) + 1) % 2 == 0) {
                ans++;
            }
        }
        return ans;
    }
}

Python

class Solution:
    def findNumbers(self, nums: List[int]) -> int:
        ans: int = 0
        for n in nums:
            # Calculate number of digits via logarithm
            if n > 0 and (int(math.log10(n)) + 1) % 2 == 0:
                ans += 1
        return ans

Complexity

• ⏰ Time complexity: O(n), where n is the length of the array. Each number is processed individually in O(1) time.
• 🧺 Space complexity: O(1), as we are not using additional space proportional to the input size, aside from the space required for the count and temporary variables.