CODEWITHSUNDEEP
c++algorithm
VGigs
VGigs

Reputation: 57

Efficient algorithm for getting the largest power of 10 which can divide an integer

I want to find the largest power of 10 that can divide a given integer.

I have a simplistic implementation for now

int factorBase10Exp(int number){
//...
int mBase10Exp = 0;
while(number%10 == 0 && number != 0)
    {
        number /= 10; mBase10Exp++;
    }
//...
return mBase10Exp;
}

The expected output is

factorBase10Exp(3000) = 3
factorBase10Exp(333) = 0

I can't use std::log10 as log10(333) = 2.522, which would give incorrect results in my use case.

What can I do to make this more efficient?

Upvotes: 1

Views: 946

Answers (2)

Cantfindname
Cantfindname

Reputation: 2138

So, you actually want to measure how many zeros are in the end of your number when written in decimal form. If you can find an fast algorithm to convert your number to string, you can then just count zeros.

Upvotes: 2

Mark Ransom
Mark Ransom

Reputation: 308130

You can use a series of divisions, each one with half as many digits as the one prior. This gives you a kind of binary search on the number of zeros.

if (number % 100000000 == 0)
{
    number /= 100000000;
    mBase10Exp += 8;
}
if (number % 10000 == 0)
{
    number /= 10000;
    mBase10Exp += 4;
}
if (number % 100 == 0)
{
    number /= 100;
    mBase10Exp += 2;
}
if (number % 10 == 0)
{
    number /= 10;
    mBase10Exp++;
}

The first division needs to be large enough to cover over half of the largest power of 10 your integer will hold.

Upvotes: 5

Related Questions