Find Even Number Of Digits in an Array

This problem tests your knowledge of mathematics. Solving this problem helps you find the place values and how they are represented in the decimal number system.

Problem statement

Given an array `A[]` of size `N`, return how many of them contain an even number of digits.

Examples

Example #1:

``````Input: A = [100, 25, 51, 2000, 4999]

Output: 4
100 contains 3 digits (odd number of digits) ❌
25 contains 2 digits (even number of digits) ✅
51 contains 2 digits (even number of digits) ✅
2000 contains 4 digits (even number of digits) ✅
4999 contains 4 digits (even number of digits) ✅

``````

Example #2:

``````Input: A = [777, 2, 1500, 1771]

Output: 2
777 contains 3 digits (odd number of digits) ❌
2 contains 1 digits (even number of digits) ❌
1500 contains 4 digits (even number of digits) ✅
1771 contains 4 digits (even number of digits) ✅

``````

Thought process

This problem is similar to the Count Number Of Digits In An Integer part, of course, Grokking Bit Manipulation For Coding Interviews.

Let us break the problem into smaller chunks and then merge all the solutions together to solve the problem.

The illustration below explains the process of counting the digits in an integer.

Number Number = (number / 10) Count
125 12 1
12 1 2
1 0 3

This is an example problem for counting digits in an integer. Solving this problem helps you find the place values and how they are represented in the decimal number system.

There are 4 different ways to solve this problem.

1. Division approach
2. Logarithmic
3. Recursive
4. String conversion

Division approach [while loop]

In this program, we use two loops, one loop to iterate through all the array elements, and the inner while loop is iterated until the expression `number != 0` is evaluated to `false`.

Let’s see one such iteration for `number = 125`.

Iterations

• After the first iteration,` n(125)` will be divided by `10`, and its value will be `12`, and the count is incremented to `1`.
• After the second iteration, the value of `n(12)` will be `1` and the count is incremented to `2`.
• After the third iteration, the value of `n(1)` will be `0`, and the count is incremented to `3`.

Then the expression is evaluated as false, as `n` is `0`, and the loop terminates.

Solution

``````public class FindEvenNumberDigits {
public static void main(String[] args) {
int[] A = {100, 25, 51, 2000, 4999};
System.out.println(evenDigits(A));
}

private static int evenDigits(int[] A) {
int result = 0;
for (int i = 0; i < A.length; i++) {
int number = A[i];
int count = 0;

while (number > 0) {
++count;
number /= 10;
}

result += (count & 1) == 0 ? 1 : 0;
}
return result;
}
}
``````

Complexity analysis

1. Time complexity:  `O(n2)`, the run time depends on the number of elements in the array and the number of digits per each integer. In the worst case, it iterates through all the digits until it becomes `0`, for all, array elements.
2. Space complexity: `O(1)`, no extra space is used, except the constant variable operations.

Logarithmic approach

We can use `log10` (logarithm of base 10) to count the number of digits of positive numbers.

Digit count of N = upper bound of log10(N).

Note: Logarithms are not defined for negative numbers.

log(0) is infinity
``````public class FindEvenNumberDigits {
public static void main(String[] args) {
int[] A = {100, 25, 51, 2000, 4999};
System.out.println(evenDigitsLogarithmic(A));
}

private static int evenDigitsLogarithmic(int[] A) {
int result = 0;
for (int number : A) {
int count = number != 0 ? ((int) Math.floor(Math.log10(number) + 1)) : -1;
result += (count & 1) == 0 ? 1 : 0;
}
return result;
}
}
``````

Some of the other ways to achieve this are shown below.

These approaches are not recommended, as the time and space complexities are high.

Recursive approach

This recursive approach might be ineffective when dealing with a large integer `n`.

A recursive call adds a stack entry every time it runs and again when once it reaches the base condition. It then backtracks and executes each recursive function.

``````public class FindEvenNumberDigits {
public static void main(String[] args) {
int[] A = {100, 25, 51, 2000, 4999};
System.out.println(recursiveApproach(A));
}

private static int recursiveApproach(int[] A) {
int result = 0;

for (int number : A) {
result += (helper(number) & 1) == 0 ? 1 : 0;
}
return result;
}

private static int helper(int n) {
// base checks
if (n == 0) {
return 0;
}

return (1 + helper(n / 10));
}
}
``````

Convert to string

This is one of the ways to implement/solve the problem, but it is not recommended, as we are converting one type of data to another.

``````public class FindEvenNumberDigits {
public static void main(String[] args) {
int[] A = {100, 25, 51, 2000, 4999};
System.out.println(convertToString(A));
}

private static int convertToString(int[] A) {
int result = 0;

for (int number : A) {
String n = Integer.toString(number);

result += ((n.length()) & 1) == 0 ? 1 : 0;
}
return result;
}
}
``````
Note: The string approach is just for your learning and understanding.
Coding Interview QuestionsArraysData Structures and Algorithms

Gopi is an engineering leader with 12+ of experience in full-stack development—a specialist in Java technology stack. He worked for multiple startups, the European govt, and FAANG in India and Europe.

Members Public

Leetcode 217: Contains Duplicate

This question marks the first problem when working on duplicate data, either integers or strings etc. Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies. Problem statement Given an integer array nums, return true if any

Members Public

Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews. Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe,

Members Public

Arrays From Zero To Mastery: A Complete Notes For Programmers

This article discusses array data structure with sketches, memory diagrams, array capacity vs. length, strengths & weaknesses, big-O complexities, and more!