3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K | Bit Manipulation Trick

In this video, I'll talk about how to solve Leetcode 3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K | Bit Manipulation Trick
Checkout DSA-169 Series: • Aryan DSA-169 Series |...
100Days 100k Placements: • 100 Days 100K Placement
Let's Connect:
📝Linkedin: / aryan-mittal-0077
📸 Instagram: / ez.pz.dsa
📱Telegram : t.me/aryan_mittal_group
🤖 Github: github.com/aryan-0077
About Me:
I am Aryan Mittal - A Software Engineer in Goldman Sachs, Speaker, Creator & Educator. During my free time, I create programming education content on this channel & also how to use that to grow :)
✨ Timelines✨
0:00 - Problem Explanation (Bit tricky problem Statement)
2:23 - Building up the basic Approach
13:01 - Optimising using Binary Search
20:19 - Bit Manipulation Trick
36:00 - Code Explanation
✨ Hashtags ✨
#programming #Interviews #leetcode #faang #maang #datastructures #algorithms

[@ekanshsharma1309]

Literally God level Explaination
Worth 43 minutes explaination
Thank you so much bhaiya :)

[@kafuu1]

the frequency of the bits before the most significant bit can be proved by pigenhole principle right

[@giridharanpasupathi]

Thala 1,2,4 vdos needed :)

[@ARYANMITTAL]

Yaa yaa coming in an hour

[@harchitgulati3065]

nice explanation !

[@hanjelly5410]

thanks for the explanation and thought process from scratch.

[@k.satish3663]

superb explanation.thank you so much for this video.

[@rsKayiira]

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.

[@krushnapatil8861]

best explanation bro🍻

[@dashrathkumar4534]

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?.

[@tejaschalke1778]

Great video, please make a video on rabin karp aswell.

[@ARYANMITTAL]

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 ❤️🫡

[@xi1798]

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;
}

[@tejaschalke1778]

@@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?

[@pokeindia5361]

​@@ARYANMITTAL can u make video on rabin karo please

[@paras_classes27]

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...

[@ARYANMITTAL]

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/

[@paras_classes27]

@@ARYANMITTAL ohh it was my mistake only thanks for response..

[@dayashankarlakhotia4943]

public long findMaximumNumber (long k,int x){
long lo=0,hi=(long)1e16;
while(lo>1);
long bits=0;
for(long i=1