3234. Count the Number of Substrings With Dominant Ones | Weekly Leetcode 408

[@vishnu4647]

please always try to upload last two problems of the contest. thanx

[@nikhilsoni2403]

Today, i was not able to relate this problem to any of the previous problems i have solved.. What should i do in such situations, when i encouter a new kind of problem? Or is grinding a lot of problems the only way ?

[@acxd]

Kafi accha explanation hai bhai

[@cosmicboy588]

Can you bring any series on Combinatorics like you did for segment tree it would be really helpful

[@imPriyansh77]

Thanks for this video !!! Please make for the 4th problem as well.

[@codingmohan]

Here you go - kzbin.info/www/bejne/hJS0oaVmZbZ0h7c

[@23cash86]

Wonderful explanation

[@nikhilsoni2403]

Thank you !! ❤😊

[@justsomeguywithoutamustach9978]

i dont get why for a valid substring, the maximum number of zeroes can be root(n). Let's say number of zeroes = x, ones = y, length = n; => x + y = n now, since the string is valid, y >= x^2 => maximum of x can be y^0.5 now as you said, maximum of x = root(n) then, y = n - x = n - root(n); but now, the condition y >= x^2 becomes y >= n => n - root(n) >= n which is not possible... can you help me with this?

[@codingmohan]

If X + Y = N --> then X can never be root(N), it will be less than root(N). Hence the inference is correct - but you should check it for a smaller X than root(N). in that case your inference would take a form like - Y = n - (root(n) - c) => n - root(n) + c >= n + c*c - 2*root(n)*c And the above equation is always true for some inequality of "c" and "n". In other words, the # of zeros will be smaller than root(n) always (not equal to root n). Another "easy" way to visualise this is that if you have greater than root(n) zeroes, you'll require ">= N" ones, which is not feasible.

[@veerajbachche1064]

@@codingmohan Even if we take root(no of ones in a string) and iterate that much zeros it will be fine .

[@ok-google-run]

So this gives us an assumption that no. of zeroes in the whole string is not going to be more than (root n). But what if we have zeroes more than (root n) but they are not considered in as a valid string. So even if they are not considered as valid strings, we have to iterate and that makes it n ^ n right? Am I thinking wrongly ? Please correct me if so

[@mr.m4884]

good boy 🐕‍🦺🐕‍🦺