CODEWITHSUNDEEP
algorithm
Rishabh
Rishabh

Reputation:

Fastest way to check if a number has the 'digit' zero anywhere in it?

What is the fastest way to check if a number has the digit '0' anywhere in it?

I need to develop a fast method since i have to perform these checks for close to $10^9$ numbers in under $20$ seconds.

Would searching for a zero after converting it into a string work?

Upvotes: 3

Views: 3628

Answers (5)

Fred Daniel Kline
Fred Daniel Kline

Reputation: 111

Here is some Mathematica code that makes one divide per digit in the number.

n = 34560116; d = IntegerLength[n]; m = 0; x = 1;  
While[d >= x, If[m == (k = Mod[n, 10^(x++)]), Break[], m = k]];
If[d >= x, Print["First zero found at: ", 10^(x - 2)]];

First zero found at: 1000

Upvotes: 0

johnnycrash
johnnycrash

Reputation:

Binary zeros: (~x) would be non zero if there were zero bits. My guess is you're not concerned with binary numbers.

If your data starts as strings, leave it that way. If not, DO NOT convert to strings and then check. The conversion to a string does more work than is necessary to detect a zero digit. This could be language specific. In c or assembly the conversion is going to be slower than your own detection algorithm.

For instance, if you had base 10 numbers stored as integers (as in c), you could make a lookup table with 1000 entries. Lookup[100] = 1, Lookup[123] = 0, etc. You would then have to divide your input numbers by 1000 instead of 10. The remainder is the lookup index. This might could go 3x faster than dividing by 10. A small lookup table would fit in cache. Too large of a table and you will get a performance loss due to ram being so slow. In c, unsigned ints might divide faster than signed ones, because the optimizer might be able to take some shortcuts.

Finally, consider multiple threads for this.

Upvotes: 1

Jeff Ferland
Jeff Ferland

Reputation: 18312

I need to develop a fast method since i have to perform these checks for close to 109 numbers in under 20 seconds.

Ah, programming question.

Would searching for a zero after converting it into a string work?

If everything you feed to the input is a number on its own line that has no leading or trailing zeroes, then /0/ does the trick. But yes, strings would be the fastest. For a more complicated representation with zeroes or non-numbers in the mix, then you'd use this regular expression for integers:

/^[1-9]+0[0-9]*$|^0$/

That requires a number that has a non-leading zero, or is the number zero. It also assumes integers.

$ cat numbers
    375
    391
    940
    493
    566
    804
    800
    453
    726
    527
    428
    77
    984
    510
    795
    077
    0

    $ egrep '^[1-9]+0[0-9]*$|^0$' numbers
940
804
800
510
0

Decimal numbers can be a bit more challenging if they're fixed-width. If not, adding a period with each of the two brackets should be enough unless your decimals start out '0.nnn' instead of '.nnn'. Tell me your numbers, I'll get you the right fix.

Upvotes: 0

mjqxxxx
mjqxxxx

Reputation:

Dividing by a number other than a power of $2$ is going to take the same number of operations regardless of what the number is. So instead of repeatedly dividing $x$ by $10$ and testing each remainder against $0$, consider repeatedly dividing $x$ by $10^6$ (say) and testing each remainder against a lookup table on $[0, 10^6)$. The lookup table should say "yes" if the remainder contains an internal zero, "no" if it contains no zeros, and "maybe" if the remainder has only initial zeroes (in which case check whether $x$ is currently nonzero and return "yes" or "no" accordingly).

Upvotes: 14

robjohn
robjohn

Reputation: 111

If you can write assembly or force your compiler to do integer division, repeatedly perform integer divisions by $10$, until either a remainder is $0$ or the dividend is $0$. If it was a remainder, there is a "$0$" digit. If it was the dividend, there is no "$0$" digit.

Upvotes: 1

Related Questions