0
$\begingroup$

Let $P(x)$ be the total number of digits '$4$' in the number $x$.

For instance:

$X= 19$: $P(19)=0$ since $19$ does not contain any digit $4$

$X=1234$: $P(1243)=1$

$X=441240$: $P(441270)=3$

$X=4444211344$: $P(44424211344)=6$

$X=12367$: $P(12367)=0$

Similarly, let $Q(x)$ be the total number of digits '$7$' in the number $x$.

For example:

$X=765217$: $Q(x)=2$

$X=12378$: $Q(x)=1$

$X=777777444477$: $Q(x)=8$

We are given the two values $A$ and $B$.We have to find

$\max(P(x) * Q(x) :: A \leq X \leq B)$

Example 1:

A= 1 B=100

(MAX(P(x) * Q(x) :: A <= X <= B) is Answer=1.

Note:

{Acheived at X=47}

Note It is also achieved when Value of X is following:

X=47

X=74

Example 2.

A= 51 B=1000

(MAX(P(x) * Q(x) :: A <= X <= B) is Answer=2.

Note:

{Acheived at X=447}

Note It is also achieved when Value of X is following:

X=447

X=474

X=477

X=744

X=747

X=774

Example 3:

A= 4123 B=9432

(MAX(P(x) * Q(x) :: A <= X <= B) is Answer=4.

Note:

{Acheived at X=4477}

Note It is also achieved when Value of X is following:

X=4477

X=4747

X=4774

X=7447

X=7474

X=7744

Example 4:

A= 2222 B=2400

(MAX(P(x) * Q(x) :: A <= X <= B) is Answer=1.

Note:

{Acheived at X=2247}

Note

It is also achieved when Value of X is following:

X=2247

X=2274

X=2347

X=2374

Note : We just need to calculate the maximum product ie.Answer is the maximum product .

No need to calculate at what value of x it occurs .

Also ,Found this question while practising algorithm problems.

The constraint is Large

1 ≤ A ≤ B≤ 10^19

Tried brute force ,but it was indeed slow.So what is the efficient way Thanks!

  • 0
    You have the sum of two numbers ($P(X)+Q(X)$), which is the total number of digits in the number $x$ and you need to find the maximum value of their product.2012-06-02

3 Answers 3

2

It's easy enough for any particular $A$ and $B$ -- just stuff as many 4's and 7's into $X$ as there is room for, such that there are as close to equally many of each as you can manage.

A general formula is going to be very complex, though, because it has to account for the possibility that $A$ and $B$ are so close to each other that they fix some of the digits of $X$. And if so, one has to count how many of the fixed digits are 4's and 7's, which will look horrible when written out as algebra, even though it is very easy to do by eye.

2

Obviously, to maximize $P(x) \cdot Q(x)$, you will only use $4$s and $7$s in the decimal representation of $x$ (unless you cannot put a $4$ or $7$ there). Now, if $x$ has $n$ digits, how many $4$s and $7$s would you like? Well, if you pick, say, $k$ times a $4$, you can have at most $n-k$ times a $7$, so that $P(x) \cdot Q(x) \leq k \cdot (n - k)$. This value is maximized when $k = \frac{n}{2}$; if this is not obvious, try proving it!

So suppose $A, B$ are given. Then you should just try to put in as many $4$s and $7$s in $X$ as you can, and try to distribute them evenly. As already mentioned by Henning, finding a general formula is hard, but the approach should be clear. So with this approach, given $A$ and $B$, it should not be hard to find the maximum.

Edit: For the examples you give, the maximum should be easier to find. If $A = 1$ and $B = 10^n$, then large numbers will have $n$ digits. If $n = 2m$ is even, the maximum is achieved at $\underbrace{44\ldots44}_m\underbrace{77\ldots77}_m$ with value $m^2$. If $n = 2m+1$ is odd then the maximum is achieved at $\underbrace{44\ldots44}_m\underbrace{77\ldots77}_{m+1}$ with value $m(m+1)$.

2

First figure out the largest digit that you can actually turn into a $4$ or $7$, since anything earlier than that can be ignored (unless they're already $4$ or $7$). We have a total of $n$ digits that are/can be $4$s and $7$s. Let $b$ be the number of $4$s. $P(x)Q(x)=b(n-b)$ maximizing in terms of $b$, we find that the maximum of this product is achieved when $b=n/2$. So if $n$ is even, pick the same number of $4$s and $7$s. If n is odd, pick $n/2 \pm 1$ $4$s and the rest $7$s. If you cannot do this (e.g, $444436\leq X \leq 444490$), get as close as possible.