Find Numbers with Even Number of Digits
Easy Digit counting
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Count how many numbers in the array have an even count of digits (for example 12 and 4321 qualify, 7 and 123 do not).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: how many numbers have 2, 4, 6… digits?
Why this works: dividing by 10 chops off one digit, so counting digits takes about log10(x) steps. This is your first logarithmic loop.
Example: nums = [12, 345, 2, 6, 7896]
12 → 1 → 0 2 digits ✓345 → 34 → 3 → 0 3 digits2 → 0 1 digit6 → 0 1 digit7896 → 789 → 78 → 7 → 0 4 digits ✓answer: 2
✦Hints open one at a time
↗Approach
For each number count its digits with repeated division by 10 and check if the count is even. The inner loop runs about log10(x) times, so the total is O(n · log M) where M is the largest value. This is a good first example of a logarithmic loop.
</>Solution (Java)
class Solution {
public int findNumbers(int[] nums) {
int count = 0;
for (int x : nums) {
int digits = 0;
while (x > 0) { // runs log10(x) times
x /= 10;
digits++;
}
if (digits % 2 == 0) count++;
}
return count;
}
}!Common mistake
Converting each number to a String works but hides the cost; also forgetting that 0 has one digit (not a concern here since values are positive, but remember it in general).
- Time: O(n · log M), M = largest number.
- Space: O(1).
