Counting Bits | Leetcode

[@AnandKumar-uy7nn]

Here the trick is that number of set bits in even numbers is equal to the number of set bits in n/2 and +1 is the number is odd Bcz doubling the number = shifting the number 1 position towards left which contribute to one 0 at the end so no effect on the number of set bits if the number is odd that means we need first add one zero to the end and then add +1 to it in order to make it odd ex : 6 ==> 110 while making it 12 we can shift by one position left so 12 = 110 1100 no more 1 is added to it while making the 13 we need to add +1 to the 12 which has a zero at its end and hence it directly contributes to one 1 12 + 1 ==> 1100 + 1 ==> 1101 class Solution { public: vector countBits(int n) { vector ans(n+1); ans[0]=0; for(int i=1; i

[@Mercer80]

So it's dynamic programming as we are using previous results

[@AnandKumar-uy7nn]

@@Mercer80 yeah !!

[@ShivamKumar-qv6em]

finest u tube channel for competitive programming .

[@Official-tk3nc]

I think this is the most underrated youtube channel for programming believe me your channel will reach 1 Million subscribers soon :)

[@techdose4u]

Thanks for your motivation

[@tonyz2203]

true

[@abhishekkeshri3974]

vector countBits(int n) { vectorbitcount; for(int i=0;i

[@subham-raj]

I'm glad that I found this channel :)

[@techdose4u]

Ahhh.... 😁

[@topcoder3812]

Simple code sol // Time: O(n) // Space: O(n) class Solution { public: vector countBits(int num) { vector res{0}; for (int i = 1; i > 1]); } return res; } };

[@techdose4u]

👍

[@nagendravelpuri444]

This is the best algorithm for solving this problem ,good explanation sir!!

[@techdose4u]

Thanks ☺️

[@snehilgupta8558]

You explain these problems so easily and in the best way ...... Amazing work sir

[@krishangopal6795]

Best youtube channel till now.

[@techdose4u]

Thanks :)

[@krishangopal6795]

TECH DOSE Sir please share your mail or contact number need placement related advice

[@SharmaTushar1-yt]

Best explanation. I watched Neetcode's video first but this explanation is a lot better.

[@techdose4u]

:)

[@karthikkunjithapatham3814]

Great solution. Am wondering how can one think and arrive at this kind of an approach. Especially during interviews :) This is where I struggle. Mostly my mind revolves around standard problem solving techniques.

[@techdose4u]

Practice will improve your ability :) so keep practicing.

[@dayanandraut5660]

clear cut explanation. 1000 likes for the idea and another 1000 likes for easy explanation. Keep it up. You just earned a subscriber.

[@techdose4u]

Thanks ❤️

[@pennilesscoder3926]

The Method is Generally Look Up table Method......For finding set bits at each Number....But We can Find Total Number of Set bits from 1 to N with Time complexity O(logN)....Which is better than O(N)....And the right shift or divide by 2 approcah is well explained and understood

[@lekanosagie]

I think you're misunderstanding. This method finds the number of set bits in O(1) time, not O(logN). Given that there are N elements in the array, the time omplexity is O(1) * N = O(N). Populating the array is O(N) at the least, so if it took LogN to find the number of set bits, then the time complexity for your solution would be O(NLogN) which is slower than TECH DOSE's approach.

[@rishabsinha8749]

dp[i] = dp[i>>1] + (i&1); can also be done and it is faster than / and %

[@amolmishra8621]

This solution is just wow! Mindblown totally.

[@techdose4u]

:)

[@akshaycharjan6384]

Best one even after 3 years!

[@basedmangoes3379]

amazing explanation. thank you!!! i was struggling with the intuition, but breaking it down was extremeyl helpful!

[@techdose4u]

Nice :)

[@udayptp]

Saw many different ways to solve this problem on you tube and gfg but this was best approach. ❤

[@pforprogrammer]

watch multiple videos but didn't even get the gist of this topic, but your way of explaining this problem is osm really got the concept... . Thankyou man

[@saravanan925]

Nowadays, I am searching for one problem in youtube, if tech dose has uploaded that problem then my problem becomes easy

[@anssha2643]

Your videos are all so good. Thanks for the conetent. Simple to understand and easy to implement

[@techdose4u]

Welcome :)

[@PriyanshuSingh-dt3oz]

Crystal Clear Explaination

[@techdose4u]

Thanks ❤️

[@amiteshanand5157]

can u explain more optimized solution using just log 32 complexity or log num

[@siddhartha.saif25]

i like the way you develop the solution. take example, then have some observations. great job! thank you!

[@techdose4u]

Welcome

[@saranshdabas4223]

Instant sub for this kind of content. Keep it up!

[@techdose4u]

Welcome :)

[@mosiurrahman4061]

bow down to this guy.

[@rogers2934]

Now this is how you explain!!! Great work!!

[@techdose4u]

Thanks :)

[@violetamalinkova8840]

Amazing explanation, thank you so much.

[@Oscar-vr2md]

You rock, Duuuude! Learned a lot from your videos!!!!

[@techdose4u]

Thanks man :)

[@chayandas4942]

Bhaiya, you such a great teacher. You make us understand so patiently and easily. Thank you

[@techdose4u]

Welcome :)

[@udaychatterjee4424]

It's not easy to come up with this solution but if you do...you are awesome !

[@abhishekrai4325]

Thank you so much sir for such a brilliant explanation. Love your videos. Thank you for putting so much effort :)

[@techdose4u]

Welcome :)

[@shivam7929]

this is explanation is lit man , I am totally mesmerized

[@techdose4u]

Thanks :)

[@rahulbawa3969]

Thanks for the awesome explanation. However, I doubt if I could have come up with this observation in an actual interview. I would have just gone with O(32n) solution :(

[@bree9895]

i dont think anyone can come up with this without seeing it first :/

[@tanujkalra7334]

This approach was fantastic :) Thanks a ton!

[@techdose4u]

Welcome :)

[@RicheshGuptaRichu]

Tagda bhai.. GFG DSA course me bhgaa dia tha iss topic ko

[@techdose4u]

Thanks bhai 😀

[@bhopalsingh4102]

Clean and crisp explanation...

[@techdose4u]

Thanks

[@srirammuralidaran2121]

Superb explanation and easy to understand the solution. Thanks keep going ...

[@techdose4u]

Welcome :)

[@dmsohel1335]

I think we can use while(n==0){ n&(n-1) expression and increment the count the Time comp is O(n*no of set bits)

[@techdose4u]

This is the same as method 1. A little more efficient.

[@rohithkumartangudu4664]

@@techdose4u This solution is giving 3ms runtime

[@dmsohel1335]

@@rohithkumartangudu4664 time complexity less or more ?

[@rohithkumartangudu4664]

@@dmsohel1335 The above method time complexity is O(logn). There are n elements to find then the total time complexity is O(nlogn).

[@HenryMufc82]

very clear explanation of the solution and the theory behind it, thanks very much :)

[@mondayemmanuel191]

I totally enjoy your explanations.

[@techdose4u]

Thanks :)

[@abhishekkumaar]

Suppose we have to find the sum of count of bits instead of the array, then there’s a O(log n) solution available.

[@JamesHalpert8555]

Great explanation as always!!! Very much helpful!! Thank You!! Can you please make a video on time complexity and space complexity...

[@techdose4u]

Yea sure. I have started the playlist but not finished due to challenges. Once this is over, I will finish it.

[@aditikhandelwal135]

Your explanation are just amazing 😍😍

[@techdose4u]

Thanks :)

[@orchideirakozesr8842]

Very thankful for the work you’re doing mate !

[@techdose4u]

Welcome :)

[@asthapandey265]

@TECH DOSE solution is great , but if the space complexity is o(n), then would it not fail for nos ~=10^9??

[@ersinerdem7285]

Great explanation for the DP solution!

[@KushalBhatia]

Mind blowing power of observation. Thank you Keep up the good work @TECH DOSE

[@techdose4u]

Welcome :)

[@mrinmoypaul6810]

great explanation and solution

[@techdose4u]

Thanks :)

[@yashkapoor508]

The best solution I found so far 😁🥳

[@techdose4u]

Nice :)

[@sandeepkumarnagamalla1020]

Excellent explanation !! Very easy to understand sir. thanks a lot for making this video.

[@techdose4u]

Welcome :)

[@Learner010]

ans[i] = ans[i&(i-1)] + 1; work perfectly

[@techdose4u]

👍

[@agileprogramming7463]

Mind == blown away

[@techdose4u]

🤣 a coder's way to represent feelings

[@liftwithamey]

Great Explanation !!!!!!!!

[@techdose4u]

Thanks

[@suryakiran2970]

Excellent Explanation

[@techdose4u]

Thanks :)

[@siddhantsamal8878]

sir , you are truly a genius ,always helped a lot..Thankyou

[@techdose4u]

Welcome :)

[@pratham654]

This is the best explanation. More kudos to you 💯💯

[@sukanyasen305]

Beautiful solution

[@techdose4u]

Thanks

[@abhisekmishra5245]

just wow !!! nice explanation sir

[@techdose4u]

Thanks :)

[@NoOneIsHereRightNow]

Amazing solution thanks

[@techdose4u]

Welcome :)

[@navyaagrawal2474]

Please continue making videos in the upcoming June challenge too. Your videos are awesome!

[@techdose4u]

Thanks :)

[@kirtigera2225]

Thankew sir.. Please upload egg dropping puzzle problem using recursion and dp...

[@techdose4u]

Yea sure. I am not getting any time you see. Daily videos is very exhausting.

[@kirtigera2225]

@@techdose4u OK sir..

[@santanu29]

Thank you for the explanation

[@techdose4u]

Welcome 😊

[@saravana6882]

fantastic solution

[@techdose4u]

Thanks :)

[@farjanask869]

Chala help ayindi anna thank you so much Annaya

[@keshavraghav3896]

ooooooohhhhh... you are really awesome sir...!

[@techdose4u]

Thanks :)

[@fsociety8438]

faad bhai faad

[@techdose4u]

Thanks bhai :)

[@shreedharkushwaha3100]

Plzz make a video for negative numbers also

[@Michandel]

Great explanation!

[@RanjuRao]

Thank you for the solution :)

[@techdose4u]

Welcome

[@dhawalpatil4038]

just loved the explanation!

[@mahipalsingh-yo4jt]

Excellent sir !!!!!!!!!!!!!!!!!

[@techdose4u]

Thanks

[@m.s.nabhiram1532]

very nicely explained

[@techdose4u]

Thanks

[@priyeshjammula854]

Superb explanation

[@abhisheksunda7925]

Great!! How to come up with this kind of solution?

[@wentingsong9435]

Brilliant, you are a savior!

[@techdose4u]

Thanks :)

[@siddhartha.saif25]

very nice! thank you!

[@techdose4u]

Welcome

[@techNtech352]

Seriously, this is one of the best Channel for coding problems. Such a nice explanation as always

[@techdose4u]

Thanks

[@gokulnaathb2627]

Very nicely explained, Sir

[@techdose4u]

Thanks 😊

[@topcoder3812]

Sir please create new course on basic to advanced competitive programming .If you have time. Your teaching style is awesome

[@techdose4u]

I wish I had more time. Currently it will not be possible. I will focus videos topicwise once leetcode challenge is over.

[@topcoder3812]

@@techdose4u As your wish👍👍

[@sabihaakter4580]

Nice Explanation

[@techdose4u]

Thanks

[@eshwarnaidu4747]

clear explanation

[@dontknow592]

Thank You Sir. Very precisely explained 🤓🙌🏻

[@techdose4u]

Welcome :)

[@meghamalviya8495]

Can you please explain how the complexity was O(N log max ) in 1st method?

[@techdose4u]

It is same as NlogN. Max means num because num is the maximum value of range.

[@meghamalviya8495]

@@techdose4u thanks!

[@karansagar7870]

great explanation

[@techdose4u]

Thanks

[@ajaywadhwa3398]

Awesome Explanations !! Really helped a lot.

[@techdose4u]

Thanks :)

[@chitobi3010]

Thank you for your explanation! However, I don't quite understand the time complexity for the first approach. Isn't it supposed to be O(N)? Time complexity using Brian Kernighan's algorithm is O(1) + O(N+ 1) to iterate from range(0, n+1). Please, am I missing something?

[@TechieIndia]

please make more videos on bitmasking also.

[@techdose4u]

👍 I will make as problems keep coming

[@TechieIndia]

@@techdose4u please make videos on code forces round 647 div 2 or 1 b/c every question is related to bitmasking

[@MrACrazyHobo]

Can we say that this approach is dynamic programming?

[@techdose4u]

Yes right.

[@deveshsharma7487]

Really a great obervation and the best method to solve this problem I have seen till now. Thanks a lot, I wish your channel becomes more and more famous. Keep up the good work

[@techdose4u]

Thanks for your wishes. Touchwood 😀

[@kunalsoni7681]

Sir this video is such a helpful to me.. to understand bit manipulation 😊☺️.. thank you..

[@techdose4u]

Welcome :)

[@anmax]

Wow I thought I wasn't understading anything, but it suddenly clicked

[@singurubhavana8368]

Simply awesome👌👌

[@techdose4u]

Thanks :)

[@raghuveernaraharisetti]

Always the best!

[@anand.prasad502]

simply awesome! Thank you very much :)

[@techdose4u]

Welcome

[@mahadishakkhor123]

i can understand from ur video

[@michaelchan6144]

great vid! subscribed!!!!!

[@techdose4u]

Thanks 😊

[@lovleshbhatt7797]

Sir I m your big fan, I want to ask a question that I have completed my Trees and BST from GeeksForGeeks and solved mostly problem on GFG and some problem on Leetcode too, Now my question is that Should I go for CP trees question or I have to completed the remaining leetcode question of Trees and BST???

[@techdose4u]

If you are coding for placements then concentrate only on leetcode and interviewbits. If you love CP then do it. Leetcode is sufficient for placement.

[@sonuagarwal7679]

This will also work num[i]=num[i-(i & -i)]+1;

[@techdose4u]

👍

[@dmsohel1335]

What is the time complexity

[@evgeni-nabokov]

@@dmsohel1335 ~num

[@kollivenkatamadhukar5059]

Excellent Observation But how can one arrive at that observation. How Does one even think of property like /2 results in the following results ?? Can u help !

[@techdose4u]

It's easy. Because dividing a number by 2 then it's right shift by one bit for decimal. That's how you can figure it out.

[@kollivenkatamadhukar5059]

@@techdose4u I think u didn't get it. I wanted to know whether you have tried out all those properties you know(Due to Practice) while figuring out this is the apt property !!. Or you have derived it according to the ques ?? If Yes Then How. Could you please walk me through it if possible? I'm willing to know your taught process when you have first seen this question basically. That helps all of us a lot is it the practice we are lacking in or Taught Process in wrong directions. :D

[@techdose4u]

@@kollivenkatamadhukar5059 I just understood on seeing only due to practice.