Before learning MO’s Algorithm, let us take a quick look at the prerequisites through which we can solve it. In competitive programming , we come across questions which involves queries mostly static queries which are given as vectors or arrays . Each such queries represent a run in the code. So, do you think running the code each time for every query operation is fine? Obviously, it is a brute force approach and it will fail most of the times in a coding platform as there will be a huge number of queries. So, what we can do? Can we always break up the array in two parts for like we do in Binary Search ? Not really! And nor it will be beneficial. Let us consider a particular part of the array may be some x th part of the array size. We divide the array into x parts to reduce our time complexity. By using complex mathematical calculations – differentiation we found out that this x is nothing but, where n is the size of the array. We come to the conclusion that dividing the array
One of the earliest known numerical algorithms is that developed by Euclid (the father of geometry) in about 300 B.C. for computing the Greatest Common Divisor (GCD) of two positive integers. Euclid’s algorithm is an efficient method for calculating the GCD of two numbers, the largest number that divides both of them without any remainder. Algorithm: The first way of doing it if we try to subtract the smallest number from the greatest, GCD remain the same and in this way, if we keep repeating this step we’ll finally get GCD . But as above process subtraction could be time-consuming then instead of subtracting what we do, we divide the smaller number, the algorithm stops when we find remainder 0. Let GCD(x,y) be the GCD of positive integers x and y. If x = y, then obviously GCD(x,y) = GCD(x,x) = x Euclid’s insight was to observe that, if x > y, then GCD(x,y) = GCD(x-y,y). Actually, this is easy to prove. Suppose that d is a divisor of both x and y. Then there exist integers q 1 a