text: # DSA Part 2: Mathematics
  
  Posted on Dec 25, 2020
  
  ## Number System
  
  ### Types of number
  
  TypeValue
  Natural Numbers$N=1,2,3,4, \ldots$
  Prime Number$P=2,3,5,7,11,13,17, \ldots$
  Composite Number$4,6,8,9,10,12, \ldots$
  Whole Numbers$W=0,1,2,3,4, \ldots$
  Integers$Z= \ldots,−3,−2,−1,0,1,2,3, \ldots$
  Rational Numbers$Q= \frac{1}{2} ,0.33333 \ldots,52,1110, \ldots$
  Irrational Numbers$F= \ldots ,π, \sqrt{2} ,0.121221222 \ldots$
  Real Numbers$R= \ldots ,−3,−1,0, \frac{1}{5},1.1, \sqrt{2} ,2,3,π, \ldots$
  Complex Number$C= \ldots ,−3+2i,0,1+3i, \ldots$
  
  ### Types of number system
  
  Number system consists values from 0 to N-1
  
  Number SystemValue
  Binary0 and 1
  Octal0 to 7
  Decimal0 to 9
  HexaDecimal0 to 9 and A to F
  
  ## Number Series
  
  SeriesFormula
  Sum of first n numbers$\frac{n \cdot (n+1)}{2}$
  Squares of first n numbers$\frac{n \cdot (n+1) \cdot (2n+1)}{6}$
  Cube of first n numbers$(\frac{n \cdot (n+1)}{2})^2$
  Sum of first n even numbers$n \cdot (n+1)$
  Sum of first n odd numbers$n^2$
  
  ## Number Sequences
  
  ### Arithmetic progression
  
  $2, 4, 6, 8, \ldots$
  
  $\rightarrow a_{1} = a + 0.d$
  
  $\rightarrow a_{2} = a + 1.d$
  
  $\rightarrow a_{3} = a + 2.d$
  
  $\vdots$
  
  $\rightarrow T_{n} = a + (n-1) \cdot d$
  
  We know that
  
  $\rightarrow avg = \frac{sum}{n}$
  
  $\rightarrow sum = avg \times n$
  
  And in case of evenly distributed numbers
  
  $\rightarrow avg = \frac{first + last}{2}$
  
  $\rightarrow sum = \frac{(a + a + (n-1).d)n}{2}$
  
  $\rightarrow S_n = \frac{n(2a + (n-1)*d)}{2}$
  
  ### Geometric progression
  
  2, 4, 16, 32, 64 ……
  
  a, $a.r^{1}$, $a.r^{2}$, $a.r^{3}$, … $r^{n-1}$
  
  Nth term $\rightarrow$ $T_{n} = a*r^{n-1}$
  
  Sum till N terms $\rightarrow$ $S_{n} = a*(r^{n} - 1)/ r-1$
  
  Sum of infinite terms $\rightarrow$ $S_{\infty} = \frac{a}{1-r}$
  
  ### Harmonic Progression
  
  Harmonic progression (or harmonic sequence) is a progression formed by taking the reciprocals of an arithmetic progression. $\rightarrow \frac{1}{5}, \frac{1}{10}, \frac{1}{15}, \ldots$
  
  Nth term $\rightarrow$ $T_{n} = \frac{1}{a + (n-1) \cdot d}$
  
  ## Average
  
  ### Mean
  
  The central of middle value in a set of data. Commons ways to calculate average are mean, median, mode.
  
  Suppose
  
  $a_{1}, a_{2}, a_{3}, …. , a_{n}$
  
  Mean is the arithmetic average of a given data.
  
  $\rightarrow mean = \frac{a_{1} + a_{2} + a_{3} + …. + a_{n}}{n}$
  
  #### Types of Mean
  
  NumberTest
  Arithmetic Mean(AM)$\frac{a+b}{2}$
  Geometric Mean(GM)$\sqrt{ab}$
  Harmonic Mean(HM)$(2ab) \cdot (a+b)$
  
  $\rightarrow GM^2 = AM \times GM$
  
  ### Median
  
  Median is the middle value
  
  $\rightarrow median = A[\frac{n+1}{2}] if n is odd else \frac{A[\frac{n}{2}] + A[\frac{n+1}{2} + 1]}{2}$
  
  ### Mode
  
  Mode is the number with the maximum frequency
  
  $\rightarrow 3 Median = 2 Mean + Mode$
  
  $ax^{2} + by + c = 0$
  
  $x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}$.
  
  $D = b^{2} - 4ac$
  
  • D < 0 : Imaginary roots
  • D = 0 : Two equal roots
  • D > 0 : Two distinct roots
  
  ### Prime numbers
  
  2,3,5,7,11, ….
  
  All the numbers having exactly two factors.
  
  Can be represented as 6n+1 or 6n-1, except 2 and 3.
  
  2 and 3 are only consecutive prime numbers.
  
  ## Test Of Divisibility
  
  NumberTest
  2Last one digit is divisible by 2 (Unit digist is 0, 2, 4, 6, 8)
  3Sum is divisble by 3
  4Last two digit is divisible by 4
  5Unit digit is either 0 or 5
  6Divisible by both 2 and 3
  7Difference between twice the unit digit of the given number and the remaining part is divisible by 7
  8Last three digit is divisible by 8
  9Sum is divisble by 9
  10Unit digit is 0
  11Difference between sum of digits at odd places and even places is either 0 or is divisible by 11
  
  ## HCF and LCM
  
  There are three ways to find HCM and LCM
  
  1. Listing factors/multiple
  2. Prime fractorization
  3. Division method
  
  $\rightarrow a\times b = HCF(a,b) \times LCM(a,b)$
  
  HCF of co-primes is 1.
  
  For fractions
  
  $HCF = \frac{HCF(Numerators)}{LCM(Denominators)}$
  
  $LCM = \frac{LCM(Numerators)}{HCF(Denominators)}$
  
  ## Area
  
  ### Rectangle
  
  $\rightarrow area = length \times bread$
  
  $\rightarrow perimeter = 2 ( length + bread)$
  
  ### Square
  
  $\rightarrow area = side^{2}$
  
  $\rightarrow perimeter = 4 \times side$
  
  ### Rhombus
  
  $\rightarrow area = \frac{product of diagonals}{2}$
  
  ### Equilateral Triangle
  
  $\rightarrow area = \frac{ \sqrt{n} \times side^{2}}{4}$
  
  $\rightarrow radius of incircle = \frac{side}{2 \times \sqrt{3}}$
  
  $\rightarrow radius of circle = \frac{side}{\sqrt{3}}$
  
  ### Isosceles Triangle
  
  $\rightarrow area = \frac{base \times length}{2}$
  
  ### Heron’s Formula
  
  $\rightarrow area = \sqrt{s(s-a)(s-b)(s-c)}$
  
  where s is semi-perimeter
  
  $\rightarrow s = \frac{a + b + c}{2}$
  
  ### Circle
  
  $\rightarrow area = \pi \times R^{2}$
  
  $\rightarrow circumference = 2 \times \pi \times R$
  
  ### Parallelogram
  
  $\rightarrow area = base \times height$
  
  ## Volume
  
  ### Cuboid
  
  $\rightarrow Volume = L \ast B \ast H$
  
  $\rightarrow Surface area = 2 \cdot (LB + BH + LH)$
  
  $\rightarrow Diagonal = \sqrt{L^2 + B^2 + H^2}$
  
  ### Cube
  
  $\rightarrow Volume = a^3$
  
  $\rightarrow Surface area = 6 \cdot a^2$
  
  $\rightarrow Diagonal = \sqrt{3}a$
  
  ### Cylinder
  
  $\rightarrow Volume = \pi r^2h$
  
  $\rightarrow Curved surface area = 2 \pi rh$
  
  $\rightarrow Total surface area = 2 \pi rh + 2 \pi r^2$
  
  ### Cone
  
  $\rightarrow Slant height = \sqrt{h^2 + r^2}$
  
  $\rightarrow Volume = \frac{\pi r^2 h}{3}$
  
  $\rightarrow Curved surface area = \pi rL$
  
  $\rightarrow Total surface area = \pi rL + \pi r^2$
  
  ### Sphere
  
  $\rightarrow Volume = \frac{4 \pi r^3}{3}$
  
  $\rightarrow Surface area = 4 \pi r^2$
  
  ## Trignometry
  
  $Radian = \frac{\pi}{180} \times θ$
  
  ### Trignometric Ratios
  
  $sin θ = \frac{Perpendicular}{Hypotenuse}$
  
  $cos θ = \frac{Base}{Hypotenuse}$
  
  $tan θ = \frac{Perpendicular}{Base}$
  
  $sec θ = \frac{Hypotenuse}{Base}$
  
  $cosec θ = \frac{Hypotenuse}{Perpendicular}$
  
  $cot θ = \frac{Base}{Perpendicular}$
  
  ### Fundamental Trignometric identities
  
  1. $sin^2 A + cos^2 A = 1$
  2. $1 + tan^2 A = sec^2 A$
  3. $1 + cot^2 A = cosce^2 A$
  
  ### Reciprocal Identities
  
  $sin θ = \frac{1}{cosec θ}$
  
  $cos θ = \frac{1}{sec θ}$
  
  $tan θ = \frac{1}{cot θ}$
  
  ### Trigonometry Table
  
  Angle0°, 030°, π/645°, π/460°, π/390°, π/2
  $sin θ$01/21/√2√3/21
  $cos θ$1√3/21/√21/20
  $tan θ$01/√31√3
  $cot θ$√311/√30
  $sec θ$12/√3√22
  $cosec θ$2√22/√31
  
  ### Periodicity Identities
  
  • $sin (π/2 – θ) = cos θ$
  • $cos (π/2 – θ) = sin θ$
  • $sin (π/2 + θ) = cos θ$
  • $cos (π/2 + θ) = – sin θ$
  
  • $sin (3π/2 – θ) = – cos θ$
  • $cos (3π/2 – θ) = – sin θ$
  • $sin (3π/2 + θ) = – cos θ$
  • $cos (3π/2 + θ) = sin θ$
  
  • $sin (π – θ) = sin θ$
  • $cos (π – θ) = – cos θ$
  • $sin (π + θ) = – sin θ$
  • $cos (π + θ) = – cos θ$
  
  • $sin (2π – θ) = – sin θ$
  • $cos (2π – θ) = cos θ$
  • $sin (2π + θ) = sin θ$
  • $cos (2π + θ) = cos θ$
  
  ### Co-function Identities
  
  • sin(90° − x) = cos x
  • cos(90° − x) = sin x
  • tan(90° − x) = cot x
  • cot(90° − x) = tan x
  • sec(90° − x) = cosec x
  • cosec(90° − x) = sec x
  
  ### Inverse Formulas
  
  • $sin^{-1} (-x) = -sin^{-1} x$
  
  • $cos^{-1} (-x) = π - cos^{-1} x$
  
  • $tan^{-1} (-x) = -tan^{-1} x$
  
  • $cosec^{-1} (-x) = -cosec^{-1} x$
  
  • $sec^{-1} (-x) = π - sec^{-1} x$
  
  • $cot^{-1} (-x) = π - cot^{-1} x$
  
  ## Logarithm
  
  Logarithm is the inverse function to exponentiation.
  
  $\log_a{b} = c \implies a^c = b$
  
  $\log_2{8} = 3 \implies 2^3 = 8$
  
  ### Types of logs
  
  • Common log $\rightarrow$ base 10 $\rightarrow log_10{x}$
  • Natural log $\rightarrow$ base e $\rightarrow log_e{x}$ or $lnx$
  • Binary log $\rightarrow$ base 2 $\rightarrow log_2{x}$
  
  ### Laws of logarithms
  
  $\log_ab + \log_ac = \log_a{bc}$
  
  #### Subtraction Property
  
  $\log_ab - \log_ac = \log_a{\frac{b}{c}}$
  
  #### Argument-Power Property
  
  $\log_ab^n = n\log_ab$
  
  #### Inverse Property
  
  $\log_ab = \frac{1}{\log_ba}$
  
  $\log_a{\frac{1}{b}} = - \log_ab$
  
  #### Power Property
  
  $\log_{a^n}b^n = \log_ab$
  
  #### Change-of-Base
  
  $\frac{\log_cb}{\log_ca} = \log_ab$
  
  • $log_a{1} = 0$
  • $log_aa = 1$
  
  ## Problems
  
  ### Number of digits in an integer
  
  #### Iterative
  
  count(n){
  int cnt = 0;
  while(n){
  cnt += n%10;
  n /= 10;
  }
  
  return cnt;
  }
  
  
  #### Recursive
  
  count(n){
  if(!n) return n;
  return 1+count(n)l
  }
  
  
  #### Logarithmic
  
  count(n){
  return floor(log(n) + 1);
  }
  
  
  ### Check if the given integer is a palindrome or not.
  
  bool isPal(int n){
  int rev = 0;
  int tmp = n;
  
  while(tmp){
  int ones = tmp % 10;
  rev = rev * 10 + ones;
  tmp /= rmp;
  }
  
  return rev == n;
  }
  
  
  ### Factorial of a number
  
  #### Iterative
  
  int fact(int n);
  
  int res = 1;
  
  for(int i=2; i<=n; i++)
  res *= i;
  
  return res;
  }
  
  
  #### Recursive
  
  int fact(int n){
  if(!n) return 1;
  return n * fact(n-1);
  }
  
  
  ### Count trailing zeros in the factorial of a number
  
  int ctz(int n){
  int res = 0;
  for(int i=5; i<=n; i *= 5)
  res += n/i;
  return res;
  }
  
  
  TC : O(log5n)
  
  ### GCD of two numbers
  
  #### Naive
  
  int gcd(int a, int b){
  int res = min(a, b);
  
  while(res){
  if(a%res == 0 and b%res == 0)
  break;
  res--;
  }
  
  return res;
  }
  
  
  Time Complexity: O(min(a,b))
  
  #### Euclidean Algorithm
  
  int gcd(int a, int b){
  while(a != b)
  if(a>b)
  a = a-b;
  else
  b = b-a;
  return a;
  }
  
  
  #### Optimized Euclidean Algorithm
  
  int gcd(int a, int b){
  if(b==0)
  return a;
  return gcd(b, a%b);
  }
  
  
  Time Complexity: O(log max(a,b))
  
  #### Extended Euclidean Algorithm
  
  int gcd(int a, int b, int *x, int *y)
  {
  if (a == 0)
  {
  *x = 0;
  *y = 1;
  return b;
  }
  
  int res = gcd(b%a, a, &x1, &y1);
  
  *x = y1 - (b/a) * x1;
  *y = x1;
  
  return res;
  }
  
  
  ### LCM of two numbers
  
  #### Naive
  
  int gcd(int a, int b){
  int res = max(a, b);
  
  while(res){
  if(res%a == 0 and res%a == 0)
  break;
  res++;
  }
  
  return res;
  }
  
  
  Time Complexity: O(a*b - max(a,b))
  
  #### Efficient Approach
  
  $\rightarrow a\times b = gcd(a,b) \times lcm(a,b)$
  
  $\rightarrow lcm(a,b) = \frac{a\times b}{gcd(a,b)}$
  
  Time Complexity: O(log max(a,b))
  
  ### Prime number
  
  #### Naive approach
  
  bool isPrime(int n)
  {
  if (n <= 1)
  return false;
  
  for (int i = 2; i < n; i++)
  if (n % i == 0)
  return false;
  
  return true;
  }
  
  
  Time Complexity: O(n)
  
  #### Efficient approach
  
  bool isPrime(int n)
  {
  if (n <= 1)
  return false;
  
  for (int i = 2; i*i <= n; i++)
  if (n % i == 0)
  return false;
  
  return true;
  }
  
  
  Time Complexity: O($\sqrt{n}$)
  
  #### Optimized approach
  
  bool isPrime(int n)
  {
  if (n <= 1)
  return false;
  if (n <= 3)
  return true;
  
  if (n % 2 == 0 || n % 3 == 0)
  return false;
  
  for (int i = 5; i * i <= n; i = i + 6)
  if (n % i == 0 || n % (i + 2) == 0)
  return false;
  
  return true;
  }
  
  
  ### Prime factorization of a number
  
  #### Naive
  
  bool isPrime(int n)
  {
  if (n <= 1)
  return false;
  if (n <= 3)
  return true;
  
  if (n % 2 == 0 || n % 3 == 0)
  return false;
  
  for (int i = 5; i * i <= n; i = i + 6)
  if (n % i == 0 || n % (i + 2) == 0)
  return false;
  
  return true;
  }
  
  void primeFactors(int n)
  {
  for (int i = 2; i <= n; i = i + 2)
  {
  
  if(isPrime(i))
  
  int x = i;
  
  while (n % x == 0)
  {
  cout << i << " ";
  x = x*i;
  }
  }
  
  }
  
  
  Time Complexity: O($nlogn$)
  
  #### Efficient
  
  void primeFactors(int n)
  {
  if (n <= 1) return;
  
  for (int i = 2; i*i <= n; i = i + 2)
  {
  while (n % i == 0)
  {
  cout << i << " ";
  n = n/i;
  }
  }
  
  if (n > 1)
  cout << n << " ";
  }
  
  
  Time Complexity: O($\sqrt{n} logn$)
  
  #### Using Sieve
  
  void primeFactors(int n)
  {
  int c=2;
  while(n>1)
  {
  if(n%c==0){
  cout<<c<<" ";
  n/=c;
  }
  else c++;
  }
  }
  
  
  Time Complexity: O(n)
  
  #### Naive
  
  void printDivisors(int n)
  {
  for (int i = 1; i <= n; i++)
  if (n % i == 0)
  cout <<" " << i;
  }
  
  
  Time Complexity: O(n)
  
  #### Efficient
  
  void printDivisors(int n)
  {
  for (int i=1; i*i<=n; i++)
  {
  if (n%i == 0)
  cout << i << " ";
  }
  
  for (; i>=1; i--)
  {
  if (n%i == 0)
  cout << n/i << " ";
  }
  }
  
  
  Time Complexity: O($\sqrt{n}$)
  
  ### N Prime Numbers
  
  #### Naive
  
  void nPrimes(){
  for(int i=2; i<=n; i++)
  if(isPrime(i))
  cout << i << " ";
  }
  
  
  Time Complexity: O($n \times \sqrt{n}$)
  
  #### Sieve of Eratosthenes
  
  void manipulated_seive(int n)
  {
  
  vector<bool> isPrime(n+1, true);
  
  for (int i=2; i*i<=n ; i++)
  {
  if (isprime[i])
  {
  cout << i << " "
  for(int j=i*i; j<=n; j+= i)
  isPrime[j] = false;
  }
  }
  }
  
  
  Time Complexity: O($log log n$)
  
  ### Computating Pow(x,n)
  
  #### Naive
  
  FOR(1->n) : x = x*x;
  
  Time Complexity: O(n)
  
  #### Optimized
  
  double myPow(double x, int n) {
  if(n==0) return 1.0;
  double y = myPow(x, n/2);
  
  if(n % 2 == 0)
  return y*y;
  else return n < 0 ? (y*y)/x : x*y*y;
  }
  
  
  Time Complexity: O(logn)
  
  #### Constant Space
  
  $\rightarrow$ Every natural number can be written as the sum of distinct powers of 2.
  
  double myPow(long long int x, long long int n) {
  long long int res = 1;
  while(n>0){
  
  if(n&1)
  res = res * x;
  
  x *= x;
  n = n >> 1;
  }
  return res;
  }
  
  
  Time Complexity: O(logn)
metadata: {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}