2
$\begingroup$

$F_4(X)$ be the number of digits 4 in the decimal representation of $X$, and $F_7(X)$ be the number of digits 7 in the decimal representation of $X$. We have to find largest product $F_4(X)\cdot F_7(X)$, where $L \leq X \leq R$.

$\max\{F_4(X)\cdot F_7(X) : L ≤ X ≤ R\}$

can a general solution be acheived?

eg:

$L=47$ AND $R=74$

$\max\{F_4(X)\cdot F_7(X)\}=1$

  • 0
    the range is 1 ≤ L ≤ R ≤ 10^18 and x is simple interger2012-06-06

1 Answers 1

1

For any range with a fixed number of unrestricted digits like $0 \le X \le 99999999$, the problem is trivial: since we can choose any 8 digits, it is easy to maximize $F_4(X) \cdot F_7(X)$ by choosing four 4's and four 7's.

Even if some initial digits are unchangeable, as in $4440000 \le X \le 4449999$, the problem is very simple. Here, the first 3 digits are fixed, but the last 4 digits may be chosen at will, and it is easy to see that we should additionally choose one/zero 4's and three/four 7's.

Finally, note that any range $L \le X \le R$ can be decomposed into $O(\log R)$ separate intervals of the type in the previous paragraph. For instance, if $47 \le X \le 74$, then $X$ fits one of the following templates: 47, 48, 49, 5x, 6x, 70, 71, 72, 73, 74. Since we can maximize over each one, we can maximize over their union.

Of course some optimizations are possible, but this is already an linear-time algorithm in the number of digits of $L$ and $R$. One could even use this technique to compute things like $\sum\limits_{L \le X \le R} F_4(X) \cdot F_7(X)$.