1295. Find Numbers with Even Number of Digits
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 0
Acceptance rate: 78.8%
Problem Breakdown
The problem requires us to count how many numbers in a given array have an even number of digits. The input is an array nums containing integers, and the output should be the count of numbers with an even number of digits. The constraints are that the length of the array is between 1 and 500, and each integer in the array is between 1 and (10^5).
Intuition
A brute-force approach would involve iterating through each number in the array, converting it to a string or using logarithms to determine the number of digits, and then checking if this count is even. This approach is straightforward but not optimal in terms of time complexity since converting numbers to strings or calculating logarithms can be computationally expensive.
The key insight is that we can avoid these operations by directly manipulating the number through division and modulus operations. By repeatedly dividing the number by 10, we can count the digits without converting it to a string or using logarithms. This approach is more efficient in terms of time complexity.
Approach
- Initialize a counter
even_countto zero. - Iterate through each number in the array
nums. - For each number, initialize a variable
digit_countto zero. - While the number is greater than zero:
- Increment
digit_countby 1. - Divide the number by 10 (integer division).
- Increment
- After counting the digits, check if
digit_countis even. - If it is even, increment
even_countby 1. - Return
even_count.
Complexity Analysis
- Time Complexity: (O(n \cdot d)), where (n) is the number of elements in the array and (d) is the average number of digits in the numbers. Since (d) is at most 6 (because (10^5) has 6 digits), this simplifies to (O(n)).
- Space Complexity: (O(1)), as we are using a constant amount of extra space.
Solution
def findNumbers(nums):
even_count = 0
for num in nums:
digit_count = 0
while num > 0:
digit_count += 1
num //= 10
if digit_count % 2 == 0:
even_count += 1
return even_count
Edge Cases Handled
- Single-digit numbers: These will have
digit_countas 1, which is odd. - Multi-digit numbers: The algorithm correctly counts the digits and checks for evenness.
- Maximum constraint (10^5): This number has 6 digits, which is even, so it should be counted.
The provided solution is correct, efficient, and clear. It handles all edge cases as described in the problem statement.