Counting the number of digits in a number - which of these two solutions is faster?

Question

I was asked in an interview recently how would I write an algorithm to count the number of digits in a given number. So for example if I was given a number 500 the result would be 3. If I was given a number 15345 the result would be 5.

I came up with 2 possible solutions:

1. Recursively divide the number by 10 until the result is less than 1 and then return the count of recursions I made.

2. Convert the number to string and then count the number of elements in this string.

Then I was asked which operation is more efficient when working with extremely large numbers and I couldn't give a good answer. So my question is what is the correct answer here - which algorithm is faster and why?

Answer 1

Well, to convert an integer to a string, the basic itoa (integer to string) function works somewhat like this:

result = ""
while (number > 0)
{
    digit = number % 10
    append digit to result
    number = number / 10
}

So, there isn't that much of a difference between your first and your second solution. The first solution will take O(n) iterations, where n is the number of digits in the integer. The second solution will have the same complexity, and additionally count the n digits in the string in O(n) time, for a total of O(2n) = O(n) complexity.

Other algorithms are possible. For example, you might take a look at the highest bits that are set, and match those against a table of values.

Answer 2

I timed three variants:

• repeated division
• logarithm
• string length

for lengths of multiples of 10. I ran 10000 runs of each.

Results in microseconds:

length     division     logarithm     string length
---------------------------------------------------
  10           7           10            16
  20          14           14            26
  30          28           14            41
  40          46           14            59
  50          73           14            80
  60          91           14            80
  70         113           14            98
  80         136           14           106
  90         170           14           116
 100         197           14           129

There are artifacts of various origin in these data, but I think you get the idea.

Answer 3

It much depends on how numbers are given. I would interpret that you are given a number stored as a machine integer. In that case I think that best of all would be taking the logarithm of the number, which should give the answer in constant time.

Both your answers run in linear time, so they should be considered equivalent.

Answer 4

Just for the record, this is the fastest way to do this, assuming the input is an unsigned long or int of some kind:

int count_digits( unsigned long n ){
   unsigned long long quotient;
   unsigned int ctDigits = 1;
   while( n > 9 ){
      ctDigits++;
      quotient = (n >> 1) + (n >> 2);
      quotient += (quotient >> 4);   
      quotient += (quotient >> 8);   
      quotient += (quotient >> 16);   
      quotient = quotient >> 3;   
      n -= ((quotient << 2) + quotient) << 1; // computes the remainder
   }
   return ctDigits;
}

Any solution that uses division (which includes any itoa/string conversion) will be a lot slower because division is an expensive operation. In the world of high-speed computation division is a bad, bad thing.