Search code examples
ctime-complexitydigitslogarithm

Count number of digits - which method is most efficient?

There are more than one solution for finding the-number-of-digits in a given number.

For example:

Method-1:

int findn(int num)
{
    char snum[100];
    sprintf(snum, "%d", num);
    return strlen(snum);
}

Method-2:

int findn(int num)
{
    if (num == 0) return 1;
    int n = 0;
    while(num) {
        num /= 10;
        n++;
    }
    return n;
}

Method-3:

int findn(int num)
{
    /* math.h included */
    if (num == 0) return 1;
    return (int) log10(num) + 1;
}

The question is - what is the most efficient method? I know method-2 is O(n) but what about method-1 and method-3? How do I find the run-time complexity of library functions?

Solution

  • The following is even more efficient:

    int findn(int num)
{
   if ( num < 10 )
      return 1;
   if ( num < 100 )
      return 2;
   //continue until max int
}

    You could optimize this even further by doing a binary search, but that would be overkill.