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...
Пікірлер: 276
I think this is the most underrated youtube channel for programming believe me your channel will reach 1 Million subscribers soon :)
@techdose4u
4 жыл бұрын
Thanks for your motivation
@tonyz2203
2 жыл бұрын
true
I'm glad that I found this channel :)
@techdose4u
4 жыл бұрын
Ahhh.... 😁
You explain these problems so easily and in the best way ...... Amazing work sir
finest u tube channel for competitive programming .
amazing explanation. thank you!!! i was struggling with the intuition, but breaking it down was extremeyl helpful!
@techdose4u
3 жыл бұрын
Nice :)
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
2 жыл бұрын
So it's dynamic programming as we are using previous results
@AnandKumar-uy7nn
2 жыл бұрын
@@Mercer80 yeah !!
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
This is the best explanation. More kudos to you 💯💯
Saw many different ways to solve this problem on you tube and gfg but this was best approach. ❤
i like the way you develop the solution. take example, then have some observations. great job! thank you!
@techdose4u
3 жыл бұрын
Welcome
Amazing explanation, thank you so much.
just loved the explanation!
Your videos are all so good. Thanks for the conetent. Simple to understand and easy to implement
@techdose4u
4 жыл бұрын
Welcome :)
very clear explanation of the solution and the theory behind it, thanks very much :)
Great explanation!
Thank you so much sir for such a brilliant explanation. Love your videos. Thank you for putting so much effort :)
@techdose4u
4 жыл бұрын
Welcome :)
clear cut explanation. 1000 likes for the idea and another 1000 likes for easy explanation. Keep it up. You just earned a subscriber.
@techdose4u
3 жыл бұрын
Thanks ❤️
Great explanation for the DP solution!
Nowadays, I am searching for one problem in youtube, if tech dose has uploaded that problem then my problem becomes easy
Instant sub for this kind of content. Keep it up!
@techdose4u
3 жыл бұрын
Welcome :)
Best one even after 3 years!
Always the best!
This is the best algorithm for solving this problem ,good explanation sir!!
@techdose4u
2 жыл бұрын
Thanks ☺️
can u explain more optimized solution using just log 32 complexity or log num
thank you so much sir!
Now this is how you explain!!! Great work!!
@techdose4u
4 жыл бұрын
Thanks :)
This approach was fantastic :) Thanks a ton!
@techdose4u
3 жыл бұрын
Welcome :)
You rock, Duuuude! Learned a lot from your videos!!!!
@techdose4u
4 жыл бұрын
Thanks man :)
Chala help ayindi anna thank you so much Annaya
bow down to this guy.
Mind blowing power of observation. Thank you Keep up the good work @TECH DOSE
@techdose4u
3 жыл бұрын
Welcome :)
clear explanation
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
3 жыл бұрын
Practice will improve your ability :) so keep practicing.
It's not easy to come up with this solution but if you do...you are awesome !
what is the name of the app used for drawing?
Superb explanation
@TECH DOSE solution is great , but if the space complexity is o(n), then would it not fail for nos ~=10^9??
This solution is just wow! Mindblown totally.
@techdose4u
3 жыл бұрын
:)
what if we were given any random range instead of 0 to n? is there any O(n) solution?
Great explanation bro 🔥🔥
Best explanation. I watched Neetcode's video first but this explanation is a lot better.
@techdose4u
9 ай бұрын
:)
Bhaiya, you such a great teacher. You make us understand so patiently and easily. Thank you
@techdose4u
3 жыл бұрын
Welcome :)
Brilliant, you are a savior!
@techdose4u
4 жыл бұрын
Thanks :)
very nice! thank you!
@techdose4u
3 жыл бұрын
Welcome
I totally enjoy your explanations.
@techdose4u
3 жыл бұрын
Thanks :)
Thank you for the solution :)
@techdose4u
3 жыл бұрын
Welcome
EXCELLENT
Great explanation as always!!! Very much helpful!! Thank You!! Can you please make a video on time complexity and space complexity...
@techdose4u
4 жыл бұрын
Yea sure. I have started the playlist but not finished due to challenges. Once this is over, I will finish it.
simply awesome! Thank you very much :)
@techdose4u
3 жыл бұрын
Welcome
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?
Awesome Explanations !! Really helped a lot.
@techdose4u
3 жыл бұрын
Thanks :)
Great Explanation !!!!!!!!
@techdose4u
3 жыл бұрын
Thanks
great vid! subscribed!!!!!
@techdose4u
3 жыл бұрын
Thanks 😊
vector countBits(int n) { vectorbitcount; for(int i=0;i
Best youtube channel till now.
@techdose4u
4 жыл бұрын
Thanks :)
@krishangopal6795
4 жыл бұрын
TECH DOSE Sir please share your mail or contact number need placement related advice
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
3 жыл бұрын
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.
Crystal Clear Explaination
@techdose4u
2 жыл бұрын
Thanks ❤️
Excellent explanation !! Very easy to understand sir. thanks a lot for making this video.
@techdose4u
4 жыл бұрын
Welcome :)
Cool 👍
Thank you for the explanation
@techdose4u
2 жыл бұрын
Welcome 😊
Sir ye wali video bit manipulation Vali playlist me ni hai. Daal do pls
Thanks man!
@techdose4u
3 жыл бұрын
Welcome
i can understand from ur video
Please continue making videos in the upcoming June challenge too. Your videos are awesome!
@techdose4u
4 жыл бұрын
Thanks :)
Great!! How to come up with this kind of solution?
Seriously, this is one of the best Channel for coding problems. Such a nice explanation as always
@techdose4u
4 жыл бұрын
Thanks
sir , you are truly a genius ,always helped a lot..Thankyou
@techdose4u
3 жыл бұрын
Welcome :)
Very thankful for the work you’re doing mate !
@techdose4u
3 жыл бұрын
Welcome :)
Thank You Sir. Very precisely explained 🤓🙌🏻
@techdose4u
3 жыл бұрын
Welcome :)
great explanation and solution
@techdose4u
3 жыл бұрын
Thanks :)
Superb explanation and easy to understand the solution. Thanks keep going ...
@techdose4u
3 жыл бұрын
Welcome :)
Tagda bhai.. GFG DSA course me bhgaa dia tha iss topic ko
@techdose4u
3 жыл бұрын
Thanks bhai 😀
ooooooohhhhh... you are really awesome sir...!
@techdose4u
3 жыл бұрын
Thanks :)
this is explanation is lit man , I am totally mesmerized
@techdose4u
2 жыл бұрын
Thanks :)
Sir this video is such a helpful to me.. to understand bit manipulation 😊☺️.. thank you..
@techdose4u
4 жыл бұрын
Welcome :)
Excellent Explanation
@techdose4u
Жыл бұрын
Thanks :)
Nice Explanation
@techdose4u
3 жыл бұрын
Thanks
Excellent sir !!!!!!!!!!!!!!!!!
@techdose4u
3 жыл бұрын
Thanks
Your explanation are just amazing 😍😍
@techdose4u
4 жыл бұрын
Thanks :)
Awesome explaination
@techdose4u
2 жыл бұрын
Thanks 😊
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 :/
thank u so much sir 😭😭😭
Clean and crisp explanation...
@techdose4u
4 жыл бұрын
Thanks
sir please explain how to solve it in log(N) time using O(1) space, im unable to understand the solution provided in GFG
@techdose4u
3 жыл бұрын
You can do the logN solution easily after you understand the O(N) solution. Just little tweak is required :)
you rock sir
Amazing solution thanks
@techdose4u
3 жыл бұрын
Welcome :)
fantastic solution
@techdose4u
3 жыл бұрын
Thanks :)
Thanks bro !
@techdose4u
2 жыл бұрын
Welcome 😄
Very nicely explained, Sir
@techdose4u
2 жыл бұрын
Thanks 😊
great explanation
@techdose4u
3 жыл бұрын
Thanks
just wow !!! nice explanation sir
@techdose4u
4 жыл бұрын
Thanks :)
The best solution I found so far 😁🥳
@techdose4u
3 жыл бұрын
Nice :)
Beautiful solution
@techdose4u
3 жыл бұрын
Thanks
Will improving solution from O(32*N) to O(N) will make any difference because asymptotically both the solution are of same complexity?
@techdose4u
4 жыл бұрын
Yea it will. If think carefully then 32N is actually NlogN. Ask yourself if improving time from NlogN to N will make any difference!!
Mind == blown away
@techdose4u
4 жыл бұрын
🤣 a coder's way to represent feelings
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
3 жыл бұрын
Thanks for your wishes. Touchwood 😀
very nicely explained
@techdose4u
3 жыл бұрын
Thanks
bro, you're amazing
@techdose4u
2 жыл бұрын
Thanks :)
Thankyou so much sir
@techdose4u
2 жыл бұрын
Welcome 😊
dp[i] = dp[i>>1] + (i&1); can also be done and it is faster than / and %