Skip to content

Math Formulas and Tricks

Here we are going to discuss common math formula and tricks used in programming.

Greatest Common Divisor

GCD or Highest Common Factor(HCF) is the largest value number which can divide two given numbers. For example GCD of is as it is the largest number which can divide both and . To find a GCD of two numbers both of them must be non-zero.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class GCD {
    // recursive:
    public int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return (b, a % b);
    }

    // iterative:
    public int gcdIter(int a, int b) {
        while (a != b) {
            if (a > b) {
                a = a - b;
            } else {
                b = b - a;
            }
        }
        return a;
    }
}
  1. A. Playing with Paper

Lowest Common Multiple

LCM is the lowest value number (except 1) which can be divided by given two numbers. For example LCM of is . The formula of LCM requires the GCD value of two given numbers and then we can have LCM as follows:

1
2
3
4
5
public class LCM {
    public int lcm(int x, int y) {
        return (x * y) / gcd(x, y);
    }
}

Check for Prime

Prime numbers in Math are the numbers which can be divided by and the number themselves. For example etc. are all prime numbers. is not considered prime number. Negative numbers cannot be prime.

An interesting observation in natural numbers line is that prime numbers always repeat themselves at a factored length of and starting from number .

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class CheckPrime {
    public boolean isPrime(int x) {
        if (x == 1) {
            return false; // 1 is not considered prime
        }
        if (x == 2 || x == 3) {
            return true; // 2 and 3 are basic primes
        }
        if (x % 2 == 0 || x % 3 == 0) {
            return false;
        }
        for (int i = 5; i * i <= x; i += 6) {
            // two prime numbers always repeat together
            // on the natural line number at an interval
            // of factored length of 6 and 8 from the 
            // last prime number
            if (x % i == 0 || (x + 2) % i == 0) {
                return false;
            }
        }
        return true;
    }
}

Power of a number

The power, let's say of a number is the value which we get if get to multiple the number by itself number of times.

In programming we can use a neat trick called binary exponentiation to calculate a power of a number in time instead of time.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Power{
    /*
    Recursive Version
    */
    public long powRec(int x, int y) {
        if (y == 0) {
            return x;
        }
        if (y % 2 == 1) {
            // factor in extra 'x'
            return x * pow(x, y / 2) * pow(x, y / 2);
        }
        return pow(x, y / 2) * pow(x, y / 2);
    }

    /*
    Iterative version
    */
    public long powIter(int x, int y) {
        int ans = 1;
        while (y > 0) {
            if ((y & 1) == 1) {
                // factor in extra 'x'
                ans *= x;
            }
            x *= x;
            y = y >> 1;
        }
        return ans;
    }
}
  1. 50. Pow(x, n)

Permutation

A permutation is arrangement of objects in a specific order after being picked up from a set of elements. The permutation can be after picking less number of objects from the set of elements. For example, for a set of if we want permutation of two elements we will get permutation as .

There is specifc formula to calcuate the number of permutations which we can get after picking elements from a set of elements as:

where and are the factorial.

In above example we can calculate permutations as:

Combination

If we only have to count the combinations of different element without taking into account their arrangements then we calcuate the combination as follows: