CODEWITHSUNDEEP
algorithmmath
CodeHead
CodeHead

Reputation: 197

What is the most efficient to count trailing zeroes in an integer?

normal way is

int main(){
  int a=2000,count=0,temp;
  while(a!=0)
  {
    temp=a%10;
    if(temp==0) count++
    else break;
    a/=10;
  }
  printf("%d",count);
}

Is there a more efficient way ?

Upvotes: 3

Views: 2278

Answers (4)

orlp
orlp

Reputation: 117771

You can do it for any 64-bit number in 5 multiplications and a single binary trailing zero count:

pub fn trailing_decimal_zeros(mut n: u64) -> u32 {
    if n == 0 { return 0; } // Or whatever you want, not really defined.

    let pow2 = n.trailing_zeros();
    let mut pow5 = 0;
    let tmp = n.wrapping_mul(0xe4a4d1417cd9a041);
    if tmp <= 0x000000000734aca5 {
        n = tmp;
        pow5 += 16;
    }

    let tmp = n.wrapping_mul(0xc767074b22e90e21);
    if tmp <= 0x00002af31dc46118 {
        n = tmp;
        pow5 += 8;
    }

    let tmp = n.wrapping_mul(0xd288ce703afb7e91);
    if tmp <= 0x0068db8bac710cb2 {
        n = tmp;
        pow5 += 4;
    }

    let tmp = n.wrapping_mul(0x8f5c28f5c28f5c29);
    if tmp <= 0x0a3d70a3d70a3d70 {
        n = tmp;
        pow5 += 2;
    }

    let tmp = n.wrapping_mul(0xcccccccccccccccd);
    if tmp <= 0x3333333333333333 {
        pow5 += 1;
    }

    pow2.min(pow5)
}

I generated the magic constants using my answer here for a fast divisibility check. The multiplicative constants are modinv(5^k, 2^64), which means when the check succeeds the multiplication actually computed the division.

Upvotes: 1

Karthik
Karthik

Reputation: 5040

You can adapt the idea of Binary search here. May be it's difficult to code but it's an idea (as you have asked for most efficient way, I am just presenting this idea).

I am not just talking about 32-bit integer or 64 bit integer.

This works very well when the number of 0's are high otherwise also it should be efficient.

Say your number is n.

First check if n%(10^1) == 0 if yes

then check for n%(10^2) == 0 if yes

then check for n%(10^4) == 0 if yes the 10^8 ....10^16. I think you got the idea.

So finally you will get a point where n % 10^(2x) !=0, and now you know that no. of 0's are between x and 2x.

So again do a binary search starting with x, x+1 ,x+2 ....till you don't find the case where n % 10^(2y) != 0 (x < y <= 2x). Repeat the same process.

The time complexity would be (if you have K 0's) :

Best case will be : 

    O(logK)

Worst case will be:

     ceil(log(K)) + ceil(log(k/2)) + ..... 1 = ~ O(logK)

Upvotes: 3

samgak
samgak

Reputation: 24427

For a 32-bit integer (maximum value 2147483647) you only need a maximum of 4 tests. For 64 bits add one more with a test for 16 zeros.

Start with the larger powers of 10 and work down:

int countTrailingZeros(int n)
{
    int zeros = 0;
    if((n % 100000000) == 0)
    {
        zeros += 8;
        n /= 100000000;
    }
    if((n % 10000) == 0)
    {
        zeros += 4;
        n /= 10000;
    }
    if((n % 100) == 0)
    {
        zeros += 2;
        n /= 100;
    }
    if((n % 10) == 0)
    {
        zeros++;
    }
    return zeros;
}

This has a better worst-case performance, but if 9/10ths of the numbers you pass it have no trailing zeros then the average case is worse. It just depends on what values you are passing to it in the typical case.

However, if 9/10ths of the numbers you pass it have no trailing zeros then you probably shouldn't worry about optimizing your original code in the first place since it will break in the first iteration of your loop 90% of the time.

Upvotes: 7

Petr
Petr

Reputation: 9997

At least you speed this up by having only one divison per zero:

c = 1;
while (a % c == 0) {
    c *= 10;
    cout ++;
}

(probably you will also have to accurately process case when *=10 overflows).

This is still the same complexity. However, for ints I doubt that you need any better complexity, as the maximal possible number of zeros is very small.

Upvotes: 2

Related Questions