A sequence of numbers is said to be in an Arithmetic progression if the difference between any two consecutive terms is always the same. 2, 4, 6, 8, 10 is an AP series because they have a common difference (4-2=6-4=8-6=10-8)

• Initial Term (a): first number in the series
• Common difference (d): The value by which consecutive terms increase or decrease
• The behavior of the AP depends on the common difference d. If d > 0, then the members (terms) will grow towards positive infinity. If d < 0, then the members (terms) will grow towards negative infinity.
• nth term of AP : a + (n-1)*d
• Arithmetic Mean : Sum of all terms in the AP / Number of terms in the AP. AM of 2 terms: (a+b) / 2
• sum of 'n' terms : 0.5 n (first term + last term) = 0.5 n [ 2a + (n-1) d ].

A sequence of numbers is said to be in a Geometric progression if the ratio of any two consecutive terms is always same. 2, 4, 8, 16 is a GP because they have common ratio. (4 / 2 = 8 / 4 = 16 / 8 = 2).

• Initial Term (a): first number in the series
• Common ratio (r): The ratio between a term in the sequence and the term before it
• The behaviour of a geometric sequence depends on the value of the common ratio.
  • r > 0 -> the terms will all be the same sign as the initial term.
  • r < 0 -> the terms will alternate between positive and negative.
  • r > 1 -> exponential growth towards positive or negative infinity (depending on the sign of the initial term).
  • r = 1 -> progression is a constant sequence
  • -1<=r<=1, (but not zero) -> exponential decay towards zero.
  • r = -1 -> progression is an alternating sequence.
  • r < -1 -> for the absolute values there is exponential growth towards (unsigned) infinity, due to the alternating sign.
• nth term of GP : a*r ^ (n-1).
• Geometric Mean (GM) : nth root of product of n terms in the GP. GM of 2 terms : sqrt(a*b)
• Sum of ‘n’ terms of a GP (r < 1) : [a (1 – r^n)] / [1 – r].
• Sum of ‘n’ terms of a GP (r > 1) : [a ((r^n) – 1)] / [r – 1].
• Sum of infinite terms of a GP (r < 1): (a) / (1 – r).

A harmonic progression is a sequence of real numbers formed by taking the reciprocals of an arithmetic progression. If a,b,c,d are in an arithmetic progression, so its reciprocals 1/a, 1/b, 1/c, 1/d are in harmonic progression.

• Harmonic Mean(HM) of 2 terms: 2ab/(a+b)
• If A,G,H are AM, GM, HM where A>=G>=H : AH= G^2 . A,G,H are ain GP.

Average of given set of data. Mean = Total sum / n. Its a very popular measure of central tendency, which can be used with both discrete and continous data, most often with continous data.

Middle value of set of data . To get median value, numbers must be in sorted order.

• N is odd : Median = middle number from sorted data :(N+1) / 2th value
• N is even : Median = average of two middle values. : Average of (N/2)th and {(N/2) + 1}th value.
• If the user adds or multiplies a constant to every value, then mean and median will also be added or multiplied by the same constant.

ax^2 + bx + c = 0 Where a,b and c are real known values and, a can't be zero.

Roots are values for which the equation satisfies the given condition. the roots of equation x^2 - 7x - 12 = 0 are 3 and 4 respectively. If we replace the value of x by 3 and 4 individually in the equation, the equation will evaluate to zero.

We can have 2 roots for a QE:

r1,r2 = (-b ± √(b^2 - 4ac))/2a

• Determinant (D) : (b^2 - 4ac)

There are 3 different cases while finding the roots:

• D < 0 0r b^2 < 4ac : roots are imaginary (not real)
  • for equation, x^2 + x + 1 : r1 = -0.5 + i1.73205, r2 = -0.5 - i1.73205
• D = 0 or b^2 = 4ac : roots are real and equal (r1= r2)
  • for eqn, x^2 - 2x + 1 : r1 = 1 and r2 = 1
• D > 0 or b^2 > 4ac : roots are real and different
  • for eqn, x^2 - 7x - 12 : r1 =3 and r2 = 4

Permutation: Permutation is defined as arrangement of 'r' things that can be done out of total 'n' things

Denoted by nPr = n!/(n-r)!

Combination: Combination is defined as Selection of 'r' things that can be done out of total 'n' things

Denoted by nCr = n!/r!(n-r)!

Numbers > 0 which are divisible by 1 and itself. Example: 2,3,5,7,11..

• Every prime number can be represented in form of (6n+1) and (6n-1) except 2 and 3, when n > 0.
  • 5 : (6 * 1 ) -1, 29: (6 * 5) - 1
• 2 and 3 are only two consecutive natural numbers, which are prime too.
• 1 is neither prime nor composite.

check if a number is prime or not

Naive approach:

• If, N < 2. It is not prime, return False.
• Else: Iterate from 2 to N-1 and check if any of the numbers between 2 and N-1 (both inclusive) divides N or not. If yes, then N is not prime, return False. Otherwise, return True.

bool isPrime(n){
    if(n<2) return false;
    for(i = 2 i<= n; i++){
        if(n%i==0) return false;
        return true;
    }
} //TC : O(n-2) SC: O(1)

A better approach:

• Divisors always appear in pairs.
  • 30: (1,30),(2,15), (3,10),(5,6)
  • if x,y is a pair then (x * y) = n
    • if x < =y , x^2 = n, x = sqrt(n).
• we dont need to traverse numbers from 1 to n, just traverse from 2 to sqrt(n)

bool isPrime(n){
    if(n<2) return false;
    for(i = 2 i * i<= n; i++){
        if(n%i==0) return false;
        return true;
    }
} //TC : O(sqrt(n)) SC: O(1)

Max efficient method (for large values of 'n') :

We can save many iterations for large 'n' by checking if n % 2==0 and n%3 ==0. If we check for these two we dont need to check for multiples of 2 and 3.

bool isPrime(n){
    if(n<2) return false;
    if(n==2 || n==3) return true;
    //optimisation: skip multiples of 2 and 3
    if(n%2==0 || n%3==0) return false;
    // here i (will be) i = 5,7,11,17,23,29...
    for(i = 5; i * i<= n; i += 6){
        if(n%i==0 || n%(i+2) ==0) return false;
    return true;
    }
}

print all prime factors of n.

Input: n =12
Output: 2,2,3.

Input: n =13
Output: 13.

Input: n = 315
Out: 3,3,5,7

Naive approach:

void primefactors(int n){
    for(i = 2; i <=n ;i++){
        if(isPrime(i)){ //TC: O(sqrt(n))
            int x = i;
            while(n%x==0){
                cout << i << endl;
                x = x*i;
            }
        }
    }
} //total TC ::O(n^2 logn)

Efficient solution:

• Divisors always appear in pairs. (If we traverse from 2 to sqrt(n) we get a prime divisor)
  • let (x,y) be a pair. x * y = n.
    • if x<=y, x *x <=n, x <= sqrt(n)
• A number 'n' can be written as multiplication of power of prime factors
  • 12 = 2^2 * 3
  • 450 = 2 * 3^2 * 5^2

void primefactors(int n)
{
    if (n <= 1)
        return;
    for (i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            printf(i);
            n = n / i;
        }
    }
    if (n > 1)
        printf(n) //cornercase : if our last(largest prime factor is of power 1 -> specify it explicitly )
}

Further optimisation:

• Take out multiples of 2 & 3 out. If num is divisible by 2 then dont check with multiples of 2. same with 3.

const primefactors = (n) => {
  if (n <= 1) return;
  while (n % 2 == 0) {
    console.log(2);
    n = Math.floor(n / 2);
  }
  while (n % 3 == 0) {
    console.log(3);
    n = Math.floor(n / 3);
  }
  for (let i = 5; i * i <= n; i += 6) {
    while (n % i == 0) {
      console.log(i);
      n = Math.floor(n / i);
    }
    while (n % (i + 2) == 0) {
      console.log(i);
      n = Math.floor(n / (i + 2));
    }
  }
  if (n > 3) console.log(n); //cornercase : if our last(largest prime factor is of power 1 -> specify it explicitly )
}; // TC: O(sqrt(n))

Print all divisors of number 'n' in increaasing order. Eg: n= 5 -> 1,3,5,15. n = 100 -> 1,2,4,5,10,20,25,50,100

Naive approach:

function divisors(n) {
  for (let i = 0; i < n; i++) {
    if (n % i == 0) console.log(i);
  }
} //TC: O(n), SC: O(1)

Efficient solution:

• Divisors always appear in pairs.
• One of the divisors in every pair is smaller than or equal to sqrt(n)
  • if x,y is a pair then (x * y) = n
    • if x < =y , x^2 = n, x = sqrt(n).
• If we traverse from 1 to sqrt(n) we will find atleast one divisor of sqrt(n).

This approach doesn't print output in sorted order..

const divisors = (n) => {
  let i;
  for (i = 1; i * i < n; i++) {
    if (n % i == 0) console.log(i);
    // for perfect squares case
    if (i != Math.floor(n / i)) console.log(n / i);
  }
}; // TC: O(sqrt(n))

To get output in sorted order..

const divisors = (n) => {
  let i;
  for (i = 1; i * i < n; i++) {
    if (n % i == 0) console.log(i);
  }
  for (; i >= 1; i--) {
    if (n % i == 0) console.log(n / i);
  }
}; // TC: O(sqrt(n) + sqrt(n)) => O(sqrt(n))

• Outer for loop traverses from 1(inclusive) to sqrt(n)(exclusive).
• Inner for loop runs from sqrt(n) (inclusive) to sqrt(n) (exclusive)

Print all primes < n. Eg :n = 10 => 2,3,5,7. n = 23 => 2,3,5,711,13,17,19,23

This is the most efficient way of generating prime numbers upto a given number N.

Algorithm:

• Create a boolean array of size n+ 1 wih all values filled with true.
• Leave the first two cells 0 & 1 as (0 & 1 are not primes)
• Mark multiples of prime numbers to be false in the array.
• Print out remaining true values

const sieve = (n) => {
  if (n <= 1) return;
  let isPrime = new Array(n + 1);
  isPrime.fill(true);
  // if i is true, mark all of its multiples as false
  for (let i = 2; i * i <= n; i++) {
    if (isPrime[i]) {
      for (let j = 2 * i; j <= n; j = j + i) {
        isPrime[j] = false;
      }
    }
  }
  //print all primes from the array
  for (let i = 2; i <= n; i++) {
    if (isPrime[i]) console.log(i);
  }
}; //TC: O(nloglogn)

A small optimisation..

const sieve = (n) => {
  if (n <= 1) return;
  let isPrime = new Array(n + 1);
  isPrime.fill(true);
  // if i is true, mark all of its multiples as false
  for (let i = 2; i * i <= n; i++) {
    if (isPrime[i]) {
      for (let j = i * i; j <= n; j = j + i) {
        isPrime[j] = false;
      }
    }
  }
  //print all primes from the array
  for (let i = 2; i <= n; i++) {
    if (isPrime[i]) console.log(i);
  }
}; //TC: O(nloglogn)

• All numbers that divide a number completely, i.e., without leaving any remainder, are called factors of that number.
• For example, 24 is completely divisible by 1, 2, 3, 4, 6, 8, 12, 24. Each of these numbers is called a factor of 24 and 24 is called a multiple of each of these numbers.

• The largest number that divides two or more numbers is the highest common factor (HCF) for those numbers.

• For example, consider the numbers 30 (2 x 3 x 5), 36 (2 x 2 x 3 x 3), 42 (2 x 3 x 7), 45 (3 x 3 x 5). 3 is the largest number that divides each of these numbers, and hence, is the HCF for these numbers.

• To find the HCF of two or more numbers, express each number as their prime factorization. The product of the minimum powers of common prime terms in both of the prime factorization gives the HCF. This is the method we illustrated in the above step.

• Also, for finding the HCF of two numbers, we can also proceed by long division method. We divide the larger number by the smaller number (divisor). Now, we divide the divisor by the remainder obtained in the previous stage. We repeat the same procedure until we get zero as the remainder. At that stage, the last divisor would be the required HCF.

GCD Application : Tiling a rectangle with squares

Naive approach:

const GCD = (a, b) => {
  //WKT., Max GCD can be min of two given numbers, so begin with min of a & b.
  let res = Math.min(a, b);
  while (res > 0) {
    if (a % res == 0 && b % res == 0) break;
    res--;
  }
  return res;
}; //TC : O(min(a,b))

The Euclidean algorithm is based on the below facts:

• GCD doesn't change, if we subtract the smaller number from larger (we reduce larger number). So if we keep subtracting repeatedly the larger of two, we end up with GCD.

• If b is smaller than a. gcd(a,b) = gcd(a-b)

  • Let g be the gcd of a,b . where a = gx, b = gy & gcd(x,y) = 1
  • (a-b) = gcd(x-y) We need to show that b and (a-b) also have gcd = 1

Approach 2 (Euclidian algorithm):

const GCD = (a, b) => {
  //stop when a & b are equal and return either of them
  while (a != b) {
    if (a > b) a = a - b;
    else b = b - a;
  }
  return a; // or return b;
};

• Now instead of doing subtraction, if we divide the smaller number, the algorithm stops when the remainder is found to be 0

Optimized euclidian algorithm:

const GCD = (a, b) => {
  if (b == 0) return a;
  else return GCD(b, a % b); //TC :O(log(min(a,b)))
};

• LCM is a smallest number other than 0 & 1 that is a multiple of each number.

• LCM of 4 & 6

  • Multiples of 4: 4,8,12,16,20,24,28,32...
  • Multiples of 6: 6,12,18,24,30,36,...
  • common multiples: 12,24,36,48 => Least common multiple = 12

• The lowest number which is exactly divisible by each of the given numbers is called the least common multiple of those numbers. For example, consider the numbers 3, 31 and 62 (2 x 31). The LCM of these numbers would be 2 x 3 x 31 = 186.

• To find LCM of given numbers: express each number as their prime factorization. The product of highest power of the prime numbers that appear in the prime factorization of any of the numbers gives us the LCM.

• consider the numbers 2, 3, 4 (2 x 2), 5, 6 (2 x 3). The LCM of these numbers is 2 x 2 x 3 x 5 = 60. The highest power of 2 comes from prime factorization of 4, the highest power of 3 comes from prime factorization of 3 and prime factorization of 6 and the highest power of 5 comes from prime factorization of 5.

Naive approach:

const lcm = (a, b) => {
  //LCM would >= larger of 2 numbers
  let res = Math.max(a, b);
  while (res) {
    if (res % a == 0 && res % b == 0) return res;
    res++;
  }
  return res;
}; // TC: O(ab-max(a,b))

Efficient soln:

a* b = gcd(a,b) * lcm(a,b)

• lcm(a,b) = (a*b) / gcd(a*b)

const lcm = (a, b) => {
  return (a * b) / GCD(a, b);
}; //TC: O(log(min(a,b)))

• For two numbers say, 'a' and 'b', LCM x HCF = a x b.
• HCF of co-primes = 1.
• For two fractions,
  • HCF = HCF (Numerators) / LCM (Denominators)
  • LCM = LCM (Numerators) / HCF (Denominators)

• Factorial of a positive integer n, denoted by n! is the product of all positive integers <= n

Find factorial of a given number, where n>=0

Ip: n = 4
Op: 24,
Ip: n= 6
Op:720
Ip: n=0
Op: 1

Iterative solution:

int fact(int n){
    int res = 1;
    for(int i = 2; i<=n;i++){
        res=res*i;
    }
    return res;
} //TC: O(n), SC: O(1)

Recursive solution:

int fact(int n){
    if(n==0 || n==1) return 1;
    return n * fact(n-1);
} // TC: O(n), SC:O(n)

Find trailing zeroes in a factorial.

Input: n = 5
Output: 1
Factorial of 5 is 120 which has one trailing 0.

Input: n = 20
Output: 4
Factorial of 20 is 2432902008176640000 which has
4 trailing zeroes.

Input: n = 100
Output: 24

Naive solution:

const fact = (n) => {
  if (n === 0 || n === 1) return 1;
  let fact = 1;
  for (let i = 2; i <= n; i++) {
    fact *= i;
  }
  return fact;
};
const trailingZeroes = (n) => {
  let res = fact(n);
  let count = 0;
  while (res % 10 === 0) {
    count++;
    res /= 10;
  }
  return count;
};
console.log(trailingZeroes(5)); // 2
//TC: O(n);

Major issue with the above solution is it causes overflow even if the n is slightly higher.

Efficient solution:

Count number of 2s and 5s in the prime factorization of given factorial.

• One interesting fact about factorials is number of 5s are < number of 2s. So we simply need to find number of 5s in the given number.
• 1x2x3x4x5x6x7x8x9x10....n -> Notice that every 5th number is going to have 5 as a prime factor. If we have a n as a number, then we have atleast floor(n/5) prime factors.
  • Why atleast? consider the case of 25. We have two 5s as prime factors. We have to consider these as well.

  • General formula: Trailing zero count = floor(n/5) + floor(n/25) + floor(n/125) + ......

const efficientTrailZeroes = (n) => {
  let res = 0;
  //first ompute n/5, then compute n/25, then compute n /125 ...
  for (let i = 5; i <= n; i *= 5) {
    res += n / i;
  }
  return Math.floor(res);
};
console.log(efficientTrailZeroes(251));
// 5^k <=n , k <= log5(n); TC: O(log5(n))

This solution solves the major issue of overflow because we are not calculating factorial here , we are dividing the given number based on number of 5s

Given an integral number N. The task is to find the count of digits present in this number. Lets say n = 2020, number of digits in 2020 = 4 and digits are 2,0,2,0

A simple solution is..

• Check if number n != 0
• increment count of digits by 1 if n !=0
• reduce number by dividing it with 10
• repeat above steps, until n is reduced to 0

//iterative
int countDigits(long n){
    int count = 0;
    while(n > 0){
        n = n/10;
        ++count;
    }
    return count;
} // TC: O(digitsCount), SC: O(1)

//recursive
int countDigits(long n){
    if(n==0) return 1;
    return 1+ countDigits(n/10);
} // TC: O(digitsCount), SC: O(digitsCount)

Another approach :

Convert number to string and find string length

    public static int countDigits(long n) {
        String num = Long.toString(n);
        return num.length();
    }//TC: O(1), SC:O(1)

A better solution..

Use Logarithmic approach to solve this problem. This can be easily obtained by using a formula

number of digits in N = log10(N) + 1. log(123) = 2.08 => 2.08+1 = 3.08 floor(3.08) is 3.

    public static long countDigits(long n) {
        if (n == 0)
            return 0;
        return (int) Math.floor(Math.log10(n) + 1);
    } //TC: O(1), SC:O(1)

check whether a given number is palindrome or not. Eg: n = 106601 -> true, n = 84348 -> true, n = 8 -> true. n= 21 -> false, n = 1789 -> false.

bool isPalindrome(int n){
    int rev = 0;
    int temp = n;
    while(temp!=0){
        int lastDigit = temp%10;
        rev = rev * 10 + lastDigit;
        temp/=10;
    }
    return(rev==n);
} // TC: O(n)

• Absolute Value
• Convert celsius to farenhiet