I think sometimes he tries and submits the ques beforehand 1 time before making the video. I have seen "Submitted 5 minutes : Accepted" from in the previous submission list a few times. xD Btw not saying it in a bad way, no one likes to do retakes for videos :| - I'm a big fan
There are indeed prime numbers greater than the number in its square. The smallest prime factor of a composite number n is less than or equal to root(n). So there is no point in checking further than the number as those get covered in the next numbers in the list and reduces complexity.
For anyone confused about i*i part, watch th-cam.com/video/T0XbxCYLBmc/w-d-xo.html (no affiliation, I was one of the confused ones that googled around)
You didn't explain why this solution is faster than the O(n sqrt n) basic solution. Basically you have the sum n + n/2 + n/3 + n/5 +... + n/prime With prime
wouldnt be better checking all the numbers from 2 to half of the upper bound.. so 2 to n/2.. cause if u think about it, the factors must be less than or equal to half of the upper bound.. cause if it is bigger than n/2... (2 * factor ) > n
Couldn't you also not do the count and just count how many you turned to true? In other words, if you have 20 elements in the array, you turn 15 of them from false to true, then you know the count would be 20 - 15, or 5. Saves that extra loop.
Any non-prime number will always have a factor that is less than or equal to its square root. For example, pick 36. It's factors are - 1*36, 2*18, 3*12, 4*9, 6*6. In each case, there is at least one number satisfying the above condition. So here, by considering all numbers up to the square root of n, we can successfully eliminate the non-prime numbers up to n. Hope this helps.
Hey Kevin, love your work. Great job. Its been a while I have been trying to learn dp and I always get stuck in the resources I should use and where should I start. It would be great if you could make some to help us
I think there is also no need for counting loop because when we go for negation in first loop that time we increment primeCount. may be Kevin I'm wrong :)
Hi Kevin, This was a great solution, but i was not able to understand line #9 (if(prime[i])), I understood that its optimizing the solution but not able to understand mathematically. Could you please explain with some example.
Coming from leetcode, knowing the solution already, this doesn't add much to it! ...I thought you could focus more on the non-obvious parts (e.g. i*i < n)
think of it as an if statement to check if the value of the current int squared is less than the value of n which is also the length of your primes array I think using n here makes more sense and involves less typing
The bruteforce method is actually super easy but leetcode won't accept my submission because of its n^2 runtime. Do you think most interviewers would accept the bruteforce method but then ask you to think about a potential better solution?
For those who are confused about i*i, let's consider-: 1. non prime number let's say 42 factors are 2*21(both are factors), 3*14, 6*7, 7*6, 14*3, 21*2 note these factors start repeating identically after square root i.e 6 (6*6) for numbers that are not prime and not multiple of primes, we would quickly find factor and break but for prime * prime type numbers we have to go till square root ex (11*13) (go till 12* 12) 2. prime number lets say 31 if this number was non prime based on factors done in step 1, we would have found something till square root of the number since, we didn't find we assume it to be prime, so ideally the analogy of factor is taken from non prime and applied to all numbers but it will optimised the prime and prime * prime type numbers because we stop at square root Complexity - O(sq1 + sq2 + ...sqN)
I think I'm dumb, but why wouldn't looping 0, n and checking if each number in between is a prime number work? I tried this but it would only pass some test cases. Can't figure out why.
think I just sieve of Eratosthenesed IN MY PANTS thanks for another great solution actually was able to get this one brute force styles but I was like mannn dis is ugly let's see what Kevin got up his sleeve was not disappointed lols
Hello, how you know that this problem was asked in google? can you tell more such problems which are not on leetcode. How to practice for google and other companies interviews.
He DOES NOT solve them while recording it...I don't understand why people think he does lolol he learns about the problem, gets to a solution first, plans an explanation, and THEN records the video.
ERATOSTHENES WAS THE MAN
lol, of course coz he was not a WOMAN. see negated the logic like you told at the end. :P
Algorithm's authorship appears to belong to David Gries, Jayadev Misra. A Linear Sieve Algorithm for Finding Prime Numbers [1978] :)
What is the time complexity?
@@algorithmimplementer415 on log log n
Let me check if it works-->
Normal Person: hits "Run"
Kevin: hits "Submit"
hahahahah
I think sometimes he tries and submits the ques beforehand 1 time before making the video. I have seen "Submitted 5 minutes : Accepted" from in the previous submission list a few times. xD Btw not saying it in a bad way, no one likes to do retakes for videos :| - I'm a big fan
@@Spectraevil haha
I think that's the reason why he moved his facecam video on top of it. Smart!
This is basically just a working solution. No explanation or complexity analysis.
There are indeed prime numbers greater than the number in its square. The smallest prime factor of a composite number n is less than or equal to root(n). So there is no point in checking further than the number as those get covered in the next numbers in the list and reduces complexity.
I hate math problems too, I was working on this today. and got pretty frustrated that I couldn't solve an 'easy' question /:
it's medium now
There is no explanation here whatsoever, only text in the video description helps
for real, what a terrible explanation
Loved the explanation. But how is it faster than O(n^2)?
I think because the for loops aren’t nested, that way the program doesn’t reiterate over the same dataset
because there is an 'if'
how is the naieve solution of checking each number below n, O(n^2) anyway? why am I mistaken when i think it's O(n)?
this guy shoots tutorials as if hes shooting an apologies video
Can anyone please guide why we did i*i into the 1st loop..why didn't we simply check for I
For anyone confused about i*i part, watch th-cam.com/video/T0XbxCYLBmc/w-d-xo.html (no affiliation, I was one of the confused ones that googled around)
Thank you!!! This link you provided is very helpful!!
You didn't explain why this solution is faster than the O(n sqrt n) basic solution.
Basically you have the sum n + n/2 + n/3 + n/5 +... + n/prime
With prime
wouldnt be better checking all the numbers from 2 to half of the upper bound.. so 2 to n/2.. cause if u think about it, the factors must be less than or equal to half of the upper bound.. cause if it is bigger than n/2... (2 * factor ) > n
Thank You So Much Handsome Person!
Couldn't you also not do the count and just count how many you turned to true? In other words, if you have 20 elements in the array, you turn 15 of them from false to true, then you know the count would be 20 - 15, or 5. Saves that extra loop.
Can you explain the time complexity of this solution
Could you explain why the check is only till i*i? I'm confused about that.
Any non-prime number will always have a factor that is less than or equal to its square root.
For example, pick 36.
It's factors are - 1*36, 2*18, 3*12, 4*9, 6*6. In each case, there is at least one number satisfying the above condition.
So here, by considering all numbers up to the square root of n, we can successfully eliminate the non-prime numbers up to n.
Hope this helps.
This could easily exceed the heap size, is there any way to overcome that without actually increasing heap size or physical memory?
Yes. Calculate primes upto square root of the number you seek, then use that to calculate the desired prime number.
Kevin, I submitted this approach on leetcode and it still said Time Limit Exceeded :(
Hey Kevin, love your work. Great job.
Its been a while I have been trying to learn dp and I always get stuck in the resources I should use and where should I start. It would be great if you could make some to help us
Thanks! I'll see what I can do :)
@@KevinNaughtonJr thanks Kevin.
Naman Gupta anytime
I think there is also no need for counting loop because when we go for negation in first loop that time we increment primeCount. may be Kevin I'm wrong :)
I was thinking the same
Hi Kevin,
This was a great solution, but i was not able to understand line #9 (if(prime[i])), I understood that its optimizing the solution but not able to understand mathematically. Could you please explain with some example.
Coming from leetcode, knowing the solution already, this doesn't add much to it! ...I thought you could focus more on the non-obvious parts (e.g. i*i < n)
hey kevin i know it must be a silly doubt to as but could you please elaborate why the first for loop has i*i
think of it as an if statement to check if the value of the current int squared is less than the value of n which is also the length of your primes array I think using n here makes more sense and involves less typing
@@Endlessvoidsutidos Thanks
@@rahulratra6672 np was confused on this myself till I spent some time digging into it
i wtched 4-5 times, still not sure why its that way
Time Limit Exceeded
The bruteforce method is actually super easy but leetcode won't accept my submission because of its n^2 runtime. Do you think most interviewers would accept the bruteforce method but then ask you to think about a potential better solution?
ofc
Bro, thanks for videos.
Where is first Leetcode problem eg. problem number 1, this is problem no 204, I have to start from first, please do help.
For those who are confused about i*i, let's consider-:
1. non prime number let's say 42
factors are 2*21(both are factors), 3*14, 6*7, 7*6, 14*3, 21*2
note these factors start repeating identically after square root i.e 6 (6*6)
for numbers that are not prime and not multiple of primes, we would quickly find factor
and break but for prime * prime type numbers we have to go till square root ex (11*13) (go till 12* 12)
2. prime number lets say 31
if this number was non prime based on factors done in step 1, we would have found something
till square root of the number since, we didn't find we assume it to be prime,
so ideally the analogy of factor is taken from non prime and applied to all numbers but it will
optimised the prime and prime * prime type numbers because we stop at square root
Complexity - O(sq1 + sq2 + ...sqN)
Hey man can you do shortest Subarray with Sum at Least K? Leetcode 862. I don’t understand the solution the gave. The brute force is just too slow
you have beautiful eyes
can this be solved by dynammic programming ?
I think I'm dumb, but why wouldn't looping 0, n and checking if each number in between is a prime number work? I tried this but it would only pass some test cases. Can't figure out why.
0 and 1 are not primes
Very poor explanation why i*i < primes.length. And you very conveniently skipped that in description part too
Awesome!
what is the time complexity of this solution?
time complexity is O(n log log n) and space complexity is O(n), you know memory is cheaper :D
think I just sieve of Eratosthenesed IN MY PANTS thanks for another great solution actually was able to get this one brute force styles but I was like mannn dis is ugly let's see what Kevin got up his sleeve was not disappointed lols
does ' if primes[i] ' mean if the primes array has the value i?
primes[i] is a boolean array. if(primes[i]) has the same meaning as if(primes[i] == true) or != false. this is only for boolean values.
Hello, how you know that this problem was asked in google? can you tell more such problems which are not on leetcode.
How to practice for google and other companies interviews.
He knows because LeetCode premium will tell you which companies ask the question under the "companies" tab of the question
Why are we using i*I again
The way you solve these problems is so Effortless
He DOES NOT solve them while recording it...I don't understand why people think he does lolol he learns about the problem, gets to a solution first, plans an explanation, and THEN records the video.
How can we come up with this awesome solution?
Hopefully this video helped!
just one of those things that as a software engineer you need to know. Alternatively be a mathematical genius...
@@treyquattro Got it! Thanks bud!
👍
I don't get this problem weird
Dude your videos are consistently unintuitive and explanations are bad -- i go to other videos and understand the solution in 30s