PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
This problem is solvable by dynamic programming method. But there exits simpler solution which works even for ranges [1; 10^100000].
It is well-known that in the problems like this Count(l, r) = Count(1, r) - Count(1, l-1), so we should create function Count(x) - the number of such i (i = 1…x) that F(i) is a lucky number. Let d be an array of digits of x (numeration starts from leftmost digit, string from 0). For example, d for x = 47501 is {4, 7, 5, 0, 1}. Now consider function Number(size) - the answer for suffix of d with size size and with prefix equal to corresponding prefix of d (for example, suffix of size 4 for 5475107 is 5107). Of course, the answer for the problem will be Number(|d|), where |d| is the number of digits of x. Now consider we need to calc Number(size). What digits we can place on position |d|-size? That are digits from 0 to d[|d|-size], inclusive. Why not d[|d|-size]+1? Because in that case number will be greater then current suffix of x, no matter what we place in next positions. What if we place there digit which is less then d[|d|-size]? Then we can place any digits in following positions! Let cnt be the number of lucky digits among digits d[0…|d|-size] (you may consider that we have placed some digit on position |d|-size which is less then d[|d|-size]). Then itearate through all lucky numbers from cnt to 1000 (let it be integer l), what is the number of numbers with given prefix (digits d[0…|d|-size]) and number of lucky digits equal to l, considering that the rest of digits we can place arbitrary. It is **C(size-1, l-cnt)Pow(2, l-cnt)Pow(8, size-1-(l-cnt)) (C(n, k) - Binomial coefficient, Pow(n, k) - n in k-th power). Wait, but why? Because C(size-1, l-cnt) is the number of ways to place exactly l-cnt lucky digits, Pow(2, l-cnt) is the number of ways to place either 4 or 7 to each such position, Pow(8, size-1-(l-cnt) is the number of ways to place unlucky digits (0, 1, 2, 3, 5, 6, 8, 9) in the rest of the positions. That was in case if we place digit less then d[|d|-size] on position |d|-size, What if place d[|d|-size] there? Then we just need to calculate Number(size-1), because our prefix increases and suffix decreases, so we can just go to Number(size-1). Of course, Number(0) is 1 if x contains lucky number of lucky digits, 0 otherwise.
What is the comlexity of such algorithm? It is O(|d|), but you also need to calc C(n, k) for 1 <= n <= 10^3, which gives complexity O(|d|*|d|). There is the way of computing C(n, k) in O(1), in this case the complexity is O(|d|) (read setter’s solution for further details).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.