Count Set Bits in First N natural numbers | Total Set Bits from 1 to N | Bit Manipulation
Vložit
- čas přidán 7. 09. 2020
- 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.com/resources/d...
For a better experience and more exercises, VISIT: www.pepcoding.com/resources/o...
#bitmanipulation #bitmasking
Have a look at our result: www.pepcoding.com/placements
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
Best explanation found after googling for more than 1hrs. Thank you
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 )
sahi me bro
The approach of subtraction to convert it into recursion was amazing.
You can use floor(log base 2(n)) to find 2 power x less than or equal to n.
Can you tell me why this is working?
@@rishabsharma5307 thats the purpose of log
@@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.
@@ayushpatel2171 thnx
Finally got some worthy content to look for. Pepcoding is great 🔥🔥🔥
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
Thanks a lot, but can you tell the reason as it working for even number but not for odds
Best explanation on entire youtube sir
Thanks a lot sir🤩
Best place to learn hard topics in easy way. Great!!!!
about to complete this series you are too good sir.
The way u explain is pretty awesome, Thanks, bro.
Ur explanation is better than GFG article. Thank you.
Thank You So Much Sumeet Sir.................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
A BIG Thanks for the explanation. 🙌
You explain great,
kudos to you
Thank you sir. This was the best explanation!
great explanation, best coding teacher on youtube
2nd is striver
great explanation i was struggling from past two days.
Mszza ahh gaya sir ... Very good explanation. Thank you 🔥🔥🔥
thank you sir for such clear explanation
best explanation, better than google
next level sir, its is very good explanation
Thank you so much sir, best explanation
Best Soln explanation for this question
Thanks Sir! Nice work.
Clear cut explaination! Sir ji !
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.
I love you ❤❤❤💖💖💖
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.....:)
aapko agar sahi lag rha hai to ek review daal dijie
g.page/Pepcoding/review?rc
Great explanation sir !! 👏👏 But I wanna know what are the complexities
Great explanation!!!!!
Nice Explanation
sir u are incredible!!!!
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.
Ok beta. Soon
subscribing ur channel now. seriously man, you are too good. love your style of presentation and explanation, keep up the good work.
Thanks a ton!
For better experience, do checkout nados.pepcoding.com
Thank you sir 1 number smz aa gya
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 )
thank you for this amazing explaination
Thankyou rohit for being aur constant supporter.
Keep learning and keep loving Pepcoding😊
great explanation sir..
Very clear explanation. Thanks!
Glad it was helpful!
Keep learning.
And for better experience and well organised content visit nados.pepcoding.com
Best explanation💯
Amazing Explaination
Seriously tooo good!!!!
excellent explanation sir
great explanation.
Great explanation...
does this program uses time complexity of theta logn??
Ekdaam faadu explaination ❤️❤️❤️❤️❤️❤️❤️ ..boleto jakhaas
If you like my efforts, I request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
czcams.com/users/Pepcodingabout?view_as=subscriber
For clearing your doubts, you can join our community on telegram
t.me/pepcoding
Great explanation.
Superb explanation. Thank you.
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 )
Best explanation..
Sir what is the time complexity of this approach. O(logN) or O(logN*logN)?
Thank you very much sir
For finding the largest of power 2 you can use log2(n) which will give the result in O(1)
Very nice explanation sir :)
Thank you!
Even though I don't know hindi.. i was able to understand it.. u r legend sir.. ❤️
Great, Keep learning, Keep growing and keep loving Pepcoding!😊
best explanation sir
Really Loved it Sir!!!
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😊
Amazing explanation 🔥🔥
Glad you liked it
thanks alot bro
thanks a lot
You freaking genius!
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;
}
nicely explained...thanks!!
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 )
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
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.
@@Pepcoding Thank you Sir 🌟🙏 for the reply......
I am Big fan of yours 🙏
Nice Explanation..Keep making videos
Thank you, I will
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
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 )
@@Pepcoding ✔
Nice way of teaching
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 )
Perfect
what is the time complexity of this?
What is the time complexity of this solution?
For getting largest power, we can use Math.floor(log2(num)) where log2 can be computed as Math.log(num)/Math.log(2);
but bitwise operations are faster
Will recurssion called only one? for all the cases
loveed the soln
Thanks you Sir!
Keep learning.
And for better experience, visit nados.io, where you will get well curated content and career opportunities.
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 ???
questions are in perfect order on portal. use portal instead of youtube. Yes, stats will be brought back.
Beautiful explanation ❤
Glad you liked it, for better experience and well organised content sign up on nados.io and start learning.
maje aa gaya bero solution dekkh ke
Shukriya ji😊
Bs aise he apna pyaar aur sahyog bnaye rkhe hum pr🙏
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.
same thing actually 1
Nice sir
Sumit sir 🤟🤟🤟
Sir explanation is too good 🙌💯
keep motivating, keep learning and keep loving Pepcoding😊
thanks a lot :)))
amazing content
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
Nice Explanation, It would be great if you had explained in english
It can be more easily solved using
vector countBits(int n) {
vector ans(n+1);
for(int i=0;i
sir colour change kr liya kro please.... and best explanation
super 😍😍😍😍
thank u so much
Happy to help
very nice explanation
Thanks for liking. keep motivating, keep learning and keep loving Pepcoding😊
Sir, please also tell the time and space complexity of this approach
Can anyone please help me, how do I use the same logic using BigInteger class? Thank you in advance
In the Interview bit, this is partially correct. But why?
what's the time complexity?
playlist of this video???
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.
sir solution toh samjh aaraha bit manipulatio series ka..but ek problem hai..intuition nahi aaraha..jaise dp ya backtracking me pata hota tha ki jo bhi ki ku kiya..but in sab me aisa lag raha bas solution samjh aaraha..intuition develop nahi ho raha..any advice for that? Bit manipulation ki practice kaha se kiya jaiye?
beta 5-6 tricks he hain, iske liye jo maths important hai wo set theory hai.
My suggestion
1. Understand basic operations of bits
2. Revise set theory
3. Do these 30 questions, now go and test yourself on a random set of questions you will perform better.
Wow!
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
czcams.com/users/Pepcodingabout?view_as=subscriber
Time complexity of this code?
How is he using bitwise left shift operator to calculate power?
Please explain.
For clearing all your doubts visit on nados.pepcoding.com
Don't forget to follow us on Instagram instagram.com/pepcoding/
Respect bro
If you like our efforts, we request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
czcams.com/users/Pepcodingabout?view_as=subscriber
For clearing your doubts, you can join our community on telegram
t.me/pepcoding
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
thanks for the optimization! Appreciate your help
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
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.
@@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.
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.
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
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 )
@@Pepcoding yes sir i will , and will wait for question solving videos ,they are so good