SPyofgame's blog

By SPyofgame, history, 4 years ago, In English

The problem

Lets $$$f(x) = $$$ product of digits of $$$x$$$. Example: $$$f(123) = 1 * 2 * 3 = 6$$$, $$$f(990) = 9 * 9 * 0 = 0$$$, $$$f(1) = 1$$$

The statement is, given such limitation $$$N$$$, count the number of positive $$$x$$$ that $$$1 \leq x * f(x) \leq N$$$

Example: For $$$N = 20$$$, there are 5 valid numbers $$$1, 2, 3, 4, 11$$$



The limitation

  • Subtask 1: $$$N \leq 10^6$$$
  • Subtask 2: $$$N \leq 10^{10}$$$
  • Subtask 3: $$$N \leq 10^{14}$$$
  • Subtask 4:

    Unable to parse markup [type=CF_MATHJAX]



My approach for subtask 1

  • If $$$(x > N)$$$ or $$$(f(x) > N)$$$ then $$$(x * f(x) > N)$$$. So we will only care about $$$x \leq N$$$ that $$$x * f(x) \leq N$$$
Calculating x * f(x) - O(log10(x))
Counting - O(n log10(n))


My approach for subtask 2

  • If $$$x$$$ contains $$$0$$$ then $$$f(x) = 0 \Rightarrow x \times f(x) < 1$$$. We only care about such $$$x$$$ without $$$0$$$ digit
Building function - O(result + log10(n))


Here is the solution:

Let takes some $$$x$$$ satisfy $$$1 \leq x * f(x) \leq N$$$

We can easily prove that $$$f(x) \leq x$$$, and because $$$x * f(x) \leq N$$$, we have $$$f(x) \leq \sqrt{N}$$$ (notice that $$$x$$$ might bigger than $$$\sqrt{N}$$$)

Since $$$f(x)$$$ is product of digits of $$$x$$$, which can be obtain by such digits {$$$1, 2, \dots, 9$$$}. So $$$f(x) = 2^a \times 3^b \times 5^c \times 7^d$$$

So we can bruteforces all possible tuple of such $$$(a, b, c, d)$$$ satisfy ($$$P = 2^a \times 3^b \times 5^c \times 7^d \leq \sqrt{N}$$$). There are small amount of such tuples (493 tuples for $$$N = 10^9$$$ and 5914 tuples for $$$N = 10^{18}$$$)

Find all possible tuples - O(quartic_root(N))

For each tuples, we need to counting the numbers of such $$$x$$$ that $$$1 \leq x \times f(x) \leq N$$$ and $$$f(x) = P$$$.

  • We have the value $$$P$$$, so $$$\lceil \frac{1}{P} \rceil \leq x \leq \lfloor \frac{N}{P} \rfloor$$$.
  • We have the value $$$f(x) = P$$$, so $$$x$$$ can be made by digits having the product exactly $$$P$$$, so we can do some DP-digit

So now we have to solve this DP-digit problem: Calculate numbers of such $$$x$$$ ($$$L \leq x \leq R$$$) whose $$$f(x) = P$$$



Solving Subproblem

We try to build each digits by digits for $$$X$$$. Because $$$X \leq N$$$, so we have to build about $$$18$$$ digits.

Lets make a recursive function $$$magic(X, N, p2, p3, p5, p7)$$$

Lets make some definition
Notice that
Ugly precalculation code - O(1)
magic function - O(18*p2*p3*p5*p7)


About the proving stuff

1) $$$\forall x \in \mathbb{N}, f(x) \leq x$$$

  • Proof: $$$x = \overline{\dots dcba} = \dots + d \times 10^3 + c \times 10^2 + b \times 10^1 + a \times 10^0 \geq \dots \times d \times c \times b \times a = f(x)$$$

2) If $$$x$$$ satisfy then $$$f(x) \leq \sqrt{N}$$$ must be satisfied

  • Proof: $$$x \times f(x) \leq N \Rightarrow f(x) \times f(x) \leq N \Rightarrow f(x) \leq \sqrt{N}$$$

3) $$$\exists\ a, b, c, d \in \mathbb{N} \rightarrow f(x) = 2^a \times 3^b \times 5^c \times 7^d$$$

  • Since $$$x = \overline{\dots dcba} \Rightarrow (0 \leq \dots, d, c, b, a \leq 9)$$$ and $$$f(x) = \dots \times d \times c \times b \times a$$$

  • And we also have $$$\forall$$$ digit $$$v$$$ ($$$v \in \mathbb{N}, 0 \leq v \leq 9$$$) $$$\rightarrow \exists\ a, b, c, d \in \mathbb{N} \rightarrow v = 2^a \times 3^b \times 5^c \times 7^d$$$

  • And because $$$f(x)$$$ is the product of digits of $$$x$$$, hence the statement is correct

4) If we know $$$f(x)$$$ we can find such $$$x$$$ satisfy $$$x \in [L, R]$$$

  • Proof: Since $$$f(x)$$$ is created from factors of digits of $$$x$$$, so $$$x$$$ can also be generated using the factors

5) Number of tuples $$$(a, b, c, d)$$$ satisfy $$$P = 2^a \times 3^b \times 5^c \times 7^d \leq \sqrt{N}$$$ is very small

  • Lets $$$O(k(x)) = O(log_2(x) \times log_3(x) \times log_5(x) \times log_7(x))$$$

  • Since each value $$$x$$$ have the upper bound of $$$log_x(\sqrt{N})$$$. So the complexity is about $$$O(log_2(\sqrt{N}) \times log_3(\sqrt{N}) \times log_5(\sqrt{N}) \times log_7(\sqrt{N})) = O(k(\sqrt{N})) \leq O(log_2(\sqrt{N})^4)$$$

  • But actually for $$$R \leq 10^{18}$$$, the complexity is just about $$$O(k(\sqrt[4]{N}))$$$

Weak proof - N = 10^k
Weak proof - N = 2^k
Code


About the complexity:

  • $$$O(h(x)) = O(log_{10}(N))$$$ is number of digits we have to build
  • $$$O(k(x)) = O(log_2(N) \times log_3(N) \times log_5(N) \times log_7(N)) = O(log(N)^4)$$$ is product of all prime digits $$$p$$$ with its maximum power $$$k$$$ satisfy $$$p^k \leq N$$$
  • $$$O(g(x)) = O(k(\sqrt{N}))$$$ is number of such valid tuples, but for $$$1 \leq N \leq 10^{18}$$$ it is about $$$\approx O(k(\sqrt[4]{N})) \leq O(log_2^4{\sqrt[4]{N}})$$$
  • The space complexity is $$$O(SPACE) = O(h(x) \times k(x)) = O(log_2(N) \times log_3(N) \times log_5(N) \times log_7(N) \times log_{10}(N)) = O(log(N)^5)$$$
  • The time complexity is $$$O(TIME) = O(SPACE) + O(g(x) \times k(x)) \approx O(log(N)^4 \times log_2^4{\sqrt[4]{N}})$$$


Other

  • About the real complexity for $$$O(k(x))$$$, do you find a better/closer upper bound of counting such tuples of $$$(a, b, c, d \in \mathbb{N})$$$ that $$$P = 2^a \times 3^b \times 5^c \times 7^d \leq N$$$ ? Since my $$$O(log_2(N))$$$ complexity seem very far than the real counting and $$$O(log_2(\sqrt{N}))$$$ is closer but just correct for $$$N \leq 10^{18}$$$

  • Thanks for reading and sorry for updating this blog publicly so many times (most is for the proving path and correcting the complexity)

  • Vote: I like it
  • +63
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Not really sure, but isnt that f(x)<x, therefore we only need to consider f(x)<=sqrt(10^9)?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes your way is correct ^^, thank sir. I have just got accepted from the problem and I am writting the solution

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have just done the problem and wrote the solution, thanks for reading ^^

If you have a better explaination/implementation or better complexity, please comment in this post too ^^.

»
4 years ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

By the way, if you guys are interesting, here is the Vietnamese version of the problem where we need to count such valid numbers in range $$$[A..B]$$$ where $$$1 \leq A \leq B \leq 10^{18}$$$. And here is the Editorial in Vietnamese

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Wow, that's an amazing problem