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⋅logM)
- 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⋅logM)
- 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)