Basic Maths for DSA | Euclidean Algorithm | Strivers A2Z DSA Course

hey everyone welcome back to the channel I hope you guys are doing extremely well so this video is going to be another video from the Strivers A to Z DSA course and this is India's most in-depth TS algo course why do I see that because this course has 455 modules I can guarantee you that you can take any paid batches any free courses none of those courses will have four 55 modules this is an extremely in-depth TS algo course that can teach you everything in breadth about DS algo and in the previous videos we have covered step 1.1 and 1.2 and regarding step 1.3 I've added a video on C plus plus STL on the playlist you can go and watch it regarding Java collection I'll be adding a video in the future not now if you need a video now you can go to YouTube and you'll find a lot of other resources from where where you can study so in this video we will be discussing about basic maths why am I teaching just the basic maths as of now so you're starting off as of now your brain not be that mature so if I teach you the advanced level Concepts you might understand but it won't be that convenient for you that is why my teaching way is very different what I do is I usually start off with the basic stuffs I give you a lot of time to absorb it and then we move on to the advanced part this is why all the basic stuffs are initially there and then we move on to the DS algo and the step 8 we have a section as advanced mathematics I'll be covering everything that is related to advanced mathematics that might be asked in interviews but as of now we will be learning basic maths now these are the problems which we will be solving but before that let's learn some basic maths concept so before solving all the problems that are listed under basic maths we'll be starting off with the basic maths concept I'll be teaching you the concepts initially and then we can solve all the problems listed under the section the first concept that I'll be teaching you is the digit concept remember one thing this is a very very important concept because if you know how to play around digits then you'll be able to solve most of the problems in basic maths so let's understand the digit concept imagine I give you a number like 7 7 8 9 so this is the number that I'm giving you now I ask you to perform extraction of digits I ask you to perform extraction of digits let's learn the extraction of digits and after that you will see how we can implement the extraction of digits in order to solve most of the problems okay so when I say extraction of digits what does it mean it means I read 9 I need eight I need seven I need seven I need all the digits individual okay so what is this digit 9 can I see this if I do a module of 10 I'll actually get 9. you might ask why if I ask you the numbers that are divisible by 10 what are they 10 20 30 40 50 60 70 so on 100 and so on do you see a pattern all the numbers that are divisible by 10 are actually ending with zero is it right so can I see if I'm doing a modulo 10 what is the meaning of module operator in B segments the module operator says I will divide the number by 10 and whatever is the remainder that is what I'll give you so if I say if I'm dividing this number by 10 what is the nearest number obviously that will be 7 7 8 0 if I divide it by 10 this is what the nearest number will be and can I see that the remainder then will be 9 because if I divide it by 10 then this is where the division like this is the number which will get divided by 10 and after that we'll be left out with 9 that is why when you do a modulo 10 you always get the last digit so you get the last digit at as nine so this is how you get the nine digit if I ask you can I get the next digit 8 how will you get the next digit a very simple you say okay this number let's divide it by 10. so if I divide 7789 by 10 can I say I'll get seven seven eight point nine can I say this if I divide the numbers 7 7 8 9 by 10 I'll get 778.9 and if I take an integer round of if I take an integer portion of it the integer portion is seven seven eight so what you will do is in order to go to the next step you will say divide by 10 if you do a division by 10 you'll actually get seven seven eight point nine but you just take the integer part that is why you get 778 so once you have 778 with you if I need the last digit which is eight how do you extract it again the same way you see can I divide a modulo rise with uh 10 if I to a mod of 10 I'll actually get 8 why because the nearest number will be 77 0 which is divisible by 10 which will still leave a remainder of 8 so I get the digit 8 as well now can I see if I require the next digit 7 can I again do a division by 10 I do a division by 10 can I say I'll get 77 why because if I write 7 7 8 by 10 I'll get 77.8 and the integer portion is 77 so I get 77. again if I have to extract the last digit can I say I'll do a modulo rise a modulo of 10 and I'll get 7 I will ends up again extracted seven now if I need the next extraction I again divided by seven so I divided by 10 and I'll get 7 because 77 because 77 divided by 10 is 7.7 and the integer part is 7 so I get seven if I do a modulo rise of 10 will actually again get 7 why will you get again seven very obvious because the nearest number that is divisible by 10 to 7 is 0. thereby you get a remainder of seven so you get seven after that if you again try to divide it by 10 this time you'll end up getting 0 because if I take 7 divided by 10 it'll be 0.7 and the integer part is 0. so can I see if I get an integer part is 0 can I say I've extracted all the digits I have and if you see the extraction has been done in the reverse order and all the digits have been extracted as simple as that so this is how you can easily extract all the digits so if I try to write the pseudo code how will the pseudo code look like can I see if I have the N I can take take it from the user I can take the N from the user and imagine I'm asking you to print all the digits extract all the digits like nine eight seven seven and you can print it so how will you do it it's very simple I will be like okay while I know what is the last step last step is the extraction goes on from n when it is 7789 to n 0 so I'll be like I'll go on till n is greater than 0 which means till n doesn't becomes 0 right and can I see the extraction is very simple the first time n was seven seven eight nine if I had to do an extraction it's very simple can I say the last digit is nothing but n modularized 10 if I do an n modularized 10 I'll get the last digit 9 and in order to get the next digit what I do is I say n is n by 10 and this is how I can do it so what will happen let's do a dry run at first imagine I give the user gives NS 7 7 8 9 10. so this says 7789 greater than 0 which is true so the last digit happens to be 7789 modularized 10 and the last digit is 9. if you want to print this last digit you can definitely put a print operation in C plus plus it is C out in Java it is system.out.printl so you can go ahead and print the nine once you have done this can I say if you do seven seven eight nine by ten then the N will reduce itself will be the value of n now can I say the value of n will be nothing but 7 7 8 this is how the first iteration first iteration will happen and then it will reach here then again goes here and when it goes here it will be a new iteration and can I say this time the iteration will be 778 because n has changed itself to 778 and 778 greater than zero what I'll do is I'll quickly erase this because it's the next iteration let's quickly erase this and the next iteration what will happen it will say 778 modularized 10. the last digit this time will be eight again you can print that last digit and this time it will be 778 by 10 hence n will become 77 again the iteration will go and will be 77 greater than 0 and this way all these steps will be performed at the end of the day the value of n yes the value of the N will be 0 ends the while loop will be false and I can say that the execution has been completed and we have successfully extracted all the digits in the reverse fashion very important in the reverse fashion got it so this is what is the concept of extraction of digits and this is going to help you solve a lot of other problems as well so now let's look at the first problem it states count digits let's understand the problem given the number n INE out and return the digits present in a number very simple it is 156 is the number and the number of digits is 3. Imagine The N is given as 7 it has just one digit it will be given an N it will tell me the number of digits so if I go back to my iPad can I see if I give you the number 7789 this has four digits can you solve this problem using the extraction of digits can you it'll be like this is super easy why because you know the extraction of digits you know one digit two digit three digit two digit the digits are extracted four times so can I say I can keep something like a counter variable over here and you know the number of times the extraction happens that is the number of times the digit will be so can I say I can put a counter equal to counter plus one on the logic of extraction of digits if I do this can I say I'll be able to count the number of digits and eventually if I print the count over here can I see that I'll always have the count of digits of Any Given N I can usually in coding rounds or any interviews you just have to code the function the function is an INT function that means you have to return the count of digits and they'll be giving you the input so you are given the variable you just have to return you have to just write the code inside the function int Main and everything will be written on the back end I've already discussed about this in the pattern video in case you haven't watched it please go back and watch it so this was the code that we discussed on the iPad right so the count stores the count of digits so I'll just return the call and then I'll go ahead and run the code and I'll see that it is running absolutely fine and then I'll go ahead and submit this so this is how you can easily solve this particular now remember one thing this last digit does not have any significance so you can remove it so that was for extraction of digits but this is kind of reducing the numbers so the number of times it is divisible by 10 is the number of times uh the digits are now since I've removed the module operation we observe something can I say the number of times it is getting divisible by 10 the number of times it is getting divisible by 10 is the count of the digits it is and this is where something like logarithmic log base 10 7789 if you do this in your calculator you'll actually get something like 3.89 something so this is the value that you'll get if you do a log base 10 of the number and then if you can add a 1 to it this will be 4.89 and if you take an integer of it that will be 4. so this is another way to find count of digits what you do is very simple you say count is equal to log 10 the number plus one and you're saying take the integer or you can just Auto cast it like type cast into integer this this is how whatever you get this is converted to an integer if you're getting 4.89 it'll be truncated to 4 and now let's run this and see if it is running fine okay so it says out of scope log 10 was not declared so if you find such errors what you can do is you can go to Hash include that's basically because in their back end they might not have added all the directories they can go ahead and add all the directories and that will start working fine so once you've done this you can go and compile and you're seeing that you're seeing this uh that this is also running fine so this is one of the other ways to count digits as well but but the primary concept is extraction of digits and that is what you should focus on now if I discuss the time complexity over here what will be the time complexity the time complexity will be nothing but log base 10 n this is the Big O of time complexity while log base 10 and the reason was very simple you saw this is getting divisible by 10. how many times is the loop running the number of times it is getting divisible by 10 so this is why you will say time complexity is near about log base 10 and this was 3.89 near about 4. the number of times this Loop did run was four yeah you can avoid these operations these are single operations because Imagine A number being very large these will be considered as unit operations that is why the time complexity is log base 10 and got it whenever there is division remember this Whenever there is division if the division is happening by 10 you say log base 10 n if the division is happening by 2 you say log base 2 and if the if the division is happening by 5 you say log base 5 n this is how you compute the time complexity of like this is this is how the law algorithmic time complexities are so whenever you're writing a logic where the number of iterations depends on Division and you're dividing dividing that is when something like logarithmic will come into the time complexity that time the time complexity will not be Vigo of n if the number of iterations is based on division time complexity will be logarithmic remember this always so you solve the first problem count digits uh the next problem is reverse a number let's go to the problem it states a write a program to generate the reverse of a given number print the corresponding reverse number if a number has trailing zeros then its reverse will not include them for example the reverse of one zero four double zero will be four zero one instead of 0 0 4 0 1 and these are some of the examples so let's get back to our extraction of digits constant so according to the problem what they are wanting is if I'm giving you the number 7789 the reverse of this number will be 9877 now we know that the extraction of digits happens in the reverse fashion where we generate 9 then we generate eight then we get 7 then we get 7. somehow we need 9877 which is the similar fashion this is where the basic maths comes in what you do is you Define a variable sum or maybe reverse number reverse number equal to zero and you say reverse number equal to reverse number into 10 plus last digit remember this this is what you say reverse number into 10 plus last digit let's see how it works so I'm saying initially reverse number is 0 to start off let's do the step by step First Step 9 gets generated so what am I doing is 0 into 10 because reverse number is 0 at the first step the first step 7 7 8 9 Mod 0 10 will generate 9 and N would have as of now become something like 7 7 8 9 by 10 so n would have as of now become 778 and reverse number says reverse number is zero into 10 plus the last digit 9. so so the number becomes or rather the reverse number as of now is 9 right this is what the first iteration is let's do the next iteration the next iteration will be I'll just quickly omit this off then the next iteration can I say it's 778 greater than zero and 778 modulo 10 as the last digit is eight I can say this and this will be 778 by 10 so n will become 77 this time reverse number is stored as 9 because you stored reverse number as this value so this is nine so what you do is you say 9 into 10 plus the last digit 8 so what do you get is 9 into 10 plus the last digit 8 which makes it 98 the next time you get 7 the reverse is 98 into 10 plus 7 which is 987 next time it is 7 so 987 into 10 plus 7 is 9877 so you got the reverse number then quite simple why did this work it is very easy understand you are getting in last digit you're easily getting the last digit 9. and after that you're getting the next last digit 8 and you somehow want to add 8 to that nine you somehow want to add 8 to that 9 and the easiest way is if you can somehow add a 0 to this line it will become 90 and then if you add 8 to it it will become 98 similarly if you want to add 7 to it if you want to add a 7 to 8 make it 987 yeah again add a 0 and then a 7 to 8 it becomes 987 again if you want to add a 7 you again add a zero this is why at every step I am doing reverse number into ten whatever you have generated into 10 that will allow the last unit digit to be zero then when you add a digit goes and gets into that place as simple as that so again you saw that extraction of digits is actually handy so what I'll do is I'll take the number and I'll keep the reverse num equal to 0 and then I'll go ahead and say n greater than 0 and I can say last digit is n modulo 10 I can say reverse number is reverse number into 10 plus last digit I guess n is n by 10 and the same time I can say C out of reverse number is what I need perfect and I'll quickly run the code and see if it is running fine it is let's quickly submit this and this should be running fine this day so the reversal number is solved again with the concept of extraction of digits next problem is check palindrome now when I go to uh the palindrome problem let's understand the problem it states write a program to determine if a given number is palindrome or not print true uh true if it is palindrome or false otherwise so overhead States palindrome of the numbers for which reverse is exactly same as the original one for example one to one because if you take one to one and you do a reverse of it one two once reverse is one to one that is why it is called as palindrome so if I go to the iPad and I write some other palindrome numbers it's like one double three one if you write the reverse of it it stays still one double three one something like 11 11 in itself is a parent drop seven seven in itself is a palindrome whereas one two three the reverse of one two three is three to one this is not a palindrome so any number which on reversal is the same number is a palindrome number so the definition of palindrome number says reverse of a number so if I somehow can generate the reverse of a number if I somehow can generate the reverse of a number which I've already did and then compare it with the original n and if they come out to be same can I say they are parallel I can so over here if you remember we took a reverse number and at the end of the day the reverse number was nothing but the reverse number and now if I can compare this reverse number with the original number with the original number which is n and if they come out to be same I can say it is palindrome like if this is true I can say this palindrome or I can say it is not bad can I see that but wait wait if you remember we were dividing in by 10. and at the end of the day n was zero so does n have the original number no because we were we are doing operations with n which has made n to be 0 at the end of the day so what I need to do is maybe I need to store a duplicate of n in some top variable and instead of comparing it with n i can compare it with the duplicate because n will be 0 at the end of the extraction of digits it's very important to store a copy of n somewhere so that it can be used to compare it with the reverse of a number that is the only change that you have to do that is the only thing that you have to keep in the mind so remember this was the code so what I'll do is I'll just go ahead and say duplicate equal to n and over here I say if dope is equal to reverse number I can go ahead and print true which is what they want which is true or else you can just go ahead and print for whereas what they required okay with a small quickly run it and see if it is running fine should be and let's quickly submit this on submitting you see that it is running absolutely fine next one is gcd or hcf but before that we will be solving Armstrong numbers so what is the definition of Armstrong number it's very simple imagine you're given this number p71. you take 3 Cube 7 Cube plus 1 Cube if taking the cubes of these numbers like cubes of these digits and adding them up sums up to the number itself that is what you call as an Armstrong number even if you take one six three four one Cube plus six cube plus 3 Cube plus 4 Cube if you sum them up you actually get one six three four but something like 35 if you take 3 Cube plus 5 Cube this is not going to be equal to 35 this is going to be equal to 134 so this and this are not same whereas 1634 and the summation of cubes of its digits is one six three four so you call one six three four as an Armstrong number or three seven one as an Armstrong number so I hope you've got the definition of Armstrong number so if you have got the definition of Armstrong number you know how to solve it I've already taught you the extraction of digits you know how do you extract line you know how do you extract eight you know how do you extract seven just have to do a cube of it so can I see this time instead of taking any such duplicate or reverse N I can just take a summation because I need to some cubes and last digit is what I have to sum can I say sum equal to sum plus last digit multiplied Thrice last digit into last digit into last digit can I do this so first time nine comes in what happens 9 into 9 into 9 gets added to sum next time 8 comes in eight into eight into eight gets added to the sum so everything is getting added first time 9 into 9 sorry 9 into 9 into 9 got here next time eight went eight into eight into eight next time 7 came in 7 into 7 into 7 next time again seven came in seven into seven into seven so can I say at the end of the day some will be storing the summation of digit cubes and after that you need to just compare it with the original end so maybe again keep a duplicate variable which stores the end because at the end of the day you have to compare if this and the duplicate are same if this is and you say it is an Armstrong if this is not it's not a numbers again what logic worked extraction of digits if you know how to extract digits you can play around with them and you can solve this problem so Armstrong number is completed and the next problem that we will be doing is print all divisions so when I say print all divisors what does it mean imagine I take a number like 36 and ask you what are all the numbers that divide 36 so you can say one is something which completely divides 36 you can say 2 is something which completely divides 36 you can again say 3 is something which completely divides 36 4 is something which completely divides is 5 something which completely divides 36 no if 36 is divided 5 it leaves the remainder of 1 so not five six is something which does it 9 is something which again does it and 12 is something which does it then 18 is something which does it and then 36 is something which does so if I talk about 36 divisions of 36 are 1 2 3 4 6 9 12 18 and 36 these are the divisors of 36. the question is very straightforward you have to print all of them in this particular order okay now how do I do that it's very simple one thing I know for sure is if I'm talking about devices or factors they're definitely going to lie between 1 to the number itself can I see all the divisors will be between 1 2 and itself because anything greater than n will never divide and for sure so if I know all the divisors are going to be between 1 and N can I just loop from one to n that's my first thought process since I know the divisions are from one to n my first thought process is very simple so let's do one let's start the loop from I equal to 1 I lesser than equal to n and I plus plus this is something I know for sure so I is used to loop around now the first value of I is 1 then it's two then it's three then it's four then it's five and then so on till 36 in this case if it is n so how do you determine that this I is a part of all the divisors it's very can I see if it is completely dividing if I is completely dividing n then it is a factor or a division and what do you mean by completely dividing it should leave a remainder of zero when I say leaving a remainder of 0 does it mean if I do a modulated of I fedu n module y the value should be 0 because it's completely divisible by what I will do is I'll say okay if n modulo i is equal to equal to 0 I will go ahead and print I and C plus plus C out in javasystem.out.printel I'll go ahead and print out I so in this way I'll be able to print all the factors of a particular n if I talk about the time complexity ask you what is the time complexity of this code you'll be like sorry but it's very simple since the loop is running from 1 to n it's taking n iterations and this is an unit operation so let's not uh calculated thereby the time complexity of this particular approach is nothing but B go off and very simple over here they have given us everything I want us to write this print devices function let's write the print business function it takes an n and as I said it's very simple you go from one you go until n and you say I this one and you know if n modulo i is equal to equal to 0 you say C out I and then you give a better space that's so what you need to write and on submitting you will see that this is running absolutely fine but the time complexity is because of N I don't want a bigger of end time complexity can I do it in a much better way I can but it requires a bit of mathematical observation Let's uh see that mathematical observation so for 36 I said that 1 was a factor if one is a factor one has to be multiplied with something in order to get 36 so one was multiplied with 30. and if you carefully observe if this is one and the number is 36 the other number will always be n by 1. if it is 2 the other number will be n by 2 which is 36 by 2 that means 18 so you get 18. next time it was 3 so the next time it is 3 so when I take three it is nothing but 12 36 by 3 because 3 into 12 will be 36 the next way when I take 4 that is 4 into 9. the next time when I take six it is six into six next time the next factor is actually nine and then you multiply it with four the next factor is 12 and you multiply it with p and the next factor is 18 you multiply it with two and the next element is 36 you multiply it with one so if I if I have to write all the factors these are all the factors these are definitely all the factors right but do you have a bit of observation if I draw a line at this portion if I draw a line at this portion and I take this and I take this on the equal 1 into 36 36 into one so can I see even if I consider everything before the orange line I will get one I'll get to I'll get three I'll get 4 I'll get 16 36 I'll get 9. I'll get 12. I'll get 18 and I'll get 36 even if I take everything before the Orange Line even if I take everything before this Orange Line do I get all the fact I do so do I need to go beyond this orange line no so what is this orange line if you carefully observe what are you doing a small number into a big number a small number into a big number a small number into a big number same number same number and then a big into small a big into small a big and too small can I see this is nothing but the square root of n because when you take square root of n square root of 36 is 6. Beyond square root the numbers will grow the numbers will grow and it will nothing but a replication of the upper half the replication of the upper half so thereby this is nothing but a repetition of the upper half thereby I can say even if you Loop till square root of n even if you Loop till square root of n you actually can get your factors oh if this is one this has to be n by 1 if this is 2 this has to be n by 2 if this is 3 this has to be n by 3 if this is 4 this has to be n by 4 if this is at R 6 this has to be n by 6. so can I see now the looping is going to be very straightforward I look from I equal to 1 till I less than equal to square root of N and I plus plus enabled and can I see if n modulo i is a factor then print I as one of the factors print I as one of the factors what is the other Factor we just now found out the other Factor was n by I but we need to be careful what is the careful observation if it is 6 the other Factor might be six so there are not two different factors so if you're taking the second Factor if you are taking the second factor to n by I just make sure that n by I is not equal to Y because the second Factor might turn out to be the same factor it's very important the N by I which is the second Factor must be compared with I and if they are not same you can say that maybe print that's your another Factor that's it so first check if I is a factor printed now the other Factor n by I with which the I will be multiplied just check if this is not equal to I if it is not that's the second fact that's it so if you go ahead and print this the printing will be something like this first one and 36 will get print next 2 and 18 will get printed next 3 and 12 will get printed next 4 and 9 will get print next one I is 6 6 gets printed but the other factor is 6. it builds this condition check thereby the other six doesn't get printed so all the factors are printed but they are not printed in a proper yes they are not printed in a sorted way so what you can do is whenever you are getting all the factors probably you can store them into a data and if you have seen the C plus plus STL video you know which data structure you can use you do not know what will be the size or what will be the number of factors the data structure that you will be using is a list a list in Java or a vector in C plus plus we'll be using an undefined like you cannot Define the size of the radius structure I'll be using a list okay and in that list you can store it you can store it store store so everything will be stored in the list once you have stored in the list sort the list and if you sort the list you will get everything in the sorted passion so if I go back to the code what did I see we will be going till square root of n right it will be going till square root of we know this is a factor and we need a list now so let's take a list this is our list vector and we know LS dot push back of i a pushback i and we know the other factor is n by I if this is not equal to I that's the other Factor again we will say list can you store the other factor and the other factor is n by I once you have stored everything can you go ahead and say over here sort LS dot begin ls.in once you have done this just need to print it you know how to print it this is how you print the list C plus plus STL video guys so I'll just I trade on the list and I'll print the list with space it's all all of them are correct and I'll go ahead and print and it will be correct why did I sort it because they wanted us to print everything in the sorted order it's very important to sort the list if I talk about the time complexity what will be the time complexity something before discussing the time complexity you're writing I less than equal to square root of n instead of this because square root is a function and every time the function will be called because square root is a mathematical function in C plus plus STL this will be called every time which will take time itself instead of writing this you can actually write I into I lesser than equal to n so it'll be like when I reaches 6 it will be like 6 into 6 lesser than equal to 36. it'll work the dominant goes to 7 7 into 7 is not equal to 36 so this will be false correct so this is the other way of writing for the square root this is what you can write so can I say this Loop is running for we go of square root of n times can I say this that this Loop is running for we go of square root of times and then the number of factors whatever is the number of factors we are sorting it the internal sorting function takes n log n what is the internal sorting function taking n log n what is n a n is the number of factors okay n is the number of factors right so can I say n is the number of factors n is not the original n it is the number of factors and then you're going ahead and printing it so again taking a number of factors time to print it whatever is the number of times so the overall time complexity in this case is we go of square root of plus we go of number of factors into log of number of factors so number of factors into log of variety properly number of practice what it quite simple and then plus this so big of this plus we go of this plus we go of this is the time complexity but the motive was to teach you that you can also find factors in B go of square root of n got it I can say I've also done print all divisors in both the ways now what is the next question it states check for Prime so what is the definition of a prime number a lot of you will say a number that is divisible by one and itself this is a wrong definition why because according to this definition one is a prime number because one is divisible by one and one is divisible by itself which is one it's a wrong definition instead of this the definition that you should always keep in mind is a number that has exactly two factors one and itself that's a better definition one and itself a number that has two factors which is one in itself so if you remember we just now computed factors eight so if you're given a number something like 11 can I say 11 has a factor of 1 and 11 itself any of the number doesn't divide syllabus so 11 is a prime number if I say 13 30 is a prime number because 1 and 13 divides it there's a five five is a prime number because 1 and 5 divides it if I say 4 4 is not a prime number why because it is divisible by 1 it is divisible by 2 it is also divisible by 4 so there are three factors so 4 is not a prime number we take eight it is not a prime number why divisible by 1 2 4 8 so not a prime number something like 17 is a prime number because divisible by 1 and 17. so what is the first The Brute Force what is the definition of Brute Force the algorithm which is the first algorithm or the initial algorithm that comes to your mind okay so can I see the simplest way to check is I will do one thing I'll keep a counter equal to 0 and I know it exactly has two factors so run a loop from one and I'll go until n and I'll say I plus plus and I'll say Hey listen if it is a factor it will be completely divisible by uh I hence it will leave a remainder 0 and I'll do a counter plus plus and can I say at the end of the day if the counter turns out to be 2 then I'll say it's a prime number or else it's not a prime number so can I say this is the extreme Brute Force approach and if I write the extreme Brute Force approach what will be the time complexity of the extreme Brute Force approach can I say I'm running a loop n and these are unit operations so I can ignore so can I say the time complexity will be we go of n because I'm running a l Loop to check for every I which can be a factor and then I'm checking it and there is and after that there are conditional checks which are unit operations can be avoided so this is B go of n and we know that practice are involved in the previous problem we did learn that all the factors can be found in square root of n why because if you remember 36 36 out of factor 1 in the corresponding Factor like the corresponding other Factor was 36 2's 18 3 is 12 4 9 and 6 6 even if you checked till square root of n you could actually count all the factors and all the factors were 1 2 3 4 6 9 12 18 36 you can count all the factors even if you Loop till square root of n so why are you looping till we go of n kindly Loop till square root of n so what you'll do is I equal to 1 I into I lesser than n I've already taught you this and counter equal to 0 and you'll say if n modulo i is equal to equal to 0 that is definitely a factor at the same time the other Factor has to be different and the other factor is different then it will also be counted and then you can have a seam check if counter is equal to 2 Prime else not a prime number as simple as that and if I talk about the time complexity this Loop ends up running for B go of square root of n so if someone is coming up and asking you how do you check for a prime number you say I know the square root method because I know the observation so every factor that is the other corresponding number with which it has to get multiplied in order to get the number thereby I can just go up to square root of n nothing Beyond it because still square root of n I'll get all the factors so this is uh the code that I did right in the iPad so I'll quickly go ahead and submit this and see if it is working fine it is indeed working fine so we have completed the check pop Prime so apparently you have completed everything and the gcd or the hcf is left so let's go across and learn the gcd or hcf and then come back and take it over so what do you mean by gcd or hcf it's very simple greatest common divisor or highest common factor let me give you an example if I give you two numbers n one equal to 9 and N2 equal to 12. so you need to find the highest common factor or greatest common divisor that actually divides n and uh that divides 9 and 12. so if I write down all the factors of 9 it is 1 3 and 9. write down all the factors of 12 it is 1 2 uh six and twelve even three four these are all the factors of 12. so if I ask you the common factors the common factors if I go ahead and Mark it is 1 1 it is three three so there are two common factors out of these two common factors which is the highest one three so I can say the gcd of 9 comma 12 is 3 because 3 is the largest number that divides 9 and 12 both if I ask you the gcd of 11 and 13 what will be it will be 1 because if you try to write down all the factors of 11 it's going to be 1 and 11 all the factors of 13 1 and 13. so the common one is just one and that is the gcd so there will always be a gcd because one is a number that divides every other number so for every given two numbers there will always be a gcd or HCA if I ask you what is the gcd of 20 comma 30. rather 20 comma 40. with the gcp of 20 comma because for 2020 is a factor and for 40 20 is also a factor so that's why 20. so for two given numbers one of them can also be a gcd of those two given numbers so that is what is the definition of GC so all of you know so you know how to find factors of two given numbers a given N1 and a given N2 so the last two problems you have learned how to find factors so imagine it's like N1 is 9. and N2 is 12. so can I see if I looped from 1 to 12 and for every number I'll check if they're dividing both does one divide both yes one as of now is the largest factor plus 2 divide both no does 3 divide both yes so 3 is the largest if I can check every number And if every number divides both of them like if a number divides both of them I just replace that with my gcd's answer the largest number that I get that divides both of them will be my gcd if I try to write it can I write this as I equal to 1 maybe I will Loop till n 1 Maybe I plus plus and I'll say if N1 modulo I equal to equal to 0 and then N2 modulo I equal to equal to 0 or else it as of now I know one thing for sure any given two numbers any given two numbers will always have a gcd of 1. so gcd will be replaced by I can I see this because I is starting from 1 so it goes from 1 then it goes to 2 Then goes to 3 so whichever number divides both of them it just keeps on getting replace the last number which will be stored in gcd will definitely be the largest because I is moving in the increasing fashion very simple now you might ask me but striver what if n was given as 12 and N2 was given as 9 then the for Loop would have been running for 12 times but I know one thing for sure that if I is 10 the 10 will not divide 9 there is no point in checking so can I say instead of running till N1 I can actually run it for something like minimum of N1 Command 2 because I know if I run till minimum of N1 comma N2 like 9 parental line that will suffice running 10 11 doesn't make sense for example if the number was 20 and 40 if I run till 20 that will work because 20 is the largest factor I can have running it for 21 22 will not make sense so can I say I can run the loop till minimum of N1 comment I can thereby can I say the time complexity will be go of minimum of N1 command whichever is minimum till that I'll run the loop so thereby the time complexity is minimum of N1 command now you might have questions in your head but striver we are we're trying to find highest and over here what are you doing you're going from one two three four and checking everyone but what if N1 is 20 n 2 is 40 and I do the other way yes I do the other way and I see I'll run it from minimum of N1 comma N2 I greater than equal to 1 I minus minus and I'll see if N1 modulo I equal to equal to 0 and and N2 modulo I equal to equal to 0 I will print that as my gcd and I'll break and I'll break and you know what is the task of break it always breaks out from the Outer Loop not this is a conditional statement this is not a loop for this break which is the loop that is outside this break this one it will break out from this how does it cook the minimum of 2040 is 20 so 20 20 modulo 20 equal to equal to 0 yes 40 modulo 20 equal to equal to 0 yes print gcd as 20 yes break so the program terminates in this way you will say in this way it will have a better complexity because the moment you are getting someone from behind it breaks out you might give me this yeah definitely this might turn out to be a better one for a lot of cases but still the worst case will be minimum of N1 comma N2 imagine I give you two numbers n 1 equal to 11 N2 equal to 13. in this case what will happen for 11 and 13 the highest common factor is one it will start from 11 10 9 I will not find any one till one so we'll eventually loop from 11 to 1 so no matter what you do the time complexity will be still this because if both the numbers of gcd has one it ends up running completely look ends up running completely and you know when you determine the time complexity not either time complexity lecture you always take worst case you always take worst case the worst case is when you run it till one so we saw the previous method was a brute force method and was taking linear time complexity now there is an algorithm known as equiloid in algorithm which is going to take much much lesser time so let's learn about it so what is equilateral algorithm it states if you're given two numbers N1 comma N2 the gcd of N1 comma N2 whatever is the gcd of N1 comma N2 that's equivalent to the gcd of N1 minus N2 comma N2 where where N1 is greater than N2 usually in books you will find them written as gcd of a comma B is equal to gcd of a minus B comma B where a is greater than b this is what the equilibrium algorithm States if you want a mathematical proof of it you can definitely uh Google such as a huge mathematical proof to it again we will not go deep into the mathematical proof because it is not required in programming world you just need this concept so just have the concept now if I try to prove this with induction it's very simple uh if I give it two numbers imagine 15 and 20. so it basically see it's the greater number and the smaller number what is the gcd of 20 comma we know the gcd of 20 comma 15 is 5 so it states the gcd of 20 comma 15 the greater number 20 and the smaller number 15 is equal to it states greater minus smaller 20 minus 50. 5 comma the smaller number 15. so what is the gcd of 5 com that is also 5 so again by induction also you can prove it you can take any two numbers and you'll be able to prove that they are seen so I can see that the gcd of 20 comma 15 is equivalent to the gcd of 5. now you apply the equality on the first two numbers and whatever you get that will always be a truncated number you saw 20 getting truncated to five again you will apply equilibrium to this if you try to apply equality into 5 comma 15 it has to be the greater number at first so apparently you have to apply equality into 15 comma 5 because 50 is a greater number right so what do you do is you say okay let's Supply equality to 15 comma 5. it'll be like gcd of 15 minus 5 10 comma 5. again you can apply equiloid into 10 comma if you apply a cloud into ten comma 5 it'll be great as 10 10 minus 5 is 5 5.5 again if you apply equality into 5.5 it'll be both of them are same any one can be at the front 0 comma five so one apparently becomes zero the moment one of the numbers becomes zero the other number is actually your gcd is actually a gcd so the gcd of 20 or 15 is this what you do is you take two numbers apply equality get it smaller apply clear idea get it smaller get it smaller get it smaller till one of them is zero if one of them is zero the other is really so the algorithm is quite simple start with a comma B keep on truncating keep on truncating with a minus B comma B and keep on doing till one of them block the greater number becomes zero as simple as but here's a catch this might end up taking a lot more time imagine I give you a number like uh a equal to 52 and b equal to 10. so it'll be like what will you do you will say gcd of 52 comma 10 truncated to uh to gcd 42 comma 10 truncated to gcd 32 comma 10 truncated to gcd 22 committed truncated to gcd 12 comma 10 truncated to gcd 2 comma 10 and then you again take the bigger number at first 10 comma 2 and then you'll be again like truncated to 8 comma 2 truncated to 6 comma 2 4 comma two two comma 2 and 0 comma two and ultimately 2 is left because everything comes up so it's a lot of steps it's a lot of steps it might not improve the linear complexity by so much there's a catch over here if it is 52 and it was 10 and you're reducing it with 10 every time and you ended up at a place of two commanded isn't it equivalent to saying you're dividing it right and you're like 52 if you divide it by 10 it's like 5. you did it five times one two three four five and you ended up having the remainder because you are minus 10 minus 10 minus 10 minus 10 till it is possible it's equivalent to saying you subtract it till it was possible until it is data can I see instead of subtracting it five times you could have directly gone from here to Here by saying 52 modulo 10 comma 10. let's see two comma till that is same instead of subtracting ten five times directly get two command even from 10 comma 2 to 0 comma 2 you could have directly gone by saying 10 modulo 2 because that is what you did indirectly simple maths so can I see the algorithm in a better sense will be gcd of a comma B but definitely a is greater than b is equal to a modulo b comma B that's a bit and you go on doing till it becomes zero as simple as that you always take the greater number so the logic is very simple forget about A and B the logic is very simple the greater module or smaller that's the logic and they go on till one of them is zero and if one of them is zero remember this if one of them is zero the other is gcd the other is GC as simple as if I try to code this up try to code this up a given B can I say you go on till both of them are greater greater than zero basin and I know one of them will be greater either a will be great in that case I'll do a modulo b or else if B is greater I'll do B module a instead of swapping changing because I did not want to get into swapping changing why over here it was 2 comma 10 so a was this B was then you swapped it to this I did not want to implement that I just I knew now 10 will be modulated so what I did was I implemented it in such a way stating if a is greater a will be modeled if B is greater P will be modulated and once this is over if a is 0 if a becomes 0 then the while loop is false can I say the gcd will be B I will or else can I say the gcd will be print of a simple as yes so you can you can just take this example 52 comma 10 and you can do a dry run on this and you will see that eventually one of them will become 0 and that is when the looping ends and the time complexity of this equilateral algorithm is we go of log of Phi minimum of a comma B y log if you remember I clearly stated during the digit extraction or in the pattern videos or the time complexity videos that whenever there is division happening Whenever there is division happening the number of iterations will be in terms of logarithm over here there is modulo you are reducing the number by division the modulation operations are happening thereby the time complexity will be in terms of logger now Wi-Fi why not something like log base 10 in the digit extraction it is always invited over here this A and B it's always changing fluctuating you're not sure what will be a and b depending on different examples it will fluctuate that is why the given them given it a term Phi if you want to know what is Phi in depth there's a huge mathematical proof to it not required you can read it but it's not required and minimum of a comma B because that is the initial number where you start from that's the initial number we start to do it so that's why the time complexity is this no one is going to ask you how and everything just keep it in mind that the time complexity is Log 5 minimum of a comma B this is the equilateral so written the same code uh after if I'm not given else because this line doesn't if this line executes the function would have end and this line will not execute that's why so now I'll go ahead and run this code and it is running absolutely fine and if I'll submit this we get the correct answer so with this we'll be wrapping up the basic maths next is basic recursion I've already made videos on it I'll be attaching them to the playlist so watch this maths video post that go and watch the basic recursion video once you have done this then we will be going across to the next topic that is basic hashing and I'll be explaining hashing in depth but I hope for this video you've understood basic maths uh completely just in case you have please hit that like button and to follow a ritual do comment understood so that I get an idea that you guys are understanding and you have watched the video till here if you're new to our Channel what are you doing please please do consider subscribing to us because that is the only thing that keeps you motivated to make these kind of content and yeah with this I'll be wrapping up this video let's put in some other videos [Music]

Channel: take U forward

Views: 304,302

Keywords: data structures, dsa in cpp, c++ in one video, c++ full course, c++ tutorial for beginners, beginners, dsa for beginners, dsa in java full course, dsa in cpp full course, dsa full playlist, dsa full course in hindi playlist, google, dsa for amazon, dsa for google, striver, dsa full course, basic maths programming, palindrome number, prime number, prime number in c, prime number in c++, print all factors of a number java, euclidean algorithm to find gcd, number theory

Id: 1xNbjMdbjug

Length: 63min 20sec (3800 seconds)

Published: Sun Jan 08 2023