2
$\begingroup$

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!

$\endgroup$

closed as off-topic by Rohan Shinde, Did, JonMark Perry, Parcly Taxel, Namaste Mar 7 '18 at 22:05

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Rohan Shinde, Did, JonMark Perry, Parcly Taxel, Namaste
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Step 1: Figure out how to tell by just looking at what digits appear (instead of actually multiplying them and looking at the result). Step 2: Organize all numbers satisfying the criterium you found in step 1 into sets which are easy to count. Step 3: Count them. $\endgroup$ – Arthur Mar 7 '18 at 8:21
  • $\begingroup$ @Arthur Yes, but what you said is too general. The critical part is how to organize all numbers into sets. And I haven't found a simple way to organize all numbers into sets for this question. Thus I post it here for ideas. $\endgroup$ – Daniel Mar 7 '18 at 9:09
  • $\begingroup$ Why downvoting? $\endgroup$ – Daniel Mar 7 '18 at 9:13
  • $\begingroup$ You're (probably) receiving downvotes and close votes because you haven't told us that you have already done this. Had you said "I know that the product of digits ends in five zeroes if and only if the number has so-and-so digits in it, but I don't know how to partition those numbers to make them easy to count" in the question post in the first place, it would've been better received. Also, note that interview questions aren't all about whether you can solve them, but also whether you attack a new problem in a constructive manner. I would actually think that the latter part is more important. $\endgroup$ – Arthur Mar 7 '18 at 9:13
  • $\begingroup$ @Arthur Thank you. I understand now. I will demonstrate more details on what I have done. $\endgroup$ – Daniel Mar 7 '18 at 9:15
0
$\begingroup$

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!

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.