Paul Coroneos

We continue looking into array problems with LeetCode 1295 - Find Numbers with Even Number of Digits

Problem statement and analysis

Let's start by taking a look at the problem statement:

Given an array nums of integers, return how many of them contain an even number of digits.

Sounds simple enough at first glance. So for example given:

[1, 123, 22, 44];

By inspect we see numbers at indices 0 and 1 have an odd number of digits. So we would say two numbers are odd.

Now unfortunately there is no Number.isOddDigits() or Number.isEvenDigits() method in JavaScript (at least that I am aware of, if there is please feel free to let me know!) So natively we do not have a method available to determine even or oddness of digit count. However, we can use a nifty property of math and simple division to made a pretty darn good digit counter.

How to count digits in an integer

Recall from when you first started learning about numbers (in base 10, though none of us really knew that was what we were being taught) that there was discussion of places. For example suppose we took the number 1. The number one has the digit one located in the ones place. Similarly if we take the integer 10, this is a number that consists of a digit one in the 10's place and a digit of 0 in the ones place.

We can represent a base 10 number as the sum of its digits where each digit is multiplied by its base number (10) to the power of the place it resides (starting at index 0). Confused? That's okay lets look at it in table format:

| Number | 10^(2) | 10^(1) | 10^(0) | | :----- | :----: | :----: | :----: | | 345 | 3 | 4 | 5 | | 21 | 0 | 2 | 1 |

So let's take for example the number 345. 345 can be broken up to be 3 _ 10^2 + 4 _ 10^1 + 5 _ 10^0. Similarly 21 can be broken up to read (let's just keep 10^2 for illustrative purposes) 0 _ 10^2 + 2 _ 10^1 + 1 _ 10^0.

So why go through all this trouble to explain base 10 concepts? Well it turns out many algorithms build off this division concept. What we now have learned is that digits are simply varying levels of multiples of 10 from one another summed together. Armed this with knowledge this mean we can extract digits by simply dividing the number over and over again by its base (10) until the floor of the number is 0.

Now why does the floor matter? Suppose the last place of a number is 1. The number 1 divided by ten will become a fractional number (in this case 0.1). But becase we are dealing with integers in the problem if we get to decimals that means we have exhausted the digits to count. At this point we should correctly stop counting digits.

Okay so we did a bunch of work. But Paul you may ask, we have no idea whether the digit count is even or odd! There is in fact no Number.isEven() or Number.isOdd() (again please let me know if I am mistaken)! Well time for trick number two.

Determining whether a number is even or odd using modulus (remainder)

Growing up I sure did a lot of division in class. In fact I really had to improve my handwriting a lot to make sure my columns lined up in long division! But one day I remember my teacher taught us something about a new type of division. One that would actually return the remainder of the division of two numbers. And thus I learned about the modulus operator.

Now of course you aren't here to hear my crappy stories about my handwriting (it still sucks). What you're wondering now is why do we care about remainder division. Well, as it turns out knowing whether a number has a remainder is very powerful in algorithms.

Take yourself back down memory lane to elementary school when you first learned about even and odd numbers. What did your math teacher talk to you about when you started trying to do simple proofs. Can't remember? It's okay I barely do either. 😆 Let's summarize the properties of even and odd numbers:

The sum off two even or odd numbers is an even number The sum of an even and odd number is an odd number Even numbers are divisible by 2 with no remainder An odd number leaves a remainder of 1

So what properties stand out to you that we might be able to take advantage of using the modulus operator? The last two! So simply put if we compute the modulus of the integer by 2 an answer of one or zero correspond to an odd or even number respectively.

Now we should have the tools we need to solve this algorithm. But for now let's quickly write out the psuedocode based off what we have learned.

Even Check Psuedocode

// Inialize a counter to 0

// Loop while the floor of the number from the array is greater than zero
// increment digit count
// set the number to itself divided by 10

// Check to see if the number of digits is even, and if so increment even counter

Now with that out of the way let's examine the main problem psuedocode which becomes quite trivial:

Main Problem Psuedocode

// Check base case that if array is empty return 0
// Inialize a counter to 0

// Loop through all the array elements
// If the element is even, increment the counter

//return counter value

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var findNumbers = function (nums) {
  //base cases
  if (nums.length === 0) return 0;

  let evenCnt = 0;
  for (let num of nums) {
    let digitCnt = 0;
    while (Math.floor(num) > 0) {
      digitCnt++;
      num /= 10;
    }
    if (digitCnt % 2 === 0) evenCnt++;
  }
  return evenCnt;
};

So starting out we check if the array is empty. If so we already know there are 0 even numbers. We then instantiate the loop to count through all the numbers in the array. For each one we loop through the digits by dividing the number from the array by 10 and incrementing a scoped counter until the number has only fractional value. Finally we perform modulus on this count to determine whether the digit count is even or odd. Finally once we complete iteration through the array we simply return the even count we have calculated.

Complexity

This problem is slightly trickier from a complexity perspective. We see two loops which might make you think the complexity is O(M x N), where M is the array count and N is the longest number in the array. But that's not quite right. See we don't actually care about the number itself we are counting digits for. We only care about it's digit count. Now I am not going to go through the proof for this part of the problem today but we can actually approximate the number of digits a number has to log(number) + 1. Since we assume worst case we have REALLY long numbers we can drop the constant 1. Therefore the final complexity becomes O(M x log(N)).

Space wise we just have 2 variables holding counts that dont grow with the array size. Thus we have O(1) space complexity.