Sir please don't stop making videos. Like other UA-camrs I know you don't demand subscribers like such but your content is gold and one day people will come to know who is the best just keep moving forward. Educational content grows slowly on yt but it is really what change people's life.
Alternate simpler approach we can just keep Sum of digit as parameter ,this way we don't need a separate count function ll helper(string &r, int sum=0,int digit=0,bool flag=true) { if(digit==r.size()) { return sum; } if(dp[digit][sum][flag]!=-1) { return dp[digit][sum][flag]; } int tight=(flag)? r[digit]-'0': 9; ll k=0; for(int i=0;i
I messed up all digit dp problems during my campus placements...didn't even know how to solve them without brute force.Thank you for providing explanations!!I'm enjoying your videos a lot
Nice explanation. Regarding the cnt() method. we can use following simplified imeplementation. LL cnt(string num, int n, int tight) { if (tight == 0) return (pow(10, n) + 0.1); if (n == 0) return 1; return stoll(num.substr(num.length()-n)) + 1; }
We can also recursively count all the valid solutions and multiply them :) string s; ll dp[20][2], ans; ll cdp[20][2]; ll cnt(int i, int j) { if (i == s.size()) return 1; ll& ret = cdp[i][j]; if (~ret) return ret; ret = 0; int lim = (j ? s[i] - '0' : 9); for (int k = 0; k
Great explanation Bhaiya, but i have one question, while generating cnt(x) if tight ==1 why are you again using recursion instead of taking last n-1 digits? for example our range is 9863 and we kept our first digit as 9 and since 9 is the maximum we can place in the first digit we need to know how many time 9 gets generated for that i can directly return 863 right if tight==0 then no issues i can return pow(10,n-1)? instead of doing recursion.
Hey Vishnu, nice observation. You are right if tight is 1 and number is 863, we can directly return 863+1(000, 001, 002, ... , 863). You can definitely solve it this way too. For me recursion seemed more consistent with the theme of the series digit dp. Also imagine if the number was 10000 digit long and you had to return cnt(x) % M. Hope that helps :)
Thank you brother for everything you are doing... Please one request is do graphs and Union Find problems from Leetcode most frequently asked questions
Thanku so much . Can you please start series for Graphs Algo ,Stl . i saw playist it have one video only for graph .By the way Your doing really amazing job bhaiya/
Hey Bro, A silly doubt. Can we apply dp to postorder in an case? I meant, if rather than calculating count separately, can we directly send sum in next call postorder? Here is an example... ``` private static long helper(long num, int x, boolean isTight, long sum){ if(x == Long.toString(num).length()) return sum; int lb = 0; int ub = isTight ? Long.toString(num).charAt(x)-'0' : 9; long res = 0; for(int i = lb; i
@@AlgosWithKartik No problem, I will try... While I always have hard time at making use of dp in postorder. And its always like we store values in preorder. Anyways thanks!!
Sir please don't stop making videos. Like other UA-camrs I know you don't demand subscribers like such but your content is gold and one day people will come to know who is the best just keep moving forward. Educational content grows slowly on yt but it is really what change people's life.
Alternate simpler approach we can just keep Sum of digit as parameter ,this way we don't need a separate count function
ll helper(string &r, int sum=0,int digit=0,bool flag=true)
{
if(digit==r.size())
{
return sum;
}
if(dp[digit][sum][flag]!=-1)
{
return dp[digit][sum][flag];
}
int tight=(flag)? r[digit]-'0': 9;
ll k=0;
for(int i=0;i
I messed up all digit dp problems during my campus placements...didn't even know how to solve them without brute force.Thank you for providing explanations!!I'm enjoying your videos a lot
Your Teaching way is Extraordinary vaia,,
Plz keep making videos.
The Best Digit DP Series, I can say
Nice explanation. Regarding the cnt() method. we can use following simplified imeplementation.
LL cnt(string num, int n, int tight) {
if (tight == 0) return (pow(10, n) + 0.1);
if (n == 0) return 1;
return stoll(num.substr(num.length()-n)) + 1;
}
We can also recursively count all the valid solutions and multiply them :)
string s;
ll dp[20][2], ans;
ll cdp[20][2];
ll cnt(int i, int j) {
if (i == s.size()) return 1;
ll& ret = cdp[i][j];
if (~ret) return ret;
ret = 0;
int lim = (j ? s[i] - '0' : 9);
for (int k = 0; k
Noicee
Great explanation Bhaiya, but i have one question, while generating cnt(x) if tight ==1 why are you again using recursion instead of taking last n-1 digits? for example our range is 9863
and we kept our first digit as 9 and since 9 is the maximum we can place in the first digit we need to know how many time 9 gets generated for that i can directly return 863 right if tight==0 then no issues i can return pow(10,n-1)? instead of doing recursion.
Hey Vishnu, nice observation.
You are right if tight is 1 and number is 863, we can directly return 863+1(000, 001, 002, ... , 863).
You can definitely solve it this way too. For me recursion seemed more consistent with the theme of the series digit dp.
Also imagine if the number was 10000 digit long and you had to return cnt(x) % M.
Hope that helps :)
@@AlgosWithKartik Thanks Bhaiya.
Thank you brother for everything you are doing... Please one request is do graphs and Union Find problems from Leetcode most frequently asked questions
Will definitely consider.
bhaiya at coder k dp problem set ki series baana do .ache questions h.plzzzzz
its great, continue.
awesome content bhaiya
nice approach
can we memoize the count function ?????
Sir is there way to get editorials of spoj problems just like codeforces.
The best I can think of is to google search for "spoj problem code editorial"
got ac first and then watched the video;)
Sir please make a video on merge interval dp problems... ASAP, thank you for contributing it is very very helpful.
can you share an example problem which uses this technique?
@@AlgosWithKartik and sir also the blog which you shared regarding dp patterns there are many more examples of these problems, such bust balloon etc.
Sir don't worry soon You will have too many subscribers :)
Thanku so much . Can you please start series for Graphs Algo ,Stl . i saw playist it have one video only for graph .By the way Your doing really amazing job bhaiya/
Thanks Fardeen!
Yes I will try to start a series for graph sometime soon
Is it really a dp problem, i feel like no sub problems will be repeated.
Hey Bro, A silly doubt. Can we apply dp to postorder in an case? I meant, if rather than calculating count separately, can we directly send sum in next call postorder?
Here is an example...
```
private static long helper(long num, int x, boolean isTight, long sum){
if(x == Long.toString(num).length()) return sum;
int lb = 0;
int ub = isTight ? Long.toString(num).charAt(x)-'0' : 9;
long res = 0;
for(int i = lb; i
Try it out :) will need to watch my solution or think of it again before answering your query
@@AlgosWithKartik No problem, I will try... While I always have hard time at making use of dp in postorder. And its always like we store values in preorder. Anyways thanks!!
what is the level of difficulty here? is this problem hard?
First comment
which tool u r using for writing on screen ??
Epic pen
Second comment 🔥
7th comment 😂
Yeh bhi theek h xD
Can't hear your English:(