# 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.

## Table of Contents

## 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.

- Division approach
- Logarithmic
- Recursive
- 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

__Time complexity__:`O(n`

, 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^{2})`0`

, for all, array elements.__Space complexity__:`O(1)`

, no extra space is used, except the constant variable operations.

## Logarithmic approach

We can use `log`

(logarithm of base 10) to count the number of digits of positive numbers._{10}

Digit count of N = upper bound of log_{10}(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.

## Gopi Gorantala Newsletter

Join the newsletter to receive the latest updates in your inbox.