 # Find Numbers with Even Number of Digits

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

## Problem Statement

Given an array of integers `nums`, write a function that returns the count of numbers in the array that have an even number of digits. The function should take in the `nums` array as input and return an integer representing the count of numbers with even digits.

## Examples

```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.```
```Input: nums = [555,901,482,1771]
Output: 1
Explanation:
Only 1771 contains an even number of digits.```

## Clarifying Questions

1. What is the size of the array?
2. Are there any constraints on the range of the integers in the array?
3. Does the array contain only positive integers or can it have negative integers as well?
4. By "even number of digits," do you mean numbers that have a digit count that is a multiple of 2 (e.g. 10, 100, 1000, etc.)?
5. Should the function return the count of numbers with even digits or the numbers themselves that have even digits?

## Solutions

There are several approaches to solving the problem:

### The Brute force Approach:

Counting the number of digits using division

One way to solve this problem is to iterate through each element of the array, convert it to a string, and check the length of the string to determine if it has an even number of digits. This approach has a time complexity of O(nk), where n is the size of the array and k is the maximum number of digits in the array.

#### Algorithm:

Iterate through the array and count the number of even-digit integers.

1. Initialize a variable to store the count of even-digit integers to 0.
2. Iterate through each integer in the array.
3. For each integer, determine the number of digits in it by repeatedly dividing it by 10 until it reaches 0.
4. If the count of digits is even, increment the count of even-digit integers by 1.
5. After iterating through all integers, return the count of even-digit integers.

Time Complexity: O(n * k), where n is the length of the input array and k is the maximum number of digits in a single integer in the input array. The time complexity is dominated by the nested while loop that counts the number of digits in each integer.

Space Complexity: O(1). The algorithm uses only a constant amount of space to store variables.

### The String Manipulation Approach:

String conversion

Another way to solve this problem is to convert each element of the array to a string and use string manipulation to check

#### Algorithm:

Convert each integer to a string and check the length of the string to determine if it has an even number of digits.

1. initialize a variable to store the count of even-digit integers to 0.
2. Iterate through each integer in the array.
3. Convert the integer to a string and determine its length.
4. If the length of the string is even, increment the count of even-digit integers by 1.
5. After iterating through all integers, return the count of even-digit integers.

Time Complexity: O(n * k), where n is the length of the input array and k is the maximum number of digits in a single integer in the input array. The time complexity is dominated by the for loop that iterates over each integer in the input array and the to_string function that converts each integer to a string.

Space Complexity: O(1). The algorithm uses only a constant amount of space to store variables.

Note: The String conversion approach may be slightly faster than the brute force approach, as it does not require division in order to count the number of digits. However, both approaches have a time complexity of O(n * k), where n is the length of the input array.

### Regular Expressions

#### Algorithm:

Use regular expressions to match integers that have an even number of digits.

1. Initialize a variable to store the count of even-digit integers to 0.
2. Create a regular expression that matches integers with an even number of digits.
3. Iterate through each integer in the array.
4. Convert the integer to a string and test it against the regular expression.
5. If the integer matches the regular expression, increment the count of even-digit integers by 1.
6. After iterating through all integers, return the count of even-digit integers.
Note: The regular expressions approach is faster than the previous approaches. However, it is less readable and may be more difficult to understand for some developers.

Time Complexity: O(n * k), where n is the length of the input array and k is the maximum number of digits in a single integer in the input array. The time complexity is dominated by the for loop that iterates over each integer in the input array and the regex_match function that checks whether a single integer has an even number of digits.

Space Complexity: O(1). The algorithm uses only a constant amount of space to store variables.

### Mathematical Approach:

Logarithmic

Another way to solve this problem is to use mathematical properties. We can use the logarithm to find the number of digits in each element of the array, and then check if the result is even or odd. This approach has a time complexity of O(n), where n is the size of the array.

#### Algorithm:

Use logarithms to determine the number of digits in each integer and then check if that count is even.

1. Initialize a variable to store the count of even-digit integers to 0.
2. Iterate through each integer in the array.
3. Compute the logarithm of the absolute value of the integer with base 10, and then add 1 to the result to get the count of digits in the integer.
4. If the count of digits is even, increment the count of even-digit integers by 1.
5. After iterating through all integers, return the count of even-digit integers.

The logarithmic approach uses a mathematical formula to calculate the number of digits in an integer in logarithmic time, which makes it the most efficient approach in terms of time complexity.

Time Complexity: O(n * log10(maxNum)), where n is the length of the input array and maxNum is the largest number in the input array. The time complexity is dominated by the for loop that iterates over each integer in the input array and the calculation of the number of digits in each integer, which takes O(log10(num)) time, where num is the integer being processed.

Space Complexity: O(1). The algorithm uses only a constant amount of space to store variables.

Note: The logarithmic time complexity and is faster than the previous approaches. However, it is less readable and may be more difficult to understand for some developers.
Overall, the logarithmic approach has the best time complexity of O(n * log10(maxNum)) among all the approaches discussed, making it the most efficient algorithm for this problem. In terms of space complexity, all four approaches use only a constant amount of space.
Share: 