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 DS algo course. Why do I say 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 455 modules. This is an extremely in-depth DS 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++ 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 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 might 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 in 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 concepts. So, before solving all the problems that are listed under basic maths, we'll be starting off with the basic maths concepts. 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 7789. 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 need 9, I need 8, I need 7, I need 7. I need all the digits individually. Okay, so what is this digit 9? Can I see this? If I do a modulo 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 modulo operator in programming? The modulo 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 7780. 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 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 way. You say, okay, this number, let's divide it by 10. So, if I divide 7789 by 10, can I say I'll get 778.9? Can I say this? If I divide the numbers 7789 by 10, I'll get 778.9, and if I take an integer round off, if I take an integer portion of it, the integer portion is 778. 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 778.9, 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 8, how do you extract it? Again, the same way. You see, can I divide a modulo-wise with 10? If I do a mod of 10, I'll actually get 8. Why? Because the nearest number will be 770, 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 778 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-wise? A modulo of 10, and I'll get 7. I will end up again extracting 7.

Now, if I need the next extraction, I again divide by 7. So, I divide by 10, and I'll get 7. Because 77 divided by 10 is 7.7, and the integer part is 7. So, I get 7. If I do a modulo-wise of 10, I'll actually again get 7. Why will you get again 7? Very obvious, because the nearest number that is divisible by 10 to 7 is 0, thereby you get a remainder of 7. So, you get 7. 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 of 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 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 9, 8, 7, 7, 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, the 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 become 0, right? And can I see the extraction is very simple? The first time N was 7789. If I had to do an extraction, it's very simple. Can I say the last digit is nothing but N modulo 10? If I do an N modulo 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 N as 7789. So, this says 7789 greater than 0, which is true. So, the last digit happens to be 7789 modulo 10, and the last digit is 9. If you want to print this last digit, you can definitely put a print operation. In C++, it is `cout`. In Java, it is `System.out.println`. So, you can go ahead and print the 9. Once you have done this, can I say if you do 7789 by 10, then the N will reduce itself. It will be the value of N now. Can I say the value of N will be nothing but 778? 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 0. 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 modulo 10. The last digit this time will be 8. 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, hence 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, input 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 say 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 backend. 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 count. 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 problem. 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 the digits are. Now, since I've removed the modulo 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 of 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 the count of digits. What you do is, very simple. You say, count is equal to log 10 the number plus 1, and you're saying, take the integer, or you can just auto-cast it, like typecast 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". `log10` was not declared. So, if you find such errors, what you can do is, you can go to `#include`. That's basically because in their backend, 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, 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 N, 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 N. 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 N. 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 N. 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 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 Big O of N. If the number of iterations is based on division, time complexity will be logarithmic. Remember this always.

So, you solved the first problem, "Count Digits". The next problem is "Reverse a Number". Let's go to the problem. It states, "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 10400 will be 401 instead of 00401." And these are some of the examples.

So, let's get back to our extraction of digits concept. 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 8, then we get 7, then we get 7. Somehow, we need 9877, which is in a 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 = 0`, and you say `reverse_number = reverse_number * 10 + last_digit`. Remember this. This is what you say: `reverse_number * 10 + 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, 7789 mod 10 will generate 9, and N would have as of now become something like 7789 by 10. So, N would have as of now become 778. And `reverse_number` says `reverse_number` is 0 into 10 plus the last digit 9. 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 0? And 778 modulo 10 as the last digit is 8. 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 9. 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. Quite simple.

Why did this work? It is very easy to understand. You are getting the 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 9. You somehow want to add 8 to that 9. And the easiest way is, if you can somehow add a 0 to this 9, 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 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 0. This is why at every step, I am doing `reverse_number * 10`. Whatever you have generated into 10, that will allow the last unit digit to be 0. Then, when you add a digit, it 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 `reverse_num = 0`. And then I'll go ahead and say `n > 0`, and I can say `last_digit = n % 10`. I can say `reverse_number = reverse_number * 10 + last_digit`. I guess `n = n / 10`. And the same time, I can say `cout << 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. On submitting, you see that it is running absolutely fine. Next problem is "GCD or HCF". But before that, we will be solving "Armstrong Numbers".

So, what is the definition of an Armstrong number? It's very simple. Imagine you're given this number 371. You take 3 cubed, 7 cubed, plus 1 cubed. 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 1634, 1 cubed plus 6 cubed plus 3 cubed plus 4 cubed, if you sum them up, you actually get 1634. But something like 35, if you take 3 cubed plus 5 cubed, 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 1634. So, you call 1634 as an Armstrong number, or 371 as an Armstrong number. So, I hope you've got the definition of an Armstrong number.

So, if you have got the definition of an Armstrong number, you know how to solve it. I've already taught you the extraction of digits. You know how to extract 9, you know how to extract 8, you know how to extract 7. 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 sum cubes, and the last digit is what I have to sum. Can I say `sum = sum + last_digit * last_digit * last_digit`? Can I do this? So, first time 9 comes in, what happens? 9 into 9 into 9 gets added to sum. Next time 8 comes in, 8 into 8 into 8 gets added to the sum. So, everything is getting added. First time, 9 into 9 into 9 got here. Next time, 8 went, 8 into 8 into 8. Next time, 7 came in, 7 into 7 into 7. Next time, again 7 came in, 7 into 7 into 7. So, can I say at the end of the day, `sum` will be storing the summation of digit cubes? And after that, you need to just compare it with the original N. So, maybe again, keep a duplicate variable which stores the N, because at the end of the day, you have to compare if this and the duplicate are same. If this is, you say it is an Armstrong. If this is not, it's not an Armstrong. 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 Divisors". 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, 1 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 36. 5, something which completely divides 36? No. If 36 is divided by 5, it leaves a remainder of 1. So, not 5. 6 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, divisors 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 divisors 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 it. And for sure. So, if I know all the divisors are going to be between 1 and N, can I just loop from 1 to N? That's my first thought process. Since I know the divisions are from 1 to N, my first thought process is very simple. So, let's do one. Let's start the loop from `i = 1`, `i <= n`, and `i++`. 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 2, then it's 3, then it's 4, then it's 5, 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 simple. Can I see if it is completely dividing? If `i` is completely dividing N, then it is a factor or a divisor. And what do you mean by completely dividing? It should leave a remainder of 0. When I say leaving a remainder of 0, does it mean if I do a modulo of `i`, if I do `n % i`, the value should be 0? Because it's completely divisible by what? I will do is, I'll say, okay, if `n % i == 0`, I will go ahead and print `i`. In C++, `cout`. In Java, `System.out.println`. I'll go ahead and print `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 a unit operation. So, let's not calculate it. Thereby, the time complexity of this particular approach is nothing but Big O of N. Very simple. Over here, they have given us everything. I want us to write this `print_divisors` function. Let's write the `print_divisors` function. It takes an N. And as I said, it's very simple. You go from 1, you go until N, and you say `i`. This one. And you know if `n % i == 0`, you say `cout << i` and then you give a 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 Big O of N time complexity. Can I do it in a much better way? I can, but it requires a bit of mathematical observation. Let's see that mathematical observation. So, for 36, I said that 1 was a factor. If 1 is a factor, 1 has to be multiplied with something in order to get 36. So, 1 was multiplied with 36. And if you carefully observe, if this is 1, 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 3, 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 6, it is 6 into 6. The next factor is actually 9, and then you multiply it with 4. The next factor is 12, and you multiply it with 3. And the next factor is 18, you multiply it with 2. And the next element is 36, you multiply it with 1. So, 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 1. So, can I see even if I consider everything before the orange line, I will get 1, I'll get 2, I'll get 3, I'll get 4, I'll get 6, 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, do I get all the factors? 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 into small. Can I see this is nothing but the square root of N? Because when you take the 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, 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 1, 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 least 6, this has to be N by 6. So, can I see now the looping is going to be very straightforward? I loop from `i = 1` till `i <= sqrt(N)`, and `i++`. And can I see if `n % i == 0`, it's 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 6. So, there are not two different factors. So, if you're taking the second factor, if you're taking the second factor, to N by `i`, just make sure that N by `i` is not equal to `i`. 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, print it. 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 factor. That's it. So, if you go ahead and print this, the printing will be something like this. First, 1 and 36 will get printed. Next, 2 and 18 will get printed. Next, 3 and 12 will get printed. Next, 4 and 9 will get printed. Next, when `i` is 6, 6 gets printed, but the other factor is 6. It builds this condition check, thereby the other 6 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 structure. And if you have seen the C++ 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++. We'll be using an undefined, like you cannot define the size of the data structure. I'll be using a list, okay? And in that list, you can store it, store it, store it. 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 fashion.

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 N. 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.push_back(i)`. Push back `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.begin(), ls.end())`? Once you have done this, just need to print it. You know how to print it. This is how you print the list. C++ STL video, guys. So, I'll just iterate on the list and I'll print the list with a 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 <= sqrt(N)`. Instead of this, because `sqrt` is a function, and every time the function will be called, because `sqrt` is a mathematical function in C++ STL, this will be called every time, which will take time itself. Instead of writing this, you can actually write `i * i <= N`. So, it'll be like, when `i` reaches 6, it will be like `6 * 6 <= 36`. It will work. The dominant goes to 7. `7 * 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 Big O of square root of N times? Can I say that? This loop is running for Big O of square root of N 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 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 Big O of square root of N plus Big O of number of factors into log of number of factors. So, number of factors into log of number of factors. What it? Quite simple. And then plus this. So, Big O of this plus Big O of this plus Big O of this is the time complexity. But the motive was to teach you that you can also find factors in Big O 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, 1 is a prime number, because 1 is divisible by 1 and 1 is divisible by itself, which is 1. 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 and 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 other number doesn't divide 11. So, 11 is a prime number. If I say 13, 13 is a prime number because 1 and 13 divides it. A 5, 5 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 8, 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 it's 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 1, and I'll go until N, and I'll say `i++`, and I'll say, "Hey, listen, if it is a factor, it will be completely divisible by `i`, hence it will leave a remainder 0", and I'll do `counter++`. 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 Big O of N? Because I'm running a loop to check for every `i` which can be a factor, and then I'm checking it. And there are conditional checks which are unit operations, can be avoided. So, this is Big O of N.

And we know that factors 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, and the corresponding factor like the corresponding other factor was 36. 2's 18, 3's 12, 4's 9, and 6's 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 Big O of N? Kindly loop till square root of N. So, what you'll do is, `i = 1`, `i * i <= n`, I've already taught you this. And `counter = 0`. And you'll say, if `n % i == 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 same check. If `counter == 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 Big O 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 till square root of N, I'll get all the factors. So, this is the code that I did right on 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 for 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, N1 = 9 and N2 = 12. So, you need to find the highest common factor or greatest common divisor that actually divides N and 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, 6, and 12. Even 3, 4. 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 3, 3. 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, 12 is 3, because 3 is the largest number that divides 9 and 12 both.

If I ask you, what is the GCD of 11 and 13? What will it 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 1, and that is the GCD. So, there will always be a GCD because 1 is a number that divides every other number. So, for every given two numbers, there will always be a GCD or HCF. If I ask you, what is the GCD of 20, 40? Rather, 20, 40. With the GCD of 20, 40? Because for 20, 20 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, does 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 N1. 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 replaced. 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, then 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, comma N2? Because I know if I run till minimum of N1, comma N2, like 9, 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, comma N2? I can thereby, can I say the time complexity will be O of minimum of N1, comma N2? Whichever is minimum, till that I'll run the loop. So thereby the time complexity is minimum of N1, comma N2.

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, N2 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 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 work? The minimum of 20, 40 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, N1 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 it will 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 Euclidean algorithm, which is going to take much, much lesser time. So let's learn about it. So what is Euclidean 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 Euclidean algorithm states. If you want a mathematical proof of it, you can definitely 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 sees 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 15, 5, comma the smaller number 15. So what is the GCD of 5, comma? 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 5. Again, you will apply Euclidean to this. If you try to apply Euclidean into 5, comma 15, it has to be the greater number at first. So apparently, you have to apply Euclidean into 15, comma 5, because 15 is the greater number, right? So what do you do? You say, okay, let's apply Euclidean to 15, comma 5. It'll be like GCD of 15 minus 5, 10, comma 5. Again, you can apply Euclidean into 10, comma. If you apply Euclidean into 10, comma 5, it'll be greater as 10. 10 minus 5 is 5, comma 5. Again, if you apply Euclidean into 5, comma 5, it'll be both of them are same. Any one can be at the front, 0, comma 5. 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 Euclidean, get it smaller, apply Euclidean, 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, 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, comma 10 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 2, 2, comma 2, and 0, comma 2. 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 2, comma 10. 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, 2, comma 10. Till that is same. Instead of subtracting 10 five times, directly get 2, comma 10. 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 math.

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 modulo 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 GCD. 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 greater. In that case, I'll do A modulo B. Or else, if B is greater, I'll do B modulo 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 modulated. If B is greater, B 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 Euclidean algorithm is O of log of Phi minimum of A, comma B. Why 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 log. Now, why Phi? 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 Phi minimum of A, comma B. This is the Euclidean. 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 ended, 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 math 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 math, 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]