You 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].
Explanation
As the constrainsts are small on L and R, we can pre-calculate 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 prefix-sums. If you donāt know about prefix-sums, you can read it here. Basically the idea is the following:
\sum_{i=l}^{i=r} A_i = \text{(Prefix-sum at i=r)} - \text{(Prefix-sum at i=l-1)}
Below is a pseudo-code for it:
def init():
for i in [1, 1000000]:
last_digit = i % 10
if last_digit == 2 or last_digit == 3 or last_digit == 9:
good[i] = 1
else:
good[i] = 0
# Build prefix sum
for i in [1, 1000000]:
good[i] += good[i-1]
def solve(l, r):
ans = good[r] - good[l-1]
return ans
The time complexity of the above approach will be O(N + T), where N = 100000 is for pre-computation and T is for answering every test case in O(1) using prefix-sums. The space complexity of the above approach will be O(N) for storing the prefix array of good elements.
Bonus Problem
Solve the problem without any pre-computation and in O(1) memory.
Idea:
Click to view
Note that every consecutive number from āxā¦0ā to āxā¦9ā has 3 good numbers.
Feel free to share your approach, if it was somewhat different.
Wtfā¦ I wasted a lot of time on this question due to some connection issue and due to some problem with codechef IDEā¦
Didnāt knew that 1st question is that low in div2 (as I was in div2 before contest and I was in div1 before previous contest)ā¦
This is completely brute Forceā¦
how many of (2,3,9) ending numbers are present between L and next round figure (multiple of 10)
how many of (2,3,9) ending numbers are present between R and previous round figure(multiple of 10)
find the difference between these two round figures and divide by 10 and multiply by 3 (because there are 3 possibilites for each 0-10, 10-20, 20-30 etcā¦)
sum of all the counts from above 3 steps gives the answer.
Hi I am beginner. Why am I getting partially solved mark for this question? If my code is not right for all test cases where can I get those test cases to test on different IDE?
A little help please
Thanks in advance!
I did it in O(1) time complexity and O(1) space complexity
No Loops Broā¦,I liked it
void solve(){
int l,r;cin>>l>>r;l--;
int a1=(r/10)*3;
int a2=(l/10)*3;
r=r%10;l=l%10;
if(r>1)a1++;if(r>2)a1++;if(r==9)a1++;
if(l>1)a2++;if(l>2)a2++;if(l==9)a2++;
cout<<a1-a2<<endl;
}
what is wrong with my code https://www.codechef.com/viewsolution/36882644
my approach is for example l=12 and r =33
then l=l-1 mean l=11( because range is inclusive )
now lx =l%10 and rx =r%10
lx =1 and rx=3
now for get no of magical no l=( l/10*2 )and r =( r/10)*3
if lx>1 then add 1 if lx>2 and 1 and i lx>8 add 1
same for y
we get r=11 and l=3
finaly answer = r-l
11-3 =8 which is right
it is showing wa
int t, rem, count = 0;
cin >> t;
while (t--)
{
int l, r;
cin >> l >> r;
for (int i = l; i <= r; i++)
{
rem = i % 10;
if (rem == 2 || rem == 3 || rem == 9)
{
count++;
}
}
cout << count << "\n";
}
return 0;
final = []
for _ in range(int(input())):
s,e = map(int,input().split())
count=0
for i in range(s,e+1):
if(i%10==2 or i%10==3 or i%10==9):
count+=1
final.append(count)
for times in final:
print(times)
Well, if you have the spare time to do it that wayā¦ but better to just calculate how many whole tens (which each have three pretty numbers) and tidy up the edges:
fav = (2,3,9)
T = int(input())
for tx in range(T):
L, R = map(int, input().split())
Lten, Lunit = divmod(L,10)
Rten, Runit = divmod(R,10)
if Lten == Rten:
ct = sum(i in fav for i in range(Lunit, Runit+1))
else:
ct = (3*(Rten-Lten-1)
+ sum(i in fav for i in range(Lunit, 10))
+ sum(i in fav for i in range(0, Runit+1)))
print(ct)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(tā)
{
int l,r;
cin>>l>>r;
int l0=l/10;
int r0=r/10;
int final=0;
final=(r0-l0)*3;
int lr=l%10;
int rr=r%10;
int count=0;
if(lr>1)
countā;
if(lr>2)
countā;
if(lr==9)
countā;
if(rr>1)
count++;
if(rr>2)
count++;
if(rr==9)
count++;
cout<<final+count<<endl;
}
} not working please help
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(tā)
{
int l,r;
cin>>l>>r;
int l0=l/10;
int r0=r/10;
int final=0;
final=(r0-l0)*3;
int lr=l%10;
int rr=r%10;
int count=0;
if(lr>1)
countā;
if(lr>2)
countā;
if(lr==9)
countā;
if(rr>1)
count++;
if(rr>2)
count++;
if(rr==9)
count++;
cout<<final+count<<endl;
}
}