Formula

Sum of 1st N Numbers :

( n * (n + 1) )/ 2

Count trailing zeroes in factorial of a number:

Divide the number by 5 until the number is > 0. Add all the quotient .

Modulo Property

(a+b+c) % x = (a%x + b%x + c%x) % x

(ab) mod p = ( (a mod p) (b mod p) ) mod p

Horner’s Method for Polynomial Evaluation

// Evaluate value of 2x3 - 6x2 + 2x - 1 for x = 3
Input: poly[] = {2, -6, 2, -1}, x = 3
Output: 5

// Evaluate value of 2x3 + 3x + 1 for x = 2
Input: poly[] = {2, 0, 3, 1}, x = 2
Output: 23

Horner’s method can be used to evaluate polynomial in O(n) time.Consider the example of 2x3 – 6x2 + 2x – 1. The polynomial can be evaluated as ((2x – 6)x + 2)x – 1.

int horner(int poly[], int n, int x) 
{ 
    int result = poly[0];  // Initialize result 
  
    // Evaluate value of polynomial using Horner's method 
    for (int i=1; i<n; i++) 
        result = result*x + poly[i]; 
  
    return result; 
} 

Linear Diophantine Equations

Given three integers a, b, c representing a linear equation of the form: ax + by = c. To Determine if the equation has a solution such that x and y are both integral values.

Algorithm to determine if an equation has integral solution:

• Find GCD of a and b

• Check if c % GCD(a ,b) ==0

• If yes then print Possible

• Else print Not Possible

Common Divisors of Two Numbers

A better solution is to calculate the greatest common divisor (gcd) of given two numbers, and then count divisors of that gcd.

// function to count the divisors 
int countDivisors(int n) 
{ 
    int cnt = 0; 
    for (int i = 1; i <= sqrt(n); i++) { 
        if (n % i == 0) { 
            // If divisors are equal, 
            // count only one 
            if (n / i == i) 
                cnt++; 
  
            else // Otherwise count both 
                cnt = cnt + 2; 
        } 
    } 
    return cnt; 
}

Check if a point lies inside circle

Distance between the points should be less than radius^2 (x - x1) * (x- x1) + (y-y1)*(y-y1) <= r*r