Counting Bits | Leetcode

This video explains a very important programming interview problem which is to find the number of set bits for all numbers from 0 to N and push them in an array and return as answer.This problem is frequently repeated in interview.There are many approaches to solving this problem but the simplest is to just iterate over all the numbers and every bit of each number and find the count of set bits.This takes O(NlogN) time.I have shown this approach as method-1 in this video.We can further optimize this solution by using simple observations and use extra space of O(N) to just solve it in O(N) time.I have shown the entire intuition with examples and CODE for this optimized solution as method 2. CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
=================================================================
INSTAGRAM: / surya.pratap.k
LinkedIn: / surya-pratap-kahar-47b...
=================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
SIMILAR PROBLEMS:-
Bitwise AND of numbers range: • Bitwise AND of numbers...
Majority element in an array (BitMasking): • Majority element in an...

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

[@subham-raj]

I'm glad that I found this channel :)

[@techdose4u]

Ahhh.... 😁

[@snehilgupta8558]

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

[@ShivamKumar-qv6em]

finest u tube channel for competitive programming .

[@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. ❤

[@pratham654]

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

[@anssha2643]

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

[@techdose4u]

Welcome :)

[@siddhartha.saif25]

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

[@techdose4u]

Welcome

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

[@HenryMufc82]

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

[@abhishekkeshri3974]

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

[@saranshdabas4223]

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

[@techdose4u]

Welcome :)

[@dhawalpatil4038]

just loved the explanation!

[@violetamalinkova8840]

Amazing explanation, thank you so much.

[@ersinerdem7285]

Great explanation for the DP solution!

[@akshaycharjan6384]

Best one even after 3 years!

[@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 ❤️

[@abhishekrai4325]

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

[@techdose4u]

Welcome :)

[@tanujkalra7334]

This approach was fantastic :) Thanks a ton!

[@techdose4u]

Welcome :)

[@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 !!

[@Oscar-vr2md]

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

[@techdose4u]

Thanks man :)

[@Michandel]

Great explanation!

[@rogers2934]

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

[@techdose4u]

Thanks :)

[@nagendravelpuri444]

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

[@techdose4u]

Thanks ☺️

[@KushalBhatia]

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

[@techdose4u]

Welcome :)

[@amolmishra8621]

This solution is just wow! Mindblown totally.

[@techdose4u]

:)

[@raghuveernaraharisetti]

Always the best!

[@SHARMATUSHAR1_]

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.

[@mondayemmanuel191]

I totally enjoy your explanations.

[@techdose4u]

Thanks :)

[@saravanan925]

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

[@udaychatterjee4424]

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

[@sandeepkumarnagamalla1020]

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

[@techdose4u]

Welcome :)

[@RanjuRao]

Thank you for the solution :)

[@techdose4u]

Welcome

[@wentingsong9435]

Brilliant, you are a savior!

[@techdose4u]

Thanks :)

[@amiteshanand5157]

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

[@farjanask869]

Chala help ayindi anna thank you so much Annaya

[@ayeshaadhikari6123]

thank you so much sir!

[@chayandas4942]

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

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

[@ShivamKumar-nx6tt]

Great explanation bro 🔥🔥

[@mosiurrahman4061]

bow down to this guy.

[@ajaywadhwa3398]

Awesome Explanations !! Really helped a lot.

[@techdose4u]

Thanks :)

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

[@liftwithamey]

Great Explanation !!!!!!!!

[@techdose4u]

Thanks

[@priyeshjammula854]

Superb explanation

[@PriyanshuSingh-dt3oz]

Crystal Clear Explaination

[@techdose4u]

Thanks ❤️

[@eshwarnaidu4747]

clear explanation

[@siddhartha.saif25]

very nice! thank you!

[@techdose4u]

Welcome

[@chidinmakalu502]

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?

[@michaelchan6144]

great vid! subscribed!!!!!

[@techdose4u]

Thanks 😊

[@anand.prasad502]

simply awesome! Thank you very much :)

[@techdose4u]

Welcome

[@krishangopal6795]

Best youtube channel till now.

[@techdose4u]

Thanks :)

[@krishangopal6795]

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

[@srirammuralidaran2121]

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

[@techdose4u]

Welcome :)

[@santanu29]

Thank you for the explanation

[@techdose4u]

Welcome 😊

[@bhopalsingh4102]

Clean and crisp explanation...

[@techdose4u]

Thanks

[@aditikhandelwal135]

Your explanation are just amazing 😍😍

[@techdose4u]

Thanks :)

[@siddhantsamal8878]

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

[@techdose4u]

Welcome :)

[@shivam7929]

this is explanation is lit man , I am totally mesmerized

[@techdose4u]

Thanks :)

[@bogasaiteja8968]

Thanks man!

[@techdose4u]

Welcome

[@kunalsoni7681]

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

[@techdose4u]

Welcome :)

[@dontknow592]

Thank You Sir. Very precisely explained 🤓🙌🏻

[@techdose4u]

Welcome :)

[@techNtech352]

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

[@techdose4u]

Thanks

[@mahipalsingh-yo4jt]

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

[@techdose4u]

Thanks

[@suryakiran2970]

Excellent Explanation

[@techdose4u]

Thanks :)

[@gokulnaathb2627]

Very nicely explained, Sir

[@techdose4u]

Thanks 😊

[@mrinmoypaul6810]

great explanation and solution

[@techdose4u]

Thanks :)

[@keshavraghav3896]

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

[@techdose4u]

Thanks :)

[@abhisekmishra5245]

just wow !!! nice explanation sir

[@techdose4u]

Thanks :)

[@newbeessfu7820]

EXCELLENT

[@rashmimishra5356]

Awesome explaination

[@techdose4u]

Thanks 😊

[@orchideirakozesr8842]

Very thankful for the work you’re doing mate !

[@techdose4u]

Welcome :)

[@NirmalSilwal]

great explanation

[@techdose4u]

Thanks

[@ishwaripednekar5164]

Cool 👍

[@NoOneIsHereRightNow]

Amazing solution thanks

[@techdose4u]

Welcome :)

[@sabihaakter4580]

Nice Explanation

[@techdose4u]

Thanks

[@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 😀

[@RicheshGuptaRichu]

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

[@techdose4u]

Thanks bhai 😀

[@m.s.nabhiram1532]

very nicely explained

[@techdose4u]

Thanks

[@agileprogramming7463]

Mind == blown away

[@techdose4u]

🤣 a coder's way to represent feelings

[@saravana6882]

fantastic solution

[@techdose4u]

Thanks :)

[@harsh007301]

what if we were given any random range instead of 0 to n? is there any O(n) solution?

[@yashkapoor508]

The best solution I found so far 😁🥳

[@techdose4u]

Nice :)

[@sukanyasen305]

Beautiful solution

[@techdose4u]

Thanks

[@devmahfuz]

what is the name of the app used for drawing?

[@anujchauhan4876]

Thanks bro !

[@techdose4u]

Welcome 😄

[@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 :/

[@LALITKUMAR-dg4yj]

it helps..thank you...

[@techdose4u]

Welcome :)

[@manassingh8063]

Will improving solution from O(32*N) to O(N) will make any difference because asymptotically both the solution are of same complexity?

[@techdose4u]

Yea it will. If think carefully then 32N is actually NlogN. Ask yourself if improving time from NlogN to N will make any difference!!

[@navyaagrawal2474]

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

[@techdose4u]

Thanks :)

[@mahadishakkhor123]

i can understand from ur video

[@pazarcimpazarcim8677]

bro, you're amazing

[@techdose4u]

Thanks :)

[@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]

👍

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

[@singurubhavana8368]

Simply awesome👌👌

[@techdose4u]

Thanks :)

[@dipeshsaili4468]

Thankyou so much sir

[@techdose4u]

Welcome 😊

[@yyyooohhhooo]

Thank you sir!

[@techdose4u]

Welcome :)

[@rishabsinha8749]

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

[@Owais486]

thank u so much sir 😭😭😭