New 21 Game - Leetcode 837 - Python

[@MgThompson]

I might think that, if the interviewer comes up with this problem, I will be sure they don't want to hire you.

[@NeetCodeIO]

Yeahhhh, this is what I call a crackhead problem..

[@dadhx8]

At first I thought there was some "simple" solution using Bayes theorem, but as I thought about it more, I realized I had no clue wtf to do lol

[@yolo3659]

Tip: You can also use a queue instead of a dp array to make life easier. Just initially push the required amount of zeroes and ones and push the subsequent probabilities into the queue while popping the front elements. In the end since we have to return dp[0] in the normal implementation, we have to return the last element in the queue. Here is the C++ code. Note here window_sum is named as sums for simplicity. And max_points is renamed as maxs double new21Game(int n, int k, int maxs) { if((k-1+maxs)=k;i--){ if(i

[@dorothychristina2721]

Could you share some insights on how you break the problem, gather inputs from the problem statement ,say your approach as you go about when you see this kind of problems ?

[@uptwist2260]

this was scary. thanks for the daily

[@itachid]

How am I supposed to come up with this in an interview?

[@infernape716]

Pray

[@MoazMahmud]

I solved it the exact same way! I used the math formula you were talking about. Which is: windowSum = min(maxPoint, n - k + 1)

[@johnnychang3456]

Can you explain the formula? Thanks

[@LarryFisherman5]

@@johnnychang3456 Basically, the n - k + 1 part is counting how many ones we have at initialization, since we have ones from k up to n, and then onwards it's all 0s. However, if maxPts is less than n - k + 1, we can't reach those 1s which are beyond k + maxPts, so they shouldn't be included in the window sum. But note that this can only happen when k + maxPts

[@MoazMahmud]

@@LarryFisherman5 This is a great explanation 😃

[@MrKB_SSJ2]

Yoooooooo THANK YOUUUUU FOR MAKING THIS RIGHT NOW

[@dheereshagrwal]

window_sum = max(0, min(n, k + maxPts - 1) - k + 1)

[@deadlyecho]

Shouldn't the probability of the non optimal solution be O(m^k)? Since the depth of the tree is of magnitude of order k?

[@himanshubarnwal1527]

we can optimize it by using 2d dp of n*k size. So, it will be O(n*k).

[@devMarcus]

I haven't watched any really recent videos because I have been on break but has NeetCode always used a csgo crosshair for drawing?

[@dark_all_day9311]

I got asked this in an MLE interview with 20 mins to solve it 😔 been an MLE for 3 years built out and scaled many pipelines, never needed anything close to the knowledge required for a problem like this one. they rly set me up to fail lol

[@CS_n00b]

would the recursive solution have been enough?

[@Kan-JenLiu]

dangg..... this problem is just crazy...

[@ouchlock]

for testcase n=1 k=0 maxPts=2 as we have [1,2] where only 1 is

[@NeetCodeIO]

Not true. If we start at 0 and k is 0, then we can't draw any cards.

[@ouchlock]

@@NeetCodeIO yes, you're right, thanks

[@DarkOceanShark]

I have been thinking about the solution in the same decision tree based approach like you, where I counted the number of solutions that give me value from k to n and, the number of solutions that give you a value of above or equal to k after previously being below k. I divided the former by latter and returned it as the answer. First and second passed but the third sample test case failed. I have realised the mistake now.

[@meemee417]

Maybe the interviewer will take pity on you if you come up with the raw dp solution and will give you a hint for sliding window 🙏🙏

[@sreesaiaditya2574]

Thank you. I really understood this problem and it is clearly explained.

[@IntelliStar_]

I was able to come up with the non optimal solution but failed to optimize further. I think it should be accepted because the question is medium...

[@HelloWorld-lh1wk]

well a good way to solve this problem in a interview is to click the end meeting button....

[@ashishdhal4614]

I solved it using dp first i multiplied the probability of that number with a recursive call then added all recursive calls formed by the max value loop . After watching the sliding window technique I feel stupid😢😢

[@akashuday7107]

wait why arent you uploading on the Neetcode official channel/?

[@YashVashistha-ot5ux]

Please do the contest problems for each contest the hard ones atleast

[@Amit-fn7bw]

Giving wrong answer on n = 185 , k = 183 , m = 2, correct output = 1, giving 62.1111 class Solution { public: double helper(int n, int k , int m, int pts){ if(pts >= k) return (pts

[@solutionscorner]

class Solution { public: double new21Game(int n, int k, int maxPts) { vector dp(n+1,0); double window_sum = 0; if(k == 0 || n >= k + maxPts) { return 1.0; } for(int i = k; i= 0; i--) { dp[i] = (double) window_sum/maxPts; double del = 0; if(i + maxPts

[@shashivish2022]

Code does not works for Python 2 but works for Python3.

[@NeetCodeIO]

Yes, that's because I'm using python3. No one really uses python2 anymore.

[@chrisliu6444]

@@NeetCodeIO why is python2 not working but python3 working tho?

[@harshmankodiya9397]

why avg?

[@NeetCodeIO]

Like I mentioned, if each branch has an equal probability, that implies we average.

[@ccx0040]

Wrote this in C++ but it's not running, please help me figure out the problem double new21Game(int n, int k, int maxPts) { vectordp(n + 1, 0); for(int i = k; i

[@shishankrawat2105]

if(i+maxPts < k) remove = dp[i+maxPts] else if(i+maxPts

[@notgreen11]

is this one really that hard? seemed like a very easy DP problem when I first tried it, you’ve done many harder problems IMO so i’m surprised w your grading

[@reactionchamber]

relatively easy to come up with the recursive solution, but recognizing how to use a sliding window is quite a stretch imo

[@meowmaple]

ur mum's easier