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] <= 105

Solution

Approach 1: Extract Digits

class Solution {
    public int findNumbers(int[] nums) {
        int n = nums.length;
        int countEvenDigits = 0;
        for(int i = 0; i < n; i++){
            if(hasEvenDigits(nums[i])){
                countEvenDigits++;
            }
        }
        return countEvenDigits;
    }

    private boolean hasEvenDigits(int num){
        int digits = 0;
        while(num != 0){
            digits++;
            num = num / 10;
        }
        return digits % 2 == 0;   // (digitCount & 1) == 0;
    }
}

Complexity Analysis

Let N be the length of nums, which represents the number of integers for which we have to check.
Let M be the maximum integer in nums.

  • Time complexity: O(N⋅log⁡M)
  • Space complexity: O(1)

Approach 2: Convert to String

class Solution {
    public int findNumbers(int[] nums) {
        // Counter to count the number of even digit integers
        int evenDigitCount = 0;

        for (int num : nums) {
            // Convert num to string and find its length
            int length = String.valueOf(num).length();
            if (length % 2 == 0)
                evenDigitCount++;
        }

        return evenDigitCount;
    }
}

Complexity Analysis

Let N be the length of nums, which represents the number of integers for which we have to check.
Let M be the maximum integer in nums.

  • Time complexity:
  • Space complexity:

Approach 3: Using Logarithm

class Solution {
    public int findNumbers(int[] nums) {
        // Counter to count the number of even digit integers
        int evenDigitCount = 0;

        for (int num : nums) {
            // Compute the number of digits in the num
            int digitCount = (int) Math.floor(Math.log10(num)) + 1;
            if (digitCount % 2 == 0)
                evenDigitCount++;
        }

        return evenDigitCount;
    }
}

Complexity Analysis

Let N be the length of nums, which represents the number of integers for which we have to check.
Let M be the maximum integer in nums.

  • Time complexity: O(N⋅log⁡M)
  • Space complexity: O(1)

Approach 4: Constraint Analysis

Analyzing constraints helped us to not worry about negative integers. Can we use constraint to our advantage in some other way?

Let’s take a look at the constraint again.

OR

Let’s take a look at the integers in the range [1,100000] 

  • 1⇝9 have 1, hence an odd number of digits.
  • 10⇝99 have 2, hence an even number of digits.
  • 100⇝999 have 3, hence an odd number of digits.
  • 1000⇝9999 have 4, hence an even number of digits.
  • 10000⇝99999 have 5, hence an odd number of digits.
  • 100000 has 6, hence an even number of digits.
class Solution {
    public int findNumbers(int[] nums) {
        // Counter to count the number of even digit integers
        int evenDigitCount = 0;

        for (int num : nums) {
            if ((num >= 10 && num <= 99) ||
                (num >= 1000 && num <= 9999) || 
                 num == 100000)
                evenDigitCount++;
        }

        return evenDigitCount;
    }
}

Complexity Analysis

Complexity Analysis

Let N be the length of nums, which represents the number of integers for which we have to check.

  • Time complexity: O(N)
  • Space complexity: O(1)