Hi , Can you please explain the time complexity of the solve function.i didn't get how it's logk.because you are just decrementing the value by some const(max 53) every time then how it's logk?.
Yaa yaa, I’ll explain it via KMP, though Kmp has a bit step curve to understand, but has a much shorter & 4 lines of code for String Matching. Thus, for Interviews i recommend KMP, but Rapin Karp also is Super great algo, much simpler & intuitive ❤️🫡
For Rabin Karp method to find the position where a string appears in another string you need to run these two function long long get_hash(string s) { int n = s.size(); long long h = 0; for (int i = 0; i < n; i++) h = (h * 31 + (s[i] - 'a' + 1)) % MOD; return h; } // check for the positios where t appears in s vector rabin_karp(string s, string t) { int n = s.size(), m = t.size(); long long p = 1; for (int i = 0; i < m - 1; i++) p = (p * 31) % MOD; vector pos; long long ht = get_hash(t); long long hs = get_hash(s.substr(0, m)); if (hs == ht) pos.push_back(0); for (int l = 1, r = m; r < n; l++, r++) { int del = ((s[l - 1] - 'a' + 1) * p) % MOD; int add = s[r] - 'a' + 1; hs = ((hs - del + MOD) * 31 + add) % MOD; if (hs == ht) pos.push_back(l); } return pos; }
@@ARYANMITTAL I tried studying/understanding KMP but it just goes over my head and for Rabin karp I don't understand how to 'Hash' effectively. So if not for the problem in the contest, can you make another video for Rabin karp as well?
Literally God level Explaination
Worth 43 minutes explaination
Thank you so much bhaiya :)
the frequency of the bits before the most significant bit can be proved by pigenhole principle right
Thala 1,2,4 vdos needed :)
Yaa yaa coming in an hour
Hi ,
Can you please explain the time complexity of the solve function.i didn't get how it's logk.because you are just decrementing the value by some const(max 53) every time then how it's logk?.
thanks for the explanation and thought process from scratch.
Thank you so much for this explanation. Could you please do solutions to DP study plan. It has 50 problems ranging mainly from Easy to Medium.
Great video, please make a video on rabin karp aswell.
Yaa yaa, I’ll explain it via KMP, though Kmp has a bit step curve to understand, but has a much shorter & 4 lines of code for String Matching. Thus, for Interviews i recommend KMP, but Rapin Karp also is Super great algo, much simpler & intuitive ❤️🫡
For Rabin Karp method to find the position where a string appears in another string you need to run these two function
long long get_hash(string s) {
int n = s.size();
long long h = 0;
for (int i = 0; i < n; i++) h = (h * 31 + (s[i] - 'a' + 1)) % MOD;
return h;
}
// check for the positios where t appears in s
vector rabin_karp(string s, string t) {
int n = s.size(), m = t.size();
long long p = 1;
for (int i = 0; i < m - 1; i++) p = (p * 31) % MOD;
vector pos;
long long ht = get_hash(t);
long long hs = get_hash(s.substr(0, m));
if (hs == ht) pos.push_back(0);
for (int l = 1, r = m; r < n; l++, r++) {
int del = ((s[l - 1] - 'a' + 1) * p) % MOD;
int add = s[r] - 'a' + 1;
hs = ((hs - del + MOD) * 31 + add) % MOD;
if (hs == ht) pos.push_back(l);
}
return pos;
}
@@ARYANMITTAL I tried studying/understanding KMP but it just goes over my head and for Rabin karp I don't understand how to 'Hash' effectively. So if not for the problem in the contest, can you make another video for Rabin karp as well?
@@ARYANMITTAL can u make video on rabin karo please
superb explanation.thank you so much for this video.
best explanation bro🍻
nice explanation !
public long findMaximumNumber (long k,int x){
long lo=0,hi=(long)1e16;
while(lo>1);
long bits=0;
for(long i=1
This code is giving error when submitted on leetcode at testcase
2109
1
the expected answer is 481 but the output is coming 482
Please check it bro...
It is giving Correct answer bro. leetcode.com/problems/maximum-number-that-sum-of-the-prices-is-less-than-or-equal-to-k/submissions/1152778070/
@@ARYANMITTAL ohh it was my mistake only thanks for response..