Find Numbers with Even Number of Digits

Easy

#1206Time: O(N * D), where N is the number of elements in the array and D is the maximum number of digits in a number. Converting a number with D digits to a string takes O(D) time. Given the problem constraints, D is small, so the complexity is often simplified to O(N).Space: O(D), where D is the maximum number of digits in a number. This space is required to store the string representation of a number. Since the constraints limit numbers to 10^5, D is at most 6, making the space complexity effectively O(1).1 company

Patterns

Math

Data structures

Array

Companies

Quora

Prompt

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 <= nums.length <= 500
1 <= nums[i] <= 10⁵

Approaches

4 approaches with complexity analysis and trade-offs.

This approach iterates through each number in the input array. For each number, it converts it into a string and then checks the length of the string. If the length is an even number, a counter is incremented.

Algorithm

Initialize a counter evenDigitCount to 0.
Loop through each integer num in the nums array.
Convert the integer num to its string representation using String.valueOf(num).
Find the length of the resulting string.
Check if the length is divisible by 2 (i.e., length % 2 == 0).
If the length is even, increment evenDigitCount.
After iterating through all the numbers, return evenDigitCount.

Walkthrough

This method provides a straightforward way to solve the problem by leveraging built-in string functionalities. The core idea is that the number of digits in an integer is equivalent to the length of its string representation.

We initialize a counter evenDigitCount to 0.
We then loop through each integer num in the input nums array.
Inside the loop, we convert the current number num to a string. For example, the integer 123 becomes the string "123".
We then get the length of this string. The length of "123" is 3.
We check if this length is an even number using the modulo operator (length % 2 == 0).
If the condition is true, we increment our evenDigitCount.
After the loop has processed all numbers in the array, the evenDigitCount holds the total count of numbers with an even number of digits, which we then return.

1class Solution {2    public int findNumbers(int[] nums) {3        int evenDigitCount = 0;4        for (int num : nums) {5            // Convert the number to a string6            String s = String.valueOf(num);7            // Check if the length of the string is even8            if (s.length() % 2 == 0) {9                evenDigitCount++;10            }11        }12        return evenDigitCount;13    }14}

Complexity

Time

O(N * D), where N is the number of elements in the array and D is the maximum number of digits in a number. Converting a number with D digits to a string takes O(D) time. Given the problem constraints, D is small, so the complexity is often simplified to O(N).

Space

O(D), where D is the maximum number of digits in a number. This space is required to store the string representation of a number. Since the constraints limit numbers to 10^5, D is at most 6, making the space complexity effectively O(1).

Trade-offs

Pros

Simple to understand and implement.
The logic is very direct and easy to reason about.

Cons

Incurs the overhead of string conversion and memory allocation for each number, which is generally less efficient than purely mathematical approaches.

This method avoids string conversion by using a mathematical formula to find the number of digits. The number of digits in any positive integer n can be calculated as floor(log10(n)) + 1. We iterate through the array, calculate the number of digits for each number using this formula, and count how many have an even number of digits.

Algorithm

Initialize a counter evenDigitCount to 0.
Loop through each integer num in the nums array.
Calculate the number of digits using the formula (int)Math.floor(Math.log10(num)) + 1.
Check if the calculated number of digits is even.
If it is, increment evenDigitCount.
After the loop, return evenDigitCount.

Walkthrough

Instead of converting numbers to strings, we can use a mathematical property to find the number of digits. The base-10 logarithm of a number can tell us its magnitude. Specifically, for any positive integer num, the number of digits is floor(log10(num)) + 1.

We start with a counter evenDigitCount set to 0.
We iterate through each num in the nums array.
For each num, we compute Math.log10(num). For example, log10(345) is approximately 2.53.
We take the floor of this value (floor(2.53) is 2) and add 1, which gives us the correct digit count of 3.
We then check if this digit count is even.
If it is, we increment evenDigitCount.
Finally, we return the total count.

1import java.lang.Math;2 3class Solution {4    public int findNumbers(int[] nums) {5        int evenDigitCount = 0;6        for (int num : nums) {7            // Calculate number of digits using logarithm8            int digitCount = (int) Math.floor(Math.log10(num)) + 1;9            // Check if the digit count is even10            if (digitCount % 2 == 0) {11                evenDigitCount++;12            }13        }14        return evenDigitCount;15    }16}

Complexity

Time

O(N), where N is the number of elements in the array. We iterate through the array, and for each element, we perform a `log10` operation, which is generally considered a constant time operation for standard integer types.

Space

O(1). No extra space that scales with the input size is used. We only use a few variables for the counter and temporary calculations.

Trade-offs

Pros

Avoids the overhead of string conversion and object creation.
The code for calculating the number of digits is very concise.

Cons

Relies on floating-point arithmetic (log10), which can be slower than pure integer arithmetic.
Can have precision issues with extremely large numbers, although it's not a problem for the given constraints.

This approach counts the digits of each number by repeatedly dividing it by 10 until it becomes 0. This method uses only integer arithmetic, which is typically faster than string conversions or floating-point operations.

Algorithm

Initialize a main counter evenDigitCount to 0.
Iterate through each num in the nums array.
For each num, initialize a temporary digit counter digits to 0.
Use a while loop that continues as long as the current number is greater than 0.
Inside the loop, increment digits and update the number by dividing it by 10 (num = num / 10).
After the loop, check if digits is even. If so, increment evenDigitCount.
Return evenDigitCount after checking all numbers.

Walkthrough

This is a highly efficient method that relies on basic integer arithmetic. To count the digits of a number, we can repeatedly perform integer division by 10 and count how many times we can do this before the number becomes 0.

We initialize a counter evenDigitCount to 0.
We loop through each num in the nums array.
For each num, we find its digit count. Let's take 7896 as an example:
1. Initialize digits = 0.
2. 7896 > 0: digits becomes 1, num becomes 789.
3. 789 > 0: digits becomes 2, num becomes 78.
4. 78 > 0: digits becomes 3, num becomes 7.
5. 7 > 0: digits becomes 4, num becomes 0.
6. 0 > 0 is false, loop terminates. The digit count is 4.
We then check if the final digits count (4 in this case) is even. If it is, we increment evenDigitCount.
After processing all numbers, we return the final count.

1class Solution {2    public int findNumbers(int[] nums) {3        int evenDigitCount = 0;4        for (int num : nums) {5            if (hasEvenDigits(num)) {6                evenDigitCount++;7            }8        }9        return evenDigitCount;10    }11 12    private boolean hasEvenDigits(int num) {13        int digitCount = 0;14        while (num > 0) {15            digitCount++;16            num /= 10;17        }18        return digitCount % 2 == 0;19    }20}

Complexity

Time

O(N * D), where N is the number of elements and D is the maximum number of digits. Since D is small and bounded by the constraint (max 6 digits for 10^5), the complexity is effectively O(N). This is generally faster in practice than the string and log approaches.

Space

O(1). We only use a few variables to store counts and perform calculations, requiring constant extra space.

Trade-offs

Pros

Very efficient as it only uses fast integer arithmetic operations.
Avoids the overhead of creating new objects (like strings) or using slower floating-point math.

Cons

The code is slightly more verbose than the logarithm-based approach.

This approach takes full advantage of the problem's constraints (1 <= nums[i] <= 10^5). Instead of calculating the number of digits for each number, we can directly check if a number falls within the specific ranges that correspond to an even number of digits.

Algorithm

Initialize count = 0.
For each num in nums:
Check if (10 <= num <= 99) OR (1000 <= num <= 9999) OR (num == 100000).
If the condition is true, increment count.
Return count.

Walkthrough

This is the most optimal solution because it leverages the given constraints to avoid any form of digit counting altogether. The constraints 1 <= nums[i] <= 10^5 mean that any number in the input array can have 1, 2, 3, 4, 5, or 6 digits.

We are only interested in numbers with an even number of digits. These are:

Numbers with 2 digits: from 10 to 99.
Numbers with 4 digits: from 1000 to 9999.
Numbers with 6 digits: only 100000 is possible under the constraint.

We can combine these checks into a single if statement. For each number in the input array, we check if it satisfies any of these conditions. If it does, we increment a counter.

1class Solution {2    public int findNumbers(int[] nums) {3        int count = 0;4        for (int num : nums) {5            if ((num >= 10 && num <= 99) || 6                (num >= 1000 && num <= 9999) || 7                num == 100000) {8                count++;9            }10        }11        return count;12    }13}

This method is extremely fast because it replaces loops (for division) or complex function calls (log10, String.valueOf) with a few simple integer comparisons.

Complexity

Time

O(N). We iterate through the array once. Each check inside the loop consists of a few simple integer comparisons, which takes constant time. This is the fastest possible approach.

Space

O(1). No extra space is needed beyond a single counter variable.

Trade-offs

Pros

The most efficient solution in terms of raw performance.
Extremely simple logic that avoids any form of iteration or complex math for digit counting.

Cons

The solution is hard-coded to the specific constraints of the problem (1 <= nums[i] <= 10^5).
If the constraints were to change, the if condition would need to be manually updated, making it less general than other approaches.

Solutions

Solution

1class Solution {2public3  int findNumbers(int[] nums) {4    int ans = 0;5    for (int v : nums) {6      if (String.valueOf(v).length() % 2 == 0) {7        ++ans;8      }9    }10    return ans;11  }12}

1/** * @param {number[]} nums * @return {number} */ var findNumbers = function (2  nums,3) {4  let ans = 0;5  for (const v of nums) {6    ans += String(v).length % 2 == 0;7  }8  return ans;9};

1class Solution:2    def findNumbers(3        self, nums: List[int]) -> int: return sum(len(str(v)) % 2 == 0 for v in nums)

1class Solution {2public:3  int findNumbers(vector<int> &nums) {4    int ans = 0;5    for (int &v : nums) {6      ans += to_string(v).size() % 2 == 0;7    }8    return ans;9  }10};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int findNumbers(int[] nums) {4    int ans = 0;5    for (int v : nums) {6      if (String.valueOf(v).length() % 2 == 0) {7        ++ans;8      }9    }10    return ans;11  }12}

1/** * @param {number[]} nums * @return {number} */ var findNumbers = function (2  nums,3) {4  let ans = 0;5  for (const v of nums) {6    ans += String(v).length % 2 == 0;7  }8  return ans;9};

1class Solution:2    def findNumbers(3        self, nums: List[int]) -> int: return sum(len(str(v)) % 2 == 0 for v in nums)

1class Solution {2public:3  int findNumbers(vector<int> &nums) {4    int ans = 0;5    for (int &v : nums) {6      ans += to_string(v).size() % 2 == 0;7    }8    return ans;9  }10};

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.