Problem

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

Examples

Example 1:

1
2
3
4
5
6
7
8
9

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:

1
2
3
4

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

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: $$ \text{digits} = \lfloor \log_{10}(n) \rfloor + 1 ) $$ 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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;
    }
}
1
2
3
4
5
6
7
8

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.