Problem LinkAuthor: Ivan Safonov Tester: Hasan Jaddouh Editorialist: Bhuvnesh Jain DifficultyCAKEWALK PrerequisitesPrefix sums ProblemYou are given to integers $L$ and $R$. Find the number of integers which have the last digit as $2$, $3$ or $9$ and lie in the range $[L, R]$. ExplanationAs the constrainsts are small on $L$ and $R$, we can precalculate all good numbers. Then each test case just asks to find out how many good numbers lie within the given range. This can be easily answered using prefixsums. If you don't know about prefixsums, you can read it here. Basically the idea is the following: $$\sum_{i=l}^{i=r} A_i = \sum_{i=1}^{i=r} A_i  \sum_{i=1}^{i=l1} A_i$$ $$\sum_{i=l}^{i=r} A_i = \text{(Prefixsum at i=r)}  \text{(Prefixsum at i=l1)}$$ Below is a pseudocode for it:
The time complexity of the above approach will be $O(N + T)$, where $N = 100000$ is for precomputation and $T$ is for answering every test case in $O(1)$ using prefixsums. The space complexity of the above approach will be $O(N)$ for storing the prefix array of good elements. Bonus ProblemSolve the problem without any precomputation and in O(1) memory. Idea: Feel free to share your approach, if it was somewhat different. Time Complexity$O(N + T)$ Space Complexity$O(N)$ Solution Links
This question is marked "community wiki".
asked 25 Jun '18, 23:40

Its a simple Brute Force application. Amazed to see such a simple problem in LTIME61B. My code goes here...(in cpp).## Heading ##
link
This answer is marked "community wiki".
answered 01 Jul '18, 17:18

Since constraints were easy there was no need to define an array to hold good/pretty numbers. a simple brute force from l to r and checking the last digit would yield the same result. See my submission: https://www.codechef.com/viewsolution/19019309 Time Complexity: O(N) answered 30 Jun '18, 23:29
Wtf.. I wasted a lot of time on this question due to some connection issue and due to some problem with codechef IDE...
(01 Jul '18, 00:20)
I did O(1) space approach
(01 Jul '18, 00:22)
@l_returns Pro tip #1 (#nooffence) Never use codechef ide in short contest for testing soln. It will ~1 min to give verdict. And sometimes it also shows "Submission Limit Reached" . Alternative offline ide(Best Option), CodeForces Ide (A bit slower but can be used) both are relatively faster. I personally use these options for testing purpose.
(01 Jul '18, 01:02)

My Solution: Time Complexity : O(T) Space Complexity : O(1) It will be useful if no. of test case is quite large. / Written By : Anish Ray / include <bits stdc++.h="">define ll long longdefine v(k) vector <k>define mod 1000000007define m(a,b) map <a,b>define ull unsigned long longdefine fi firstdefine se secondusing namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
} answered 01 Jul '18, 12:18
