Wed
04
Oct 2017

I was recently asked a test question to write a function that would check whether a given integer number is a power of ten. I didn't know the answer immediately because I never solved this puzzle before, so I needed to think about a solution. I quickly came to a conclusion that there are many possible solutions, so I later decided to write them down and share with you.

Number is a power of 10 if it's equal to 10, 100, 1000 etc. 1 is also 0-th power of 10. Other numbers like 2, 3, 11, 12 etc. are not powers of 10. 0 and all negative numbers should also be rejected.

Below you can find 5 different solutions - all of them correct, but some of them more efficient than others. Example code is in C, but you can easily implement the same algorithms in Java or any other programming language.

First thing that came to my mind was to convert the number to a string and check whether it contains '1' followed by '0'-s.

int IsLog10_v1(int32_t x)
{
    // Convert x to string.
    char buf[12];
    itoa(x, buf, 10);
    const size_t bufLen = strlen(buf);

    // Check if string contains '1' followed by '0'-s.
    if(buf[0] != '1')
        return 0;
    for(size_t i = 1; i < bufLen; ++i)
    {
        if(buf[i] != '0')
            return 0;
    }
    return 1;
}

Another option is to convert the number to floating-point format, use "real" log10 function, and check if the result is an integer. Note that double must be used here, because float has too small precision and would incorrectly return 1 for inputs like: 999999999, 1000000001.

int IsLog10_v2(int32_t x)
{
    // Convert x to double. Calculate log10 of it.
    double x_d = (double)x;
    double x_log10 = log10(x_d);
    // Check if result is integer number - has zero fractional part.
    return x_log10 - floor(x_log10) == 0.0;
}

If we want to operate on integer numbers only, we may come up with a recursive algorithm that checks whether the number is greater than zero, divisible by 10 and then calls the same function for x/10.

int IsLog10_v3(int32_t x)
{
    if(x <= 0)
        return 0;
    if(x == 1)
        return 1;
    if(x % 10 != 0)
        return 0;
    // Recursion.
    return IsLog10_v3(x / 10);
}

Because it's a tail recursion, it's easy to convert it to iterative algorithm (use loop instead of recursive call).

int IsLog10_v4(int32_t x)
{
    if(x <= 0)
        return 0;
    // Same algorithm as v3, but converted from recursion to loop.
    for(;;)
    {
        if(x == 1)
            return 1;
        if(x % 10 != 0)
            return 0;
        x /= 10;
    }
}

Finally, the most efficient solution is to notice that there are only few possible powers of 10 in the range of 32-bit integers, so we can just enumerate them all.

int IsLog10_v5(int32_t x)
{
    // Just enumerate all possible results.
    return
        x == 1 ||
        x == 10 ||
        x == 100 ||
        x == 1000 ||
        x == 10000 ||
        x == 100000 ||
        x == 1000000 ||
        x == 10000000 ||
        x == 100000000 ||
        x == 1000000000;
}

You can find full source code as a simple, complete C program together with tests on my GitHub, as file: IsLog10.c.

Comments | #c #algorithms Share

Comments