Given an array nums of integers, return how many of them contain an even number of digits.
Problem Statement
Given an array of integers nums, write a function that returns the count of numbers in the array that have an even number of digits.
The function should take in the nums array as input and return an integer representing the count of numbers with even digits.
Examples
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.
Input: nums = [555,901,482,1771]
Output: 1
Explanation:
Only 1771 contains an even number of digits.
Clarifying Questions
What is the size of the array?
Are there any constraints on the range of the integers in the array?
Does the array contain only positive integers or can it have negative integers as well?
By "even number of digits," do you mean numbers that have a digit count that is a multiple of 2 (e.g. 10, 100, 1000, etc.)?
Should the function return the count of numbers with even digits or the numbers themselves that have even digits?
Solutions
There are several approaches to solving the problem:
The Brute force Approach:
Counting the number of digits using division
One way to solve this problem is to iterate through each element of the array, convert it to a string, and check the length of the string to
determine if it has an even number of digits. This approach has a time complexity of O(nk), where n is the size of the array and k is the maximum
number of digits in the array.
Algorithm:
Iterate through the array and count the number of even-digit integers.
Initialize a variable to store the count of even-digit integers to 0.
Iterate through each integer in the array.
For each integer, determine the number of digits in it by repeatedly dividing it by 10 until it reaches 0.
If the count of digits is even, increment the count of even-digit integers by 1.
After iterating through all integers, return the count of even-digit integers.
public int CountNumbersWithEvenDigits(int[] nums) {
int count = 0; // initialize count variable to 0
foreach (int num in nums) { // loop through each integer in the input array
int numDigits = 0; // initialize the number of digits to 0
int temp = num; // create a temporary copy of the integer
while (temp != 0) { // while there are still digits in the integer
temp /= 10; // divide by 10 to remove the last digit
numDigits++; // increment the count of digits
}
if (numDigits % 2 == 0) { // if the number of digits is even
count++; // increment the count of integers with even digits
}
}
return count; // return the final count
}
def count_numbers_with_even_digits(nums):
count = 0 # initialize count variable to 0
for num in nums: # loop through each integer in the input array
num_digits = 0 # initialize the number of digits to 0
temp = num # create a temporary copy of the integer
while temp != 0: # while there are still digits in the integer
temp //= 10 # divide by 10 to remove the last digit
num_digits += 1 # increment the count of digits
if num_digits % 2 == 0: # if the number of digits is even
count += 1 # increment the count of integers with even digits
return count # return the final count
public int countNumbersWithEvenDigits(int[] nums) {
int count = 0; // initialize count variable to 0
for (int num : nums) { // loop through each integer in the input array
int numDigits = 0; // initialize the number of digits to 0
int temp = num; // create a temporary copy of the integer
while (temp != 0) { // while there are still digits in the integer
temp /= 10; // divide by 10 to remove the last digit
numDigits++; // increment the count of digits
}
if (numDigits % 2 == 0) { // if the number of digits is even
count++; // increment the count of integers with even digits
}
}
return count; // return the final count
}
int countNumbersWithEvenDigits(vector<int>& nums) {
int count = 0; // initialize count variable to 0
for (int num : nums) { // loop through each integer in the input array
int numDigits = 0; // initialize the number of digits to 0
int temp = num; // create a temporary copy of the integer
while (temp != 0) { // while there are still digits in the integer
temp /= 10; // divide by 10 to remove the last digit
numDigits++; // increment the count of digits
}
if (numDigits % 2 == 0) { // if the number of digits is even
count++; // increment the count of integers with even digits
}
}
return count; // return the final count
}
Time Complexity: O(n * k), where n is the length of the input array and k is the maximum number of digits in a single integer in
the input array. The time complexity is dominated by the nested while loop that counts the number of digits in each integer.
Space Complexity: O(1). The algorithm uses only a constant amount of space to store variables.
The String Manipulation Approach:
String conversion
Another way to solve this problem is to convert each element of the array to a string and use string manipulation to check
Algorithm:
Convert each integer to a string and check the length of the string to determine if it has an even number of digits.
initialize a variable to store the count of even-digit integers to 0.
Iterate through each integer in the array.
Convert the integer to a string and determine its length.
If the length of the string is even, increment the count of even-digit integers by 1.
After iterating through all integers, return the count of even-digit integers.
public int CountNumbersWithEvenDigits(int[] nums) {
int count = 0; // initialize count variable to 0
foreach (int num in nums) { // loop through each integer in the input array
if (num.ToString().Length % 2 == 0) { // if the number of digits is even
count++; // increment the count of integers with even digits
}
}
return count; // return the final count
}
def count_numbers_with_even_digits(nums):
count = 0 # initialize count variable to 0
for num in nums: # loop through each integer in the input array
if len(str(num)) % 2 == 0: # if the number of digits is even
count += 1 # increment the count of integers with even digits
return count # return the final count
public int countNumbersWithEvenDigits(int[] nums) {
int count = 0; // initialize count variable to 0
for (int num : nums) { // loop through each integer in the input array
if (String.valueOf(num).length() % 2 == 0) { // if the number of digits is even
count++; // increment the count of integers with even digits
}
}
return count; // return the final count
}
int countNumbersWithEvenDigits(vector<int>& nums) {
int count = 0; // initialize count variable to 0
for (int num : nums) { // loop through each integer in the input array
if (to_string(num).length() % 2 == 0) { // if the number of digits is even
count++; // increment the count of integers with even digits
}
}
return count; // return the final count
}
Time Complexity: O(n * k), where n is the length of the input array and k is the maximum number of digits in a single integer in
the input array. The time complexity is dominated by the for loop that iterates over each integer in the input array and the to_string function
that converts each integer to a string.
Space Complexity: O(1). The algorithm uses only a constant amount of space to store variables.
Note: The String conversion approach may be slightly faster than the brute force approach, as it does not require division in order to count the
number of digits. However, both approaches have a time complexity of O(n * k), where n is the length of the input array.
Regular Expressions
Algorithm:
Use regular expressions to match integers that have an even number of digits.
Initialize a variable to store the count of even-digit integers to 0.
Create a regular expression that matches integers with an even number of digits.
Iterate through each integer in the array.
Convert the integer to a string and test it against the regular expression.
If the integer matches the regular expression, increment the count of even-digit integers by 1.
After iterating through all integers, return the count of even-digit integers.
using System.Text.RegularExpressions;
public int CountNumbersWithEvenDigits(int[] nums) {
int count = 0; // initialize count variable to 0
foreach (int num in nums) { // loop through each integer in the input array
if (Regex.IsMatch(num.ToString(), @"^\d{2}(\d{2})*$")) { // if the number of digits is even
count++; // increment the count of integers with even digits
}
}
return count; // return the final count
}
import re
def count_numbers_with_even_digits(nums):
count = 0 # initialize count variable to 0
for num in nums: # loop through each integer in the input array
if re.match(r'^\d{2}(\d{2})*$', str(num)): # if the number of digits is even
count += 1 # increment the count of integers with even digits
return count # return the final count
import java.util.regex.Pattern;
public int countNumbersWithEvenDigits(int[] nums) {
int count = 0; // initialize count variable to 0
for (int num : nums) { // loop through each integer in the input array
if (Pattern.matches("^\\d{2}(\\d{2})*$", Integer.toString(num))) { // if the number of digits is even
count++; // increment the count of integers with even digits
}
}
return count; // return the final count
}
#include <regex>
int countNumbersWithEvenDigits(vector<int>& nums) {
int count = 0; // initialize count variable to 0
for (int num : nums) { // loop through each integer in the input array
if (regex_match(to_string(num), regex("^\\d{2}(\\d{2})*$"))) { // if the number of digits is even
count++; // increment the count of integers with even digits
}
}
return count; // return the final count
}
Note: The regular expressions approach is faster than the previous approaches. However, it is less readable and may be more difficult to
understand for some developers.
Time Complexity: O(n * k), where n is the length of the input array and k is the maximum number of digits in a single integer in
the input array. The time complexity is dominated by the for loop that iterates over each integer in the input array and the regex_match function
that checks whether a single integer has an even number of digits.
Space Complexity: O(1). The algorithm uses only a constant amount of space to store variables.
Mathematical Approach:
Logarithmic
Another way to solve this problem is to use mathematical properties. We can use the logarithm to find the number of digits in each element of the
array, and then check if the result is even or odd. This approach has a time complexity of O(n), where n is the size of the array.
Algorithm:
Use logarithms to determine the number of digits in each integer and then check if that count is even.
Initialize a variable to store the count of even-digit integers to 0.
Iterate through each integer in the array.
Compute the logarithm of the absolute value of the integer with base 10, and then add 1 to the result to get the count of digits in the integer.
If the count of digits is even, increment the count of even-digit integers by 1.
After iterating through all integers, return the count of even-digit integers.
public int CountNumbersWithEvenDigits(int[] nums) {
int count = 0; // initialize count variable to 0
foreach (int num in nums) { // loop through each integer in the input array
if ((int)(Math.Log10(num) + 1) % 2 == 0) { // if the number of digits is even
count++; // increment the count of integers with even digits
}
}
return count; // return the final count
}
import math
def count_numbers_with_even_digits(nums):
count = 0 # initialize count variable to 0
for num in nums: # loop through each integer in the input array
if int(math.log10(num) + 1) % 2 == 0: # if the number of digits is even
count += 1 # increment the count of integers with even digits
return count # return the final count
import java.lang.Math;
public int countNumbersWithEvenDigits(int[] nums) {
int count = 0; // initialize count variable to 0
for (int num : nums) { // loop through each integer in the input array
if ((int)(Math.log10(num) + 1) % 2 == 0) { // if the number of digits is even
count++; // increment the count of integers with even digits
}
}
return count; // return the final count
}
#include <cmath>
int countNumbersWithEvenDigits(vector<int>& nums) {
int count = 0; // initialize count variable to 0
for (int num : nums) { // loop through each integer in the input array
if ((int)(log10(num) + 1) % 2 == 0) { // if the number of digits is even
count++; // increment the count of integers with even digits
}
}
return count; // return the final count
}
The logarithmic approach uses a mathematical formula to calculate the number of digits in an integer in logarithmic time, which makes it the most
efficient approach in terms of time complexity.
Time Complexity: O(n * log10(maxNum)), where n is the length of the input array and maxNum is the largest number in the input
array. The time complexity is dominated by the for loop that iterates over each integer in the input array and the calculation of the number of
digits in each integer, which takes O(log10(num)) time, where num is the integer being processed.
Space Complexity: O(1). The algorithm uses only a constant amount of space to store variables.
Note: The logarithmic time complexity and is faster than the previous approaches. However, it is less readable and may be more difficult to
understand for some developers.
Overall, the logarithmic approach has the best time complexity of O(n * log10(maxNum)) among all the approaches discussed, making it the most
efficient algorithm for this problem. In terms of space complexity, all four approaches use only a constant amount of space.
