PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
It is well-known that the sum of any range Sum[l; r] can be rewritten in form Sum[0; r]-Sum[0; l-1]. Let Sum4[i] is the total number of digits 4 in all numbers from 1 to i, inclusive, and Sum7[i] is the total number of digits 7 in all numbers from 1 to i, inclusive. We need to find the number of such pairs (l; r) that 1 <= l <= r <= N and Sum4[r]-Sum4[l-1] = Sum7[r]-Sum7[l-1]. Rewrite it in this way: Sum4[l-1]-Sum7[l-1] = Sum4[r]-Sum7[r]. We can iterate through all r from 1 to N, and for each r we need to know the number of correct l indexes. Let S = Sum4[r]-Sum7[r] for some current r. We need to find the number of such l (l <= r) that Sum4[l-1]-Sum7[l-1] = S. Since we are iterating r through all numbers from 1 to N, we can handle some array C[i], where C[i] is current number of such l that Sum4[l]-Sum7[l] = i. In each iteration of r, we add to the result number C[Sum4 [r]-Sum7[r]], and then increment C[Sum4[r]-Sum7[r]] by 1. In general this array can has negative indexes so if your programming language does not support arbitrary indexation you should make some tricks. But it can be proven that Sum4[r]-Sum7[r] is always non-negative so you can use usual array for this. Also it is useful to handle arrays Cnt4[i] and Cnt7[i] where Cnt4[i] is the number of fours of decimal representation of i and similar definition is for Cnt7[i]. Then Cnt4[i] can be calculated in O(1) time from Cnt4[i/10]. Thus the total complexity of such algorithm is O(N) for one query. But, you can precompute results for all numbers from 1 to 105 and store them in some array. That gives O(1) complexity for each query.
And here is some example: test case for N = 10.
| i | Sum4[i] | Sum7[i] | Sum4[i]-Sum7[i] | C[-1] | C[0] | C[1] | Result |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 2 | 0 | 1 |
| 2 | 0 | 0 | 0 | 0 | 3 | 0 | 3 |
| 3 | 0 | 0 | 0 | 0 | 4 | 0 | 6 |
| 4 | 1 | 0 | 1 | 0 | 4 | 1 | 6 |
| 5 | 1 | 0 | 1 | 0 | 4 | 2 | 7 |
| 6 | 1 | 0 | 1 | 0 | 4 | 3 | 9 |
| 7 | 1 | 1 | 0 | 0 | 5 | 3 | 13 |
| 8 | 1 | 1 | 0 | 0 | 6 | 3 | 18 |
| 9 | 1 | 1 | 0 | 0 | 7 | 3 | 24 |
| 10 | 1 | 1 | 0 | 0 | 8 | 3 | 31 |
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.
