Explanation

$l = 1$

Let's start with an example: $l = 1$ and $r = 875$. Observe that we really need to consider three numbers as viable answers: $875$, $799$, and $869$. Try to think about why, and how this generalizes!

$l \neq 1$

We can apply a very similar approach when $l \neq 1$. In fact, it's almost identical, with one minor difference. Consider the case where $l = 855$ and $r = 875$, just as before. The only difference is we can no longer consider $799$ as a viable answer, as it is less than $l$. Again, try to think about how to generalize this!

Implementation

Time Complexity: $\mathcal{O}(D^2)$, where $D$ is the maximum number of digits (19).

Copy
#include <bits/stdc++.h>
using ll = long long;
using namespace std;

/** @return the product of the given string's digits (-1 if empty) */
ll prod(string s) {
	// remove leading zeros
	int i = 0;
	while (s[i] == '0') { i++; }
	s = s.substr(i);