Find Even Number Of Digits in an Array

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.

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 log₁₀(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.