Count Set Bits in First N natural numbers | Total Set Bits from 1 to N | Bit Manipulation

Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, we discuss the problem where we are required to find the set bits in the first N natural numbers using Bit Manipulation. In this problem,
1. You are given a number n.
2. You have to print the count of set bits of first n natural numbers.
To submit this question, click here: www.pepcoding....
For a better experience and more exercises, VISIT:
#bitmanipulation #bitmasking
Have a look at our result:
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education

[@shivamagrawal2284]

Best explanation found after googling for more than 1hrs. Thank you

[@Pepcoding]

Glad it was helpful and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )

[@sumitsharma6738]

sahi me bro

[@vardhanshah8843]

The approach of subtraction to convert it into recursion was amazing.

[@pramodtarpe]

You can use floor(log base 2(n)) to find 2 power x less than or equal to n.

[@rishabsharma5307]

Can you tell me why this is working?

[@pramodtarpe]

@@rishabsharma5307 thats the purpose of log

[@ayushpatel2171]

@@rishabsharma5307 In simple words logarithm is "How many of one number do we multiply to get another number?" Eg. log2(8) means how many 2s we need to multiply in order to get 8. The answer is 3, so the (log base 2(8)) = 3. Now if we do log base 2 for a number which is not a power of 2 we will get a decimal value eg. log base 2(10) = 3.322. And if we use floor function with log base 2(10) we will get 3. And 2^3 is highest power of 2 less than 10.

[@rishabsharma5307]

@@ayushpatel2171 thnx

[@uttkarshsingh3771]

Finally got some worthy content to look for. Pepcoding is great 🔥🔥🔥

[@ManishKumar-zk5ky]

Best explanation on entire youtube sir Thanks a lot sir🤩

[@b_1729-j8j]

Ur explanation is better than GFG article. Thank you.

[@rishijain8472]

great explanation, best coding teacher on youtube 2nd is striver

[@RajSingh-YrBTechChemicalEnggII]

best explanation, better than google

[@Biradar_Ganesh]

Clean Explanation Sir!! Learned a new technique 🫡

[@systemforge]

Even though I don't know hindi.. i was able to understand it.. u r legend sir.. ❤️

[@Pepcoding]

Great, Keep learning, Keep growing and keep loving Pepcoding!😊

[@stith_pragya]

Thank You So Much Sumeet Sir.................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@PulkitMalhotra]

Thank you sir 1 number smz aa gya

[@Pepcoding]

Thankyou beta! Keep learning and keep loving Pepcoding😊 If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )

[@arijitchowdhury4189]

Mszza ahh gaya sir ... Very good explanation. Thank you 🔥🔥🔥

[@sreejitkar8044]

Best explanation sir ❤

[@kashbhalla4363]

about to complete this series you are too good sir.

[@lalitkumarmehta1721]

The way u explain is pretty awesome, Thanks, bro.

[@csgirl6895]

Thank you so much, Sir. Your way of explaining the solution is awesome. After watching your videos most difficult questions also become easy for me.

[@sonianarendramodi2605]

I love you ❤❤❤💖💖💖

[@srinivasak4087]

very nicely explained Sir, Thanks!

[@Devendrakr63]

Best place to learn hard topics in easy way. Great!!!!

[@CrackMODS8]

one of the best soln

[@neerajbhatia2008]

subscribing ur channel now. seriously man, you are too good. love your style of presentation and explanation, keep up the good work.

[@Pepcoding]

Thanks a ton!

[@Pepcoding]

For better experience, do checkout nados.pepcoding.com

[@yashgupta9662]

A BIG Thanks for the explanation. 🙌

[@Uniyaltech]

great explanation i was struggling from past two days.

[@amreshgiri]

If implementing in Python, don't use the bit shifting method for calculating power as it will give negative shift value error when the value of x

[@kusalsaraf5464]

Thanks a lot, but can you tell the reason as it working for even number but not for odds

[@bhailog_gaming_2000]

Thank you sir. This was the best explanation!

[@UCVision93]

Clear cut explaination! Sir ji !

[@vishalrajak2417]

maje aa gaya bero solution dekkh ke

[@Pepcoding]

Shukriya ji😊 Bs aise he apna pyaar aur sahyog bnaye rkhe hum pr🙏

[@prayagpatel9136]

Great explanation!!!!!

[@pradeepmondal4943]

Ekdaam faadu explaination ❤️❤️❤️❤️❤️❤️❤️ ..boleto jakhaas

[@Pepcoding]

If you like my efforts, I request a review g.page/Pepcoding/review?rc You can subscribe to our channel here kzbin.infoabout?view_as=subscriber For clearing your doubts, you can join our community on telegram t.me/pepcoding

[@vikas5840]

thank you sir for such clear explanation

[@dhruvpurwar6642]

Seriously tooo good!!!!

[@powerofbasics869]

Sir I've jst started the getting started wala portion.... And it is really really good.. Bohat deep explanation Kiya Gaya h .. Thank u so much sir... Hope this channel will become the highest subscribed channel for coding.....:)

[@Pepcoding]

aapko agar sahi lag rha hai to ek review daal dijie g.page/Pepcoding/review?rc

[@057anmolkesarwani4]

Best Soln explanation for this question

[@utkrsh06]

You freaking genius!

[@divyansh3266]

Best explanation..

[@BOSS-s6w8w]

best explanation sir

[@amolshrivastava7786]

Thank you sir, sab smjh m aa gaya after this solution ...also m phele pow(2,x) use karta tha but from now on i'll use (1x) to get 1/2^x.

[@karunakeshari1058]

Best explanation💯

[@aravkhandelwal7043]

very nice explanation

[@Pepcoding]

Thanks for liking. keep motivating, keep learning and keep loving Pepcoding😊

[@myyoutubeisthis]

Thank you very much sir

[@vamsimadugula8524]

It can be more easily solved using vector countBits(int n) { vector ans(n+1); for(int i=0;i

[@mehirrouth7346]

Amazing Explaination

[@jolly_dollyyy]

excellent explanation sir

[@harshitbajaj7549]

Thank you so much sir, best explanation

[@karankesri3648]

For finding the largest of power 2 you can use log2(n) which will give the result in O(1)

[@harshalgarg1676]

int countSetBits(int n) { if(n==0) return 0; int x = log(n)/log(2); int power = pow(2,x); int ans = (power/2)*x + (n-power+1) + countSetBits(n-power); return ans; }

[@kunalkheeva]

Thank you!

[@yagizegemen7303]

Sir the explanation is amazing. Appreciate your effort . Just a suggestion if you can also explain the Time and Space Complexity as well that would be great.

[@Pepcoding]

Ok beta. Soon

[@binitrajshah9354]

You explain great, kudos to you

[@ROHITKADYANJI]

Sumit sir 🤟🤟🤟 Sir explanation is too good 🙌💯

[@Pepcoding]

keep motivating, keep learning and keep loving Pepcoding😊

[@manavpatnaik1948]

Very clear explanation. Thanks!

[@Pepcoding]

Glad it was helpful! Keep learning. And for better experience and well organised content visit nados.pepcoding.com

[@raorao7329]

loveed the soln

[@rahuldwivedi4758]

Nice explanation but it's difficult to remember the formula. We could simply do as following. If the number if even, the result will be f(n/2) and if it's odd it will simply be 1 + f(n/2) take base cases as 0 for n == 0 and 1 for n == 1 const helper = function(n){ if(n === 0) return 0; if(n === 1) return 1; if (n % 2 === 0) return helper(parseInt(n/2)); return 1 + helper(parseInt(n/2)); } var countBits = function(n) { const ans = []; for(let i=0; i

[@akhileshsonkar2061]

Nice Explanation

[@thejasnaveen4223]

Beautiful explanation ❤

[@Pepcoding]

Glad you liked it, for better experience and well organised content sign up on nados.io and start learning.

[@AbhishekSingh-fc2rx]

next level sir, its is very good explanation

[@akshayjadhav4199]

super 😍😍😍😍

[@manideep7148]

Nice Explanation, It would be great if you had explained in english

[@adityamhetras4799]

Thanks you Sir!

[@Pepcoding]

Keep learning. And for better experience, visit nados.io, where you will get well curated content and career opportunities.

[@mickyman753]

fabulous explaination , you made it so easy to understand , i saw the of the same problem on gfg and after hitting my head for several minutes and still not getting it ,saw your explanation ,love you sir

[@Pepcoding]

Thankyou beta! I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem. If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )

[@mickyman753]

@@Pepcoding yes sir i will , and will wait for question solving videos ,they are so good

[@surabhichoubey2987]

Nice sir

[@SaumyaSharma007]

thanks a lot, sir...... you are really a great mentor. Your efforts justify Pepcoding's vision. (yesterday I watched your full interview......) huge respect for u SIR...Long live Sumeet SIR. Sir just want to ask u where can I get your full coding questions sheet (level 1,2). plzzzzz reply

[@Pepcoding]

I am glad. Keep learning. Keep supporting. Your kind words are the kind of motivation that truly help me in making more and more content. Especially, these days, not everybody is generous with motivating anybody either. It means a lot😊 You can find this content on our website under free resources section, as there the content is given in a very structured and sequencial order. and out of which level-1 is almost complete and level-2 is still underprocess.

[@SaumyaSharma007]

@@Pepcoding Thank you Sir 🌟🙏 for the reply...... I am Big fan of yours 🙏

[@sonalisharma9654]

Very nice explanation sir :)

[@ayushmishra9100]

sir u are incredible!!!!

[@vishalm784]

For getting largest power, we can use Math.floor(log2(num)) where log2 can be computed as Math.log(num)/Math.log(2);

[@mickyman753]

but bitwise operations are faster

[@shivammehta9661]

Nice Explanation..Keep making videos

[@Pepcoding]

Thank you, I will

[@kritikakashyap384]

Nice way of teaching

[@Pepcoding]

Thankyou beta! I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem. If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )

[@samardhiman4365]

great explanation sir..

[@dontgiveup5271]

Great explanation sir !! 👏👏 But I wanna know what are the complexities

[@akhilagrawal4559]

Really Loved it Sir!!!

[@Pepcoding]

Thank you for appreciating. The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos. So, keep motivating, keep learning and keep loving Pepcoding😊

[@utkarsh_108]

thanks a lot

[@labbusharma9865]

sir colour change kr liya kro please.... and best explanation

[@samartajshaikh2601]

great explanation.

[@ruchaharshe6489]

nicely explained...thanks!!

[@Pepcoding]

Glad it was helpful! and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )

[@adarshjayadevan4379]

Superb explanation. Thank you.

[@Pepcoding]

Glad to know that you liked the content and thank you for appreciating. The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos. If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )

[@hiteshyadav2298]

I love the way you explained everything. Please use variable name in simplest form if possible. so that we can easily track flow of code. pls ignore words like - btill2x, msb2xton,etc

[@Pepcoding]

Thankyou beta, I am glad you liked it. I also hope that you are watching till end. If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )

[@hiteshyadav2298]

@@Pepcoding ✔

[@taukirlalwala2865]

thank u so much

[@Pepcoding]

Happy to help

[@Prashantkumar-pn6qq]

Thanks Sir! Nice work.

[@mannumichel1925]

maja aa gya sirji

[@Pepcoding]

Thankyou beta! I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem. If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )

[@prakhyat2001]

thanks a lot :)))

[@GoblinMaster30]

Thanks a lot, your video helped me a lot.. I have optimized your code which runs even faster.. hope it helps others { int sum = 0; int x; while(n>0){ x = floor(log(n)/log(2)); sum += x * (1

[@nomaanahmad3357]

thanks for the optimization! Appreciate your help

[@sagarsattigeri9005]

Will recurssion called only one? for all the cases

[@saloniranka5609]

Going forward, can you please add time and space complexity in the end as well, it would be of more help to the existing content

[@Devendrakr63]

Time complexity would be O(logn) , since we are dividing the problem into two parts in each call. And Stack Space take by the algo will also be O(logn), since there are log n recursive function calls.

[@omprakashbarupal2129]

@@Devendrakr63 ig TC is O(longn)^2, as recursive call has TC logn and in each call we we finding 2's power less than n has also TC as logn.

[@omprakashbarupal2129]

TC is O(longn)^2, as recursive call has TC logn and in each call we we finding 2's power less than n has also TC as logn.

[@nomaanahmad3357]

You could have used floor(log2(n)) to find largest power of 2 less than or equal to n. Though log2() function is not available in java but there are multiple ways to do so.

[@abhishekshankar1136]

same thing actually 1

[@kaushiksarmah999]

thanks alot bro

[@divyanshuchaudhari5416]

if n==1: return 1 This condition should also be included,otherwise it gives negative shift value error for input 1. For this assignment : btill2x = x*(1

[@Pepcoding]

Beta, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. For clearing your doubts, you can join our community on telegram - t.me/pepcoding.

[@beinghappy9223]

Ig it gives random value and x being 0 , the final result will be 0 and so no effect

[@rishabhrawat7943]

Sir what is the time complexity of this approach. O(logN) or O(logN*logN)?

[@rohitshinde8478]

thank you for this amazing explaination

[@Pepcoding]

Thankyou rohit for being aur constant supporter. Keep learning and keep loving Pepcoding😊

[@itsyashh1308]

Sir I have a request and feedback, will you please show stats list on website that is really motivation to solve maximum number of questions in a day and questions serial number if possible ???

[@Pepcoding]

questions are in perfect order on portal. use portal instead of youtube. Yes, stats will be brought back.

[@rahulbhatia3075]

Amazing explanation 🔥🔥

[@Pepcoding]

Glad you liked it

[@aparajitakumari2936]

How is he using bitwise left shift operator to calculate power? Please explain.

[@Pepcoding]

For clearing all your doubts visit on nados.pepcoding.com Don't forget to follow us on Instagram instagram.com/pepcoding/

[@Radaradababurao]

amazing content

[@Pepcoding]

Thankyou beta! I am glad you liked it. I also hope that you are watching till the end and trying to understand the what, how, and especially why of the problem. If you like our efforts, will you like to review us here - g.page/Pepcoding/review?rc

[@payalsagar1808]

Wow!

[@Pepcoding]

I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem. If you like our efforts, we request a review g.page/Pepcoding/review?rc You can subscribe to our channel here kzbin.infoabout?view_as=subscriber

[@apoorvmendiratta9002]

class Solution: def countBits(self, N): x = self.largest(N) ans = 0 one = x*(1

[@AmanSharma-vb5jl]

What is the time complexity of this solution?

[@RoshanSingh-kj4fy]

Easy or effective

[@AryanKumar-cc7ku]

playlist of this video???

[@abhimanyu8575]

does this program uses time complexity of theta logn??

[@omkark7118]

Can anyone please help me, how do I use the same logic using BigInteger class? Thank you in advance

[@satyakidas9593]

what is the time complexity of this?