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 div...
Posts
Competitive Programming as the names suggest is kind of programming in any contest or competition. In other words, it is brain sport which usually takes place over the internet or local network means it’s kind of competition of programming. Suppose if I make a group of five people to do a particular task with some provided specifications and who will do the task first will get a reward then there would be the atmosphere of competition, everyone will try hard to solve the task than other so he or she could win the task. Competitive Programming is also, same as the situation explained above were in a competition or event programmers take part and solve the problem first then the other than in given time constraint. Math for Competitive Programming As today’s programmers or learners get to know from different resources what Competitive Programming is? It seems very fascinating to them that it would help them to solve problems quicker than other so they jump directly to C...
1. Sum of Odd numbers: 1+3+5+7+9+....+n =? where n is an odd number Solve: let, n = 3 list = 1+3+5 = 9 ; 3^2=9 or 3*3 = 9 let, n = 5 list = 1+3+5+7+9 = 25 ; 5^2 =25 or 5*5 =25 • so, summation of n odd numbers = n^2 = n*n 2.Sum of Even numbers: 2+4+6+8+10+....+n =? where n is an even number Solve: n=4, list = 2+4+6+8 = 20; sum = 4^2+4 = 20 or 4*5 =20 n=7, list = 2+4+6+8+10+12+14 = 56; sum = 7^2+7 = 56 or 7*8 = 56 • so, summation of n even numbers = n^2+n = n*(n+1)
Q. f ( n ) = - 1 + 2 - 3 + .. + ( - 1) n n . Given n, find out f(n) Approach(1)- Bruteforce: 1. Calculation sum=n*(n+1)/2 2. loop[i=1,i=n : i+=2] odd+=i 3.ans=sum-2*odd Code: #include < bits / stdc ++. h > using namespace std ; int main (){ long long x ; cin >> x ; long long p =( x *( x + 1 ))/ 2 ; long long bad = 0 ; for ( long long i = 1 ; i <= x ; i += 2 ) bad += i ; cout << p - 2 * bad << endl ; } Approach(2)-Greedy: Basic: s=1+2+3+4+....+n Formula: sum=n*(n+1)/2= (n/2) + (n+1).2 ...