Doubt in Digit Dp

#1

I am doing the standard digit dp to get sum of digits. But getting wrong answer. Can you check my technique?

#2

hello @kks2029

dont paas and memoise count , that might take too much memory

instead try this way->
solve(idx,tight) = current digit + solve(idx+1,updated tight)

base case if idx==n return 0

#3

I dont think dats the problem because the constraints arent that big. Also I m not getting run time or memory limit I m getting wrong ans

#4

Also if I remove the count part It will increase the time complexity

#5

1000000000 999999999
consider this test case Its giving faulty ans here 82 should be the ans! I cant figure it out
@aman212yadav

#6

no, that will work fine infact thata space efficient.

removeif in line 19 and then try

#7

if I remove if in line 19 then I ll have to call memset twice Should I do that?

#8

yead u need to call memset twice.

#9

Thannks bro my code got accepted I included memset twice and removed the extra check for tight

#10


But I followed this article for the problem where they have given another way to escape using memset twice. Because calling memset everytime kind of looks waste to me . So could you point out the mistake here?

#11

U can’t use result of one probleme in other problem.
Here for different value of n ,dp states will have different answers.
I prefer to solve independently to avoid any issue

#12

so is this article wrong? or this is some different scenario altogethher.? I cant understand
I get your point but if I dont use tight values in my dp table the other vlaues for any value will remain unrestricted and hence should behave in same way so we may use it? so makes sense?

#13

Yeah.try submitting their code and see it’s working or not

#14

Its working It seems I m doing some silly mistake!!

#15


This is the new code its working fine

#16

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.