Why is this facing issues? Please tell

#1

Why is this facing issues?
Please tell.

#2

Hey @cbcao263
K can be 10^12 so u can’t use it
Try to solve it in less time
Here is the hint :
say a=d0 and b=d1
then

d2 =(a+b) %10
d3= (2d2) %10
d4=(4d2) %10
d5=(8*d2) %10
d6=16%10 (d2) %10=(6d2) %10
d7=12%10 d2=(2d2)%10 and so on
Try to calculate sum in O(1) now

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#4

Sir, I have done this and it is showing this error

And I am not able to understand the logic.
Please help.

#5

Hey @cbcao263 Again u are doing the same mistake u cant run loop because K can be

You have to observe pattern and solve it in lesser time
Here di represents digit i
so d0=a and d1=b this is given
now
d2= (d0+d1)%10 = (a+b) %10
d3=(d2+d1+d0)%10 = (2*a+2*b)%10 =(2*d2)%10
d4=(d3+d2+d1+d0)%10 =(4*d2)%10
d5=(d4+d3+d2+d1+d0)%10=(8*d2)%10
d6=(d5+d4+d3+d2+d1+d0)%10 =(16*d2)%10 = (6*\d2)%10 //Because (a*b)%m=((a%m)*(b%m))%m
and so on
so u see
pattern in digits is
d0 d1 d2 2d2 4d2 8d2 6d2 2d2 4d2 8d2 6d2

Now add 3 terms in sum ,and for the rest take 4 terms at a time so sum will be
d0+d1+d2+ ((n-3)/4)*(2d2+4d2+8d2+6d2) + residual term
if((n-3)%4)==1) residualterm=2d2
else if ((n-3)%4)==2) residualterm =4d2
else residualterm=8d2

#6

Take long long to store sum
Also (a+b)%x =((a%x)+(b%x))%x

#7

Sir How you got this formula?

And How you got this approach?
Means How you thought for it as it is not very easy to get this?
How you thought about that and the process you followed?

#8

Bro the more you practice the easier it becomes
see k is 10^12 so we can’t solve this in O(K) and clearly O(logK) soln doesn’t exist
So this means can be solved in O(1)
So this means you have to make an observation and produce a formula or pattern something.

sum is sum of all digits
so we did sum = first 3 digits + since pattern of 4 nos at a time so no of pattern*sum of pattern + for last few nos pattern may be incomplete so residual term

here first 3 digits is d0 +d1+d2
no of pattern = (n-3)/4
sum of pattern =(2d2+4d2+8d2+6d2)
and residual terms is already explained in last comment

#9

This is with Test Case.

#10

Okayy, I thought DSA Learning Series is completely for beginners and expected very basic level questions there but it is actually very hard.
Not actually hard but a lot logical.

1 Like