PROBLEM LINKS:
DIFFICULTY:
Easy
PREREQUISITES:
Ad-hoc
QUICK EXPLANATION:
To make sure that we get a number between L and R, we need to retain all the digits starting from the most significant digit which are equal in both L and R as long as we find a difference in the digits of any corresponding position. Next we try to fill the remaining positions using only 4’s and 7’s. But before that we need to ensure that we keep the number being formed less than R and greater than L. Note that it can be equal to either of them. It’s enough if we ensure this condition at a single digit position. For example, L=144239 and R=144880. For this, if we for a number X=1445??, we have already ensured that it is between L and R and hence we can fill the other ?'s using 4’s and 7’s. Suppose we form the number like X=1442??, then it’s still not ensured that L<=X<=R. Hence this has to be taken care in one of the next positions. Similarly X=1448?? is not ensured to be in between.
Once you ensure that it lies in between, we can fill all the lesser significant positions using any combination of 4’s and 7’s. We choose the combination for which the product is maximum.
DETAILED EXPLANATION:
Tip :
In this example we’ll treat numbers as an array of digits with the most significant digit having the highest index. For example, if the number is 45382 consider it to be an array like the following:
index : 0 1 2 3 4
digit : 2 8 3 5 4
The problem requires you to find a number between L and R for which F4(x) * F7(x) is maximum. Let us try to find a number between L and R first.
To do that, let’s make both the numbers of equal length by appending 0’s to the smaller number(if required). For example, if you have L=238 and R=1209, append a single ‘0’ to L to make it 0238. Now, both L and R are of length 4. Next, we try to find the first position where both the numbers differ, starting from the most significant digit. Let’s call that position ‘i’. Obviously, L[i] < R[i]. As we keep checking for the difference in both the numbers, we count the number of 4’s (n4) and 7’s (n7) encountered so far. If i<0, this means both the numbers are same and our answer is n4*n7.
Now we can find a number between L and R in the following way. Suppose the number is X. And let X[y] denote the yth digit of X. Keep every digit in X from most significant position to i+1 same as that of L and R.
For example, L = 410327 and R = 410989. Here i=2 becase L[k] = R[k] for k > 2
index : 5 4 3 2 1 0
L : 4 1 0 3 2 7
R : 4 1 0 9 8 9
X : 4 1 0 ? ? ?
Let’s divide the numbers into 3 categories:
-
The number has it’s digit at
position i between L[i] and R[i]
i.e. L[i] < X[i] < R[i] -
The number has it’s digit at
position i equal to L[i] i.e. X[i] =
L[i] -
The number has it’s digit at
position i equal to R[i] i.e. X[i] =
R[i]
Let’s discuss case 1 first. L[i] < X[i] < R[i] ensures that no matter what, X will always be in between L and R. So we try to maximize the product of n4 and n7 by filling the lesser significant digits(i.e. Digits at positions < i ) using only 4’s and 7’s. We already have n4 4’s and n7 7’s. So we try out filling all the remaining i positions using s4 4’s and s7 7’s such that s4 + s7 = i. Also, if X[i] is 4 or 7, add it to corresponding count (either n4 or n7). Now we try out all different combinations for which s4 + s7 = i and look for the one for which (s4+n4) * (s7+n7) is maximum. This can be done easily by looping from j=0 to i-1 and considering that there are j 4’s and (i - j) 7’s in the remaining digits of x. For example, in the above given case, we can have X[i] = 4/5/6/7. And the rest two digits i.e. X1 and X[0] can be 44,47,74 and 77 so as to maximize the products.
Next we come to case 2 i.e. X[i] = L[i]. To get a number between, L and R, we can do the following:
X[j] = L[j] for j=i to k. Then, to make X larger than L, we have L[k-1] < X[k-1]. Now we have the same case as 1 with ‘i’ modified to k-1. We apply the same method and try to maximize the product. But here, we need to do it for every possible ‘k’ i.e. from i to 0.
In the case 3, we have X[i] = R[i]. To get a number between, L and R, we can do the following:
X[j] = R[j] for j=i to k. And to have X smaller than R, we have X[k-1] < R[k-1]. Then proceed as case 1. Again, we would have to try out for all possible k i.e. from i to 0.
The maximum out of all the three cases will be our final answer.
Let’s take a look at the complexity of the solution. Let N be the length of R.
Case 1 takes atmost N * B operations where B is the number of digits in base 10 i.e. 10.
Case 2 & 3 both have to do the same N*B operations as mentioned above. But these operations have to be repeated for different ‘k’ which in the worst case will be N. Thus there will be total of NNB operations.
Hence, the complexity of the solution is O(T * N * N * B).
This solution can be improved in the following manner:
In the existing solution, we can observe that given n4, n7 and i, we were calculating the maximum possible product by trying to replace every digit at index less than i with either 4 OR 7. Let’s call this value f(n4, n7, i). Instead of looping over for all values between 0 to i, the function can give the same results if modified in the following manner:
int f(int n4,int n7,int i) {
int k=(n7+i-n4)/2;
if(k*(i-k)>=0) return (n4+k)*(n7+i-k);
k++;
if(k*(i-k)<=0) return (n4+k)*(n7+i-k);
return max((n4+i)*n7,n4*(n7+i));
}
This function does the same job in O(1) time rather than O(i) time. To understand this lets consider that there are k 4’s and (i-k) 7’s in the remaining i positions. Then the product *F4(x)F7(x) will be (n4+k) * (n7+(i-k)).
This is a quadratic equation in k. Hence the only possible points where the value can be maximum is when k=(i+n7-n4)/2 or at the end points i.e. K=0 or k=i. Hence this can be calculated in O(1) now.
A futher optimization can be to precalculate the values for given n4, n7 and i for every pair of L and R i.e. precalculating f(L,R,n4,n7,i) in the following way:
int F (int L, int R, int n4, int n7, int i) {
if(L>R) return 0;
int ans=F(n4, n7, i);
if(L<=4 && 4<=R)
MAX(ans,F(n4+1, n7, i));
if(L<=7 && 7<=R)
MAX(ans,F(n4, n7+1, i));
return ans;
}
The function is quite easy to understand.
Using the above 2 optimizations, we can get a much efficient solution.
SETTER’S SOLUTION:
Will be updated soon.
APPROACH:
The problem setter used the above approach in his solution.
TESTER’S SOLUTION:
Can be viewed here.
APPROACH:
The problem setter used the above approach in his solution.
