Among all 10 digit numbers, how many are there satisfying that the product of all digits ends in at least 5 zeros?

Question

For example, 2222255555 and 5324855555 are both such numbers. By the way, this is an interview question, and thus I think there should be a not-too-complicated way to count it.

I'm sorry for that I didn't put what I've done here. Here is my thought for this problem:

Since the product ends in at least 5 zeros, the factorization of the product should contain at least $2^5 \times 5^5$, and each digit of the number shouldn't be zero. That's our starting point. Let's first consider there are exactly 5 fives in the number, and the remaining 5 digits should contain at least $2^5$. And the first case is that if all 5 digits are multiples of 2 (can be 2,4,6, or 8), the number of these numbers is ${10\choose 5}\times 4^5$. The second case is that if exactly 4 of the 5 digits are multiples of 2. But I'm stuck here, and can't find an easy way to continue my counting.

UPDATE:

I have provided a not-too-complicated way to solve this problem in the answer section, and also provide computer programs to verify the correctness of my method there. Hope these help you, and any other different methods are very welcome!

Answer 1

I have just figured out a way to continue my counting as follows:

(A) When there are exactly five 5s in the number, let's partition the remaining five digits into 4 cases:

(a.1) 5 of 5: These 5 digits are all multiples of 2, which can be 2, 6, 4, 8 (I sort them in ascending order of the power of 2). There are ${10 \choose 5,5}\times 4^5$ such numbers.

(a.2) 4 of 5: Exactly 4 of the 5 digits are multiples of 2, and the other digit can only be 1,3,7,9 (excluding 5). There are ${10\choose 5,4,1}\times (4^4-2^4) \times 4$ such numbers, where $2^4$ corresponds to only choosing 2 or 6 for the multiples of the 4 digits, which should be excluded. The last $\times 4$ corresponds to the 4 choices of the odd digit.

(a.3) 3 of 5: Exactly 3 of the 5 digits are multiples of 2. There are ${10\choose 5,3,2}\times (4^3-(2^3+3\times2^2)) \times 4^2$ such numbers, which is similar to the counting in (2).

(a.4) 2 of 5: Exactly 2 of the 5 digits are multiples of 2. There are ${10\choose 5,2,3}\times 3 \times4^3$ such numbers.

(B) When there are exactly six 5s in the number, we can get similar results:

(b.1) 4 of 4: ${10\choose 6,4}\times (4^4-2^4)$.

(b.2) 3 of 4: ${10\choose 6,3,1}\times (4^3-(2^3+3\times2^2))\times 4$.

(b.3) 2 of 4: ${10\choose 6,2,2}\times 3 \times4^2$.

(C) When there are exactly seven 5s in the number:

(c.1) 3 of 3: ${10\choose 7,3}\times (4^3-(2^3+3\times2^2))$.

(c.2) 2 of 3: ${10\choose 7,2,1}\times 3 \times4$.

(D) When there are exactly eight 5s in the number:

(d.1) 2 of 2: ${10\choose 8,2}\times 3$.

That's all. Systematic and not-too-complicated.

UPDATE:

I have just written a simple Python program to verify the correctness of my method as follows:

from sympy import multinomial_coefficients as mc

def partition():
    s = 0
    s += mc(2,10)[5,5] * 4**5
    s += mc(3,10)[5,4,1] * (4**4 - 2**4) * 4
    s += mc(3,10)[5,3,2] * (4**3 - 2**3 - 3 * 2**2) * 4**2
    s += mc(3,10)[5,2,3] * 3 * 4**3

    s += mc(2,10)[6,4] * (4**4 - 2**4)
    s += mc(3,10)[6,3,1] * (4**3 - 2**3 - 3 * 2**2) * 4
    s += mc(3,10)[6,2,2] * 3 * 4**2

    s += mc(2,10)[7,3] * (4**3 - 2**3 - 3 * 2**2)
    s += mc(3,10)[7,2,1] * 3 * 4

    s += mc(2,10)[8,2] * 3

    return s

def brute_force():
    current_number = [0 for _ in range(10)]
    index = 0
    n = 0
    while index >= 0:
        if index == 10:
            product = 1
            for i in current_number:
                product *= i
            if product % 100000 == 0:
                n += 1
                if n % 100 == 0: # print the current number every 100 times
                    print(current_number)
            index -= 1
        if current_number[index] == 9:
            current_number[index] = 0
            index -= 1
        else:
            current_number[index] += 1
            index += 1
    return n

if __name__ == '__main__':
    print(partition())
    print(brute_force())

And both functions will return the same number: $3994023$. FYI, because the Python version of the brute_force() function is really slow (it took about 53mins to finish on my laptop!), I also wrote it in Go programming language as follows for you to verify my method much more quickly (it took less than 1min!):

package main

import "fmt"

func brute_force() int {
    current_number := [10]int{}
    index := 0
    n := 0
    product := 1
    for index >= 0 {
        if index == 10 {
            for _, value := range current_number {
                product *= value
            }
            if product % 100000 == 0 {
                n += 1
                if n % 100000 == 0 { // print the current number every 100000 times
                    fmt.Println(current_number)
                }
            }
            product = 1
            index--
        }
        if current_number[index] == 9 {
            current_number[index] = 0
            index--
        } else {
            current_number[index] += 1
            index++
        }
    }
    return n
}

func main() {
    fmt.Println(brute_force())
}

Hope these help you!