Taro Logo

Find Numbers with Even Number of Digits

Easy
Quora logo
Quora
1 view
Topics:
Arrays

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


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What is the range of values for the integers within the input array `nums`? Can they be negative, zero, or extremely large?
  2. What is the maximum size of the input array `nums`?
  3. If the input array `nums` is empty, what should I return?
  4. Are all elements in the array integers, or could there be other data types?
  5. Are we concerned about integer overflow when calculating the number of digits?

Brute Force Solution

Approach

We want to find how many numbers in a given list have an even number of digits. The brute force method involves checking each number individually and counting its digits. If the digit count is even, we increment a counter.

Here's how the algorithm would work step-by-step:

  1. Take the first number from the list.
  2. Count how many digits that number has.
  3. Check if the number of digits is an even number.
  4. If the number of digits is even, add one to a running total.
  5. Repeat these steps for every number in the list.
  6. Once you've checked all the numbers, the running total will be the final answer.

Code Implementation

def find_numbers_with_even_number_of_digits(numbers):
    even_digits_count = 0
    for number in numbers:
        # Convert the number to a string to easily count digits
        number_string = str(number)

        number_of_digits = len(number_string)

        # Check if the number of digits is even
        if number_of_digits % 2 == 0:

            # Increment the counter if the digit count is even
            even_digits_count += 1

    return even_digits_count

Big(O) Analysis

Time Complexity
O(n)The algorithm iterates through each of the n numbers in the input list. For each number, it counts the number of digits, which takes time proportional to the number of digits in that number. However, the number of digits is bounded by a constant (the maximum number of digits a number in the list can have), so the digit counting step can be considered O(1). Since we perform an O(1) operation for each of the n numbers, the overall time complexity is O(n).
Space Complexity
O(1)The provided solution iterates through the input list and calculates the number of digits for each number individually. It uses a counter variable to keep track of the numbers with an even number of digits. The extra space used is only for the counter variable, which remains constant regardless of the input list size, N. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The problem requires us to count numbers with an even number of digits. The trick is to quickly figure out how many digits a number has and check if that count is even without doing any complicated calculations.

Here's how the algorithm would work step-by-step:

  1. Consider each number one at a time.
  2. For each number, figure out how many digits it contains.
  3. A quick way to count the digits is to repeatedly divide the number by ten until you reach zero, and count how many divisions it takes.
  4. After counting the digits, check if the count is an even number. You can do this by dividing the count by two and seeing if there is any remainder. No remainder means it's even.
  5. If the number of digits is even, add one to your final total count.
  6. Repeat this process for all the numbers and at the end, you'll have the answer.

Code Implementation

def find_numbers_with_even_number_of_digits(numbers):
    even_digit_count = 0

    for number in numbers:
        digit_count = 0
        temporary_number = number

        # Count digits by repeatedly dividing by 10
        while temporary_number > 0:
            temporary_number //= 10
            digit_count += 1

        # Check if the number of digits is even
        if digit_count % 2 == 0:
            # Increment the count if even
            even_digit_count += 1

    return even_digit_count

Big(O) Analysis

Time Complexity
O(n*log(m))The algorithm iterates through each of the n numbers in the input array. Inside the loop, for each number, we count its digits by repeatedly dividing the number by 10 until it becomes 0. The number of divisions is proportional to the logarithm base 10 of the number itself (m). Therefore, counting digits takes O(log(m)) time, where m is the value of the number. Because this digit-counting process occurs for each of the n numbers, the total time complexity is O(n*log(m)), where m is the largest number in the input.
Space Complexity
O(1)The algorithm iterates through the input numbers, but it only uses a few constant space variables: one to store the digit count for each number and another to store the final count of numbers with even digits. No auxiliary data structures like lists or hash maps are used to store data dependent on the input size N (the number of input numbers). Therefore, the space complexity is constant and independent of the input size.

Edge Cases

CaseHow to Handle
Null or empty input arrayReturn 0 immediately, as there are no numbers to evaluate.
Array containing only single-digit numbersCount will be 0 as none of the numbers will have even digits.
Array with extremely large numbers that could cause integer overflow during digit countingConsider using string conversion to count digits to avoid integer overflow.
Array containing only negative numbersTake the absolute value of each number before counting digits, as the negative sign doesn't affect digit count.
Array containing zerosZero has one digit, therefore should not be counted toward the even number count.
Array with a large number of elements to assess performance implicationsEnsure the algorithm has O(n) time complexity by iterating through the array once.
Array with a mix of positive and negative numbersThe algorithm should correctly handle both positive and negative integers after taking the absolute value.
Array where all numbers have an even amount of digitsThe count should accurately reflect the number of elements in the array.