Table of Contents

Contents Page

Bipartite graph 1

Floyd 1

DSU 2

Subtree count 2

MST-Kruskal 3

Dijkstra 4

BFS 5

Cycle detection 5

Printing Cycle 6

Tree diameter 6

Bellman 7

Optimized bellman 8

SCC 10

Ordered set 11

Trie 12

Segment tree 13

Bitmask 14

To binary 15

Get bits , bits cnt 15

Fast power 15

NCR and NPR 16

GCD 16

LCM 16
● Bipartite graph O(n+m)
int n;
vector<vector<int>> adj;

vector<int> side(n, -1);

bool is_bipartite = true;
queue<int> q;
for (int st = 0; st < n; ++st) {
if (side[st] == -1) {
q.push(st);
side[st] = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
for (int u : adj[v]) {
if (side[u] == -1) {
side[u] = side[v] ^ 1;
q.push(u);
} else {
is_bipartite &= side[u] != side[v];
}
}
}
}
}
cout << (is_bipartite ? "YES" : "NO") << endl;

● Floyd O(N3)
void Floyd(){
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
floyd[i][j] = min( floyd[i][k] + floyd[k][j],
floyd[i][j] );
return;}
void process(){
for(int i = 0; i <= 200; i++) {
for(int j = 0; j <= 200; j++) {
if( i == j ) floyd[i][j] = 0;
else floyd[i][j] = 1000000000;
// set to size bigger than the biggest cost
}
}Return;}

1
● Dijkstra O((n+e) log(e))
void Display(ll node){
if(node == -1) return;
Display( parent[node] );
cout << node << " ";
}
int main(){
for(ll i = 0; i <= 1e6; i++) costs[i] = 1e12;
// cost node
priority_queue < pair <ll, ll> > pq;
pq.push( {0, 1} );
costs[1] = 0;
parent[1] = -1;
bool ok = false;
while(!pq.empty()) {
ll cost = -pq.top().first;
ll node = pq.top().second;
pq.pop();
if(node == n) {
ok = true;
break;
}
if (cost > costs[node]) continue;
for(ll i = 0; i < v[node].size(); i++) {
if( cost + v[node][i].second < costs[v[node][i].first]) {
costs[v[node][i].first] = cost + v[node][i].second;
parent[v[node][i].first] = node;
pq.push( { -(costs[v[node][i].first]),
v[node][i].first} );
}
}
}
if(ok) return Display(n), 0;
else return cout << -1, 0;

4
● BFS O(n+m)
vector<vector<int>> adj; // adjacency list representation
int n; // number of nodes
int s; // source vertex

queue<int> q;
vector<bool> used(n);
vector<int> d(n), p(n);

q.push(s);
used[s] = true;
p[s] = -1;
while (!q.empty()) {
int v = q.front();
q.pop();
for (int u : adj[v]) {
if (!used[u]) {
used[u] = true;
q.push(u);
d[u] = d[v] + 1;
p[u] = v;
}
}
}

● Cycle detection O(n+m)

vector<vector<int>> adj;
vector<bool> visited;
vector<int> parent;
int cycle_start, cycle_end;

bool dfs(int v, int par) { // passing vertex and its parent vertex
visited[v] = true;
for (int u : adj[v]) {
if(u == par) continue; // skipping edge to parent vertex
if (visited[u]) {
cycle_end = v;
cycle_start = u;
return true;
}
parent[u] = v;
if (dfs(u, parent[u]))
return true;
}
return false;}

5
● To binary

void tobinary(int n)
{
while(n>0)
{
v.push_back(n%2);
n=n/2;
}
for(int i=v.size()-1; i>=0; i--)
cout << v[i];
v.clear();
}

● Get bits & Cnt bits

ll cnt_bit(ll x)
{
return __builtin_popcountll(x);
}

● Fast Power

ll fp(ll base, ll exp)

{
if (exp == 0)
return 1;
ll ans = fp(base, exp / 2);
ans = (ans * ans) % mod;
if (exp % 2 != 0)
ans = (ans * (base % mod)) % mod;
return ans;
}

15
● NCR and NPR

void calcFacAndInv(ll n)
{
fact[0] = inv[0] = 1;
for (ll i = 1; i <= n; i++)
{
fact[i] = (i * fact[i - 1]) % mod;
inv[i] = fp(fact[i], mod - 2);
}
}

ll ncr(ll n, ll r)
{
return ((fact[n] * inv[r]) % mod * inv[n - r]) % mod;
}

ll npr(ll n, ll r)
{
return (fact[n] * inv[n - r]) % mod;
}

● GCD and LCM:

int GCD(int a, int b){

if(b==0) return a;
else return GCD(b, a%b);
}
int LCM(int a, int b){
return (a*b)/GCD(a,b);
}

● Sieve
bool prime[100000];
int n = 1000;
memset(prime , true, sizeof prime );
prime[0] = prime[1] = false;
for (int i = 2; i * i <= n; i++)
if ( prime[i])
for (int j = i * i; j <= n; j += i)
prime[j] = false;

16
● Prime Factorization
void printPrimeFactors(int n) {
while (n%2 == 0){
cout<<"2\t";
n = n/2;
}
for (int i = 3; i <= sqrt(n); i = i+2){
while (n%i == 0){
cout<<i<<"\t";
n = n/i;
}
}
if (n > 2)
cout<<n<<"\t";
}

17
● Smallest prime factor (optimized) O(log(n))

bool v[MAX];
int len, sp[MAX];

void Sieve(){
for (int i = 2; i < MAX; i += 2) sp[i] = 2;//even numbers have
smallest prime factor 2
for (lli i = 3; i < MAX; i += 2){
if (!v[i]){
sp[i] = i;
for (lli j = i; (j*i) < MAX; j += 2){
if (!v[j*i]) v[j*i] = true, sp[j*i] = i;
}
}
}
}
int main() {
Sieve();
for (int i = 0; i < 50; i++) cout << sp[i] << endl;
return;
}
void primeFactors(int n)
{
while(n%2==0)
{
cout << 2 << " ";
n = n/2;
}
// n must be odd at this point. So we can skip, one element (Note
i = i +2)
for(int i=3; i<=sqrt(n); i+=2)
{
while (n%i==0)
{
cout << i << " ";
n/=i;
}
}
// This condition is to handle the case when n, is a prime number
greater than 2
if (n>2) cout << n << " "; }

18
● Power & Big power

ll power(ll b,ll e)
{
if(e==0)
return 1;
if(e&1)
return b*power(b*b,e/2);
return power(b*b,e/2);
}
double bigPower(double a, int n)
{
double x = a, ret = 1;
while(n)
{
int currentBit = n&1;
if(currentBit)
ret *= x;
x*=x;
n = n>>1;
}
return ret;
}

● Is Power of 2

bool isPowerOfTwo(int x)
{
// x will check if x == 0 and !(x & (x - 1)) will check if x is a
power of 2 or not
return (x && !(x & (x - 1)));
}

19
● Perfect Squares

bool perfectsquares(ll n)
{
ll i=4, j=3;
bool ans=true;
while(i<=n && ans)
{
if(n%i==0)
ans=false;
j+=2;
i+=j;
}
return ans;
}

● eGCD

int eGCD(int a, int b, int &x0, int &y0) {

// 30x + 12y = g by-return x, y
int r0 = a, r1 = b, x1, y1;
x1 = y0 = 0;
x0 = y1 = 1;
while (r1) {
int q = r0 / r1;
move1step(x0, x1, q);
move1step(y0, y1, q);
move1step(r0, r1, q);
}
return r0;
}

● GCD move one step

int move1step(int &a, int &b, int q) {

int next = a - q * b;
a = b;
b = next; }

20
● Get Divisors

set<ll>GetDivisors(ll val)
{
set<ll> st;
for(int i=1; i<=sqrt(val); i++)
if(val%i==0)
st.insert(i), st.insert(val/i);
return st;
}
void divisions(ll num)
{
vector<ll>v;
for(ll i=1; i<=sqrt(num); i++ )
{
if(num%i==0)
{
v.push_back(i);
if(i!=num/i)
v.push_back(num/i);
}
}
}

● Binary search
int low = 0, high = n - 1, mid;
while ( low <= high ) {
mid = (low + high)/2;
if ( arr[mid] < k ) low = mid + 1;
else if ( arr[mid] > k ) high = mid - 1;
Else return cout << "found", 0;
}

21
 ● First occurrence
int low = 0, high = n - 1, mid;
while ( low <= high ) {
mid = (low + high)/2;
if ( arr[mid] < k ) low = mid + 1;
else if ( arr[mid] > k ) high = mid - 1;
else {
ans = mid;
high = mid - 1;
}
}
cout << ans;

● Last occurence
int low = 0, high = n - 1, mid;
while ( low <= high ) {
mid = (low + high)/2;
if ( arr[mid] < k ) low = mid + 1;
else if ( arr[mid] > k ) high = mid - 1;
else {
ans = mid;
low = mid + 1;
}
}

● Lower bound
// get first number less than or equal k
int low = 0, high = n - 1, mid;
while ( low <= high ) {
mid = (low + high)/2;
// if you want the number itself ( arr[mid] <= k )
if ( arr[mid] < k ) {
ans = arr[mid];
low = mid + 1;
}
else high = mid - 1;
}

22
 ● Upper bound
// first number bigger than or equal k
int low = 0, high = n - 1, mid;
while ( low <= high ) {
mid = (low + high)/2;
// if you want the number itself ( arr[mid] >= k )
if ( arr[mid] < k ) low = mid + 1;
else if ( arr[mid] > k ) {
ans = arr[mid];
high = mid - 1;
}
else low = mid + 1;
}

● Ternary
// for int
int low = 0, high = n - 1, mid1, mid2;
while ( low < high ) {
mid1 = (low + high)/2;
mid2 = mid1 + 1;
if ( mid1 > mid2 ) low = mid2;
Else high = mid1;
}
cout << high;
// for double
int e = (max x), s = (min x), mid1, mid2;
while ( e - s >= 1e-6 ) {
mid1 = s + ( e - s )/3;
mid2 = e - ( e - s )/3;
if ( arr[mid1] > arr[mid2] ) s = mid1;
else e = mid2;
}

● Merge sort
void mergesort(vector<int>&arr, int low, int high)
{
if(low<high)
{
int mid=(low+high)/2;
mergesort(arr, low, mid);
mergesort(arr, mid+1, high);
}
}

23
 ● Angles

const double PI
= acos(-1.0);

double toDegeeFromMinutes(double minutes) {

return (minutes / 60);
}

double toRadians(double degree) {

return (degree * PI / 180.0);

double toDegree(double radian) {

if (radian < 0) radian += 2 * PI;
return (radian * 180 / PI);
}

● Solving triangles

double fixAngle(double A) {
return A > 1 ? 1 : (A < -1 ? -1 : A);
}

// sin(A)/a = sin(B)/b = sin(C)/c

double getSide_a_LAB(double b, double A, double B) {
return (sin(A) * b) / sin(B);
}

double getAngle_A_abB(double a, double b, double B) {

return asin(fixAngle(a * sin(B)) / b));
}

// a^2 = b^2 + c^2 - 2*b*c*cos(A)

double getAngle_A_abc(double a, double b, double c) {
return acos(fixAngle(b * b + c * c - a * a) / (2 * b * c)));
}

29
 ● Triangle Areas

double triangleArea(point p0, point p1, point p2) {

double a = length(p0 - pl), b = length(p0 - p2), c = length(p1
- p2);
double s = (a + b + c) / 2;
return sqrt((s - a) * (s - b) * (s - c) * 5); //Heron's formula
// base=u+v (divided by h) u = (a^2 + b^2 - C2)/2a,
// h - sqrt(b^2-^2) where base is a.
// If these 3 points on circle boundry (Trinagle inside circle)
// double radius1 = (a*b*c)/(4*triangleArea);
// If circle inside triangle
// double radius2 - sqrt((s-a)*(s-b)*(-C)/s);
}

// Given the length of three medians of a triangle, find area

double triangleAreal(double m1, double m2, double m3) {
// Area of triangle using medians as sides = 3/4 * (area of
original triangle)
if (m1 <= 0 || m2 <= 0 || m3 <= 0) return -1; // impossipole
// For area made by sides as medians
double s = 0.5 * (m1 + m2 + m3);
double medians_area = (s * (s - m1) * (s - m2) * (s - m3));
double area = 4.0 / 3.0 * sqrt(medians_area);
if (medians_area <= 0.0 || area <= 0) return -1; // impossipole
return area;
}

30
 ● Points and Lines
#define X real()
#define Y imag()
#define angle(a) (atan2((a).imag(), (a).real()))
#define vec(a, b) ((b)-(a))
#define same(p1, p2) (dp(vec(p1,p2),vec(p1,p2)) < EPS)
#define dp(a, b) ( (conj(a)*(b)).real() ) // a*b cos(T), if
zero -> prep
#define cp(a, b) ( (conj(a)*(b)).imag() ) // a*b sin(T), if
zero ->parallel
#define length(a) (hypot((a).imag(), (a).real()))
#define normalize(a) (a)/length(a)
//#define polar(r,ang) ((r)*exp(point(0,ang))) ==> Already added
in c++11
#define rotateO(p, ang) ((p)*exp(point(0,ang)))
#define rotateA(p, ang, about) (rotateO(vec(about,p),ang)+about)
#define reflectO(v, m) (conj((v)/(m))*(m))
point reflect(point p, point p0, point p1) {
point z = p-p0, w = p1-p0;
return conj(z/w)*w + p0; // Reflect point p around p0p1
}
bool isCollinear(point a, point b, point c) {
return fabs( cp(b-a, c-a) ) < EPS;
}
bool isPointOnRay(point p0, point p1, point p2) {
if(length(p2-p0) < EPS) return true;
return same( normalize(p1-p0), normalize(p2-p0) );
}
bool isPointOnRay(point a, point b, point c) { // not tested?
if(!isCollinear(a, b, c))
return false;
return dcmp(dp(b-a, c-a), 0) == 1;
}
bool isPointOnSegment(point a, point b, point c) {
return isPointOnRay(a, b, c) && isPointOnRay(b, a, c);
}
bool isPointOnSegment(point a, point b, point c) {
double acb = length(a-b), ac = length(a-c), cb =
length(b-c);
return dcmp(acb-(ac+cb), 0) == 0;
}

31
 double distToLine( point p0, point p1, point p2 ) {
return fabs(cp(p1-p0, p2-p0)/length(p0-p1)); // area =
0.5*b*h
}
//distance from point p2 to segment p0-p1

// 0 a==b, -1 a<b, 1 a>b

int dcmp(double a,double b){
if(fabs(a-b)<=EPS)return 0;
else if(a<b)return -1;
else return 1;
}
// point c above line a-b
// 1 above , 0 on, -1 below
int isPointAboveLine(point a,point b,point c)
{
if(cp(b-a,c-a)>0)return 1;
else if(cp(b-a,c-a)<0)return -1;
else return 0;
}

bool intersectSegments(point a, point b, point c, point d, point &

intersect) {
double d1 = cp(a - b, d - c), d2 = cp(a - c, d - c), d3 = cp(a -
b, a - c);
if (fabs(d1) < EPS)
return false; // Parallel || identical

double t1 = d2 / d1, t2 = d3 / d1;

intersect = a + (b - a) * t1;

if (t1 < -EPS || t2 < -EPS || t2 > 1 + EPS)

return false; //e.g ab is ray, cd is segment ... change to
whatever
return true;
}

32
// Where is P2 relative to segment p0-p1?
// ccw = +1 => angle > 0 or collinear after p1
// cw = -1 => angle < 0 or collinear after p0
// Undefined = 0 => Collinear in range [a, b]. Be careful here
int ccw(point a, point b, point c) {
point v1(b - a), v2(c - a);
double t = cp(v1, v2);

if (t > +EPS)
return +1;
if (t < -EPS)
return -1;
if (v1.X * v2.X < -EPS || v1.Y * v2.Y < -EPS)
return -1;
if (norm(v1) < norm(v2) - EPS)
return +1;
return 0;
}
bool intersect(point p1, point p2, point p3, point p4) {
// special case handling if a segment is just a point
bool x = (p1 == p2), y = (p3==p4);
if(x && y) return p1 == p3;
if(x) return ccw(p3, p4, p1) == 0;
if(y) return ccw(p1, p2, p3) == 0;
return ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 &&
ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0; }
// Accurate and efficient
int isInsidePoly(vector<point> p, point p0) {
int wn = 0; // the winding number counter
for (int i = 0; i < sz(p); i++) {
point cur = p[i], nxt = p[(i + 1) % sz(p)];
if (isPointOnSegment(cur, nxt, p0))
return true;
if (cur.Y <= p0.Y) { // Upward edge
if (nxt.Y > p0.Y && cp(nxt-cur, p0-cur) > EPS)
++wn;
} else { // Downward edge
if (nxt.Y <= p0.Y && cp(nxt-cur, p0-cur) < -EPS)
--wn;
}
}
return wn != 0;
}

33
 ● Pick’s Theorem

int n;
cin >> n;
pair<int, int> a[n + 5];
for (int i = 0; i < n; i++)
cin >> a[i].first >> a[i].second;
ll area = 0, boundary = 0; // area = x1*y2 - x2*y1
for (int i = 0; i < n; i++) {
ll x1 = a[i].first, y1 = a[i].second, x2 = a[(i + 1) %
n].first, y2 = a[(i + 1) % n].second;
area += x1 * y2 - x2 * y1;
boundary += __gcd(abs(x1 - x2), abs(y1 - y2));
}
area = abs(area);
area /= 2;
cout << area - boundary / 2 + 1 << endl;

● Calculate Polygon Area (shoelace)

//to check if the points are sorted anti-clockwise or clockwise remove the fabs
at the end and it will return -ve value if clockwise
ld polygonArea(ld x[], ld y[], int n) {
ld ret = 0;
for(int i = 0; i < n; i++){
int j = (i + 1) % n;
ret += x[i] * y[j];
}
return fabs(ret) / 2;
}

● To determine if a point is inside a circle

If angle is bigger than or equal 90
Dot product because cos determines the angle
If dot product == 0, on the line
Else if dot product < 0, inside the line
Else if dot product > 0, outside the line

bool inDisk(point a, point b) {

return dot( a - p, b - p ) <= 0;
}

34
 ● Check if a point is inside a circle
// 0 outside the circle, 1 on the circle line, 2 inside the circle
int inCircle(point cen, ld r, point p) {
ld sqrlen = lengthSqr(p - cen);
if (fabs(sqrlen - r * r) < EPS) return 1;
if (fabs(sqrlen < r * r)) return 2;
return 0;
}

● To check if point is inside a rectangle

float area(int x1, int y1, int x2, int y2, int x3, int y3) {
return abs((x1 * (y2 - y3) + x2 * (y3 - y1) +
x3 * (y1 - y2)) / 2.0);
}
/* A function to check whether point P(x, y) lies inside the rectangle formed
by A(x1, y1), B(x2, y2), C(x3, y3) and D(x4, y4) */
bool check(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int
x, int y) {
/* Calculate area of rectangle ABCD */
float A = area(x1, y1, x2, y2, x3, y3) + area(x1, y1, x4, y4, x3, y3);
/* Calculate area of triangle PAB */
float A1 = area(x, y, x1, y1, x2, y2);
/* Calculate area of triangle PBC */
float A2 = area(x, y, x2, y2, x3, y3);
/* Calculate area of triangle PCD */
float A3 = area(x, y, x3, y3, x4, y4);
/* Calculate area of triangle PAD */
float A4 = area(x, y, x1, y1, x4, y4);
/* Check if sum of A1, A2, A3 and A4 is same as A */
return (A == A1 + A2 + A3 + A4);
}

● To check if a point is on the right or left of a line

int point_pos(point a, point b, point c)
{
if (cross((b - a), (c - a)) == 0) return 0; // on line
else if (cross((b - a), (c - a)) < 0) return 1; // right
else if (cross((b - a), (c - a)) > 0) return -1; // left
}

35
 ● Triangle Area
// angles in radian
ld triangleArea2anglesSide(ld t1, ld t2, ld s) {
return fabs(s * s * sin(t1) * sin(t2) / (2 *
sin(t1 + t2)));
}

ld triangleArea2sidesAngle(ld a, ld b, ld t) {
return fabs(a * b * sin(t) / 2);
}

ld triangleAreaBH(long double b, long double h) {

return b * h / 2;
}

ld triangleArea3sides(ld a, ld b, ld c) {
ld s((a + b + c) / 2);
return sqrt(s * (s - a) * (s - b) * (s - c));
}

ld triangleArea3points(point a, point b, point c) {

return fabs(cross(a,b) + cross(b,c) +
cross(c,a)) / 2;
}

● Cosine Rule
ld cosRule(ld a, ld b, ld c) {
ld res = (b * b + c * c - a * a) / (2 * b *
c); if (res > 1) res = 1;
if (res < -1) res = -1;
return acos(res);
}

● Sine Rule
ld sinRuleAngle(ld s1, ld s2, ld a1) {
ld res = s2 * sin(a1) / s1;
if (res > 1) res = 1;
if (res < -1) res = -1;
return asin(res);
}
ld sinRuleSide(ld s1, ld a1, ld a2) {
// Handle denom = 0
ld res = s1 * sin(a2) / sin(a1);
return fabs(res);
}

40
 ● Next greater element O(N)

void printNGE(int arr[], int n)

{
stack<int> s;
int res[n];
for (int i = n - 1; i >= 0; i--) {

if (!s.empty()) {
while (!s.empty() && s.top() <= arr[i]) {
s.pop();
}
}
res[i] = s.empty() ? -1 : s.top();
s.push(arr[i]);
}
for (int i = 0; i < n; i++)
cout << arr[i] << " --> " << res[i] << endl;
}

int main()
{
int arr[] = { 11, 13, 21, 3 };
int n = sizeof(arr) / sizeof(arr[0]);

printNGE(arr, n);
return 0;
}

● Is it a power of two?

bool isPowerOfTwo(ll n) {
/*
N = 4, 000100
N-1 = 3, 000011
*/
return n && (!(n & (n - 1)));
}

41
 max_current = max(arr[i], max_current + arr[i]);

max_global = max(max_global, max_current);

}

cout << max_global << endl;

}

● Fast Fibonacci O(log(n))

//fast_Fibonacci O(log(n))
int fast_Fibonacci(int n){
int i=1, h=1, j=0, k=0, t;
while (n > 0) {
if (n%2 == 1)
t = j*h, j = i*h + j*k + t, i = i*k + t;
t = h*h, h = 2*k*h + t, k = k*k + t, n = n/2;
}
return j;
/* Golden Mean
double d = sqrt(5);
double b=pow( (1+d)/2, n);
double c=pow( (1-d)/2, n);
cout<<(b-c)/d;
*/
}

● Pascal

void Pascal(int n)
{
// ncr -> n = row, r = column;
int arr[n][n];
for (int line = 0; line < n; line++)
for (int i = 0; i <= line; i++)
if (line == i || i == 0) arr[line][i] = 1;
Else arr[line][i] = arr[line - 1][i - 1] + arr[line-1][i] ;
}

43
 ● Geometry Rules

● Area of regular polygon : (n * L * a)/2, where the length of ‘a’ is given

as the L / (2 * tan(180/n)
-
where ‘L’ is the side length, ‘n’ is the number of sides of the regular polygon and
‘a’ is the length from the center to the vertices.
- In terms of the perimeter of a regular polygon, the area of a regular polygon is
given as, Area = (Perimeter × apothem)/2, in which perimeter = n * L
● Area of triangle = (½) * a * b * sin(c) ,where c the angle between sides a and b

● Heron’s Formula = sqrt( s (s-a) (s-b) (s-c) )

45
 - where s = (a + b + c)/2, a, b, and c are the length of its sides.

● Area of rhombus = (1/2) × (product of diagonals

● Area of Sector = theta / 2 * r * r “when theta is in radians”

● Area of Sector = theta / 360 * pi * r * r “when theta is in degrees”

● Length of Arc = theta / 360 * 2 * pi * r

46
 𝑛(𝑛 − 3)
● Number of diagonals =
2

1 1 2 2 2 2
● Area = 2
𝑃𝑄 𝑠𝑖𝑛(θ)= 4 (𝑏 + 𝑑 − 𝑎 + 𝑐 )𝑡𝑎𝑛(θ)=

1 2 2 2 2 2 2 2
4
4𝑃 𝑄 − (𝑏 + 𝑑 − 𝑎 −𝑐 ) =
1
(𝑠 − 𝑎)(𝑠 − 𝑏)(𝑠 − 𝑐)(𝑠 − 𝑑) − 𝑎𝑏𝑐𝑑𝑐𝑜𝑠 2
(𝐴 + 𝐶)

1 2
● Area of sector =
2
𝑟 θ𝑟𝑎𝑑

47
 ● Area of triangle = 𝑝(𝑝 − 𝑎)(𝑝 − 𝑏)(𝑝 − 𝑐), where a, b,
𝑎+𝑏+𝑐
c are the lengths of the three sides and p =
2
=
𝑎𝑏𝑠𝑖𝑛(𝐶) | 𝐴𝑥(𝐵𝑦−𝐶𝑦) + 𝐵𝑥(𝐶𝑦−𝐴𝑦)+𝐶𝑥(𝐴𝑦−𝐵𝑦) | 2
|=
3
= | 𝑆,
2 2 4

where s is any side of an equilateral triangle =

𝐴×𝐵 + 𝐵×𝐶+ 𝐶×𝐴
, where A, B, C are the three vectors
2

● Area of an ellipse: abπ

● Lengths of a right-angled triangle given non-hypot side:
2 2 2 2
𝑛 𝑛 𝑛 𝑛
4
, 4
+ 1, 𝑛,n is even, 2
, 2
+ 1, 𝑛,n is
odd
θ
● Chord length: 2𝑟𝑠𝑖𝑛( 2 )

48
 ● c2= a2+b2-2ab cos(⁡C)
𝑟𝑎𝑑
θ *180
● θo=
Π

49
 ● Math Rules

● LCM * GCD = the multiple of the 2 numbers

50
 ● LCM = multiply the numbers which has the greatest power from the 2
numbers even if they're not common
● GCD = multiply the numbers which has the lowest power from the 2 numbers
even if they're not common

𝑛
● Arithmetic sequence :
2
(𝑎 + 𝑏)
𝑛
𝐿*𝑅−𝑎 𝑟 −1
● Geometric sequence :
𝑟−1
= 𝑎 * 𝑟−1
𝑛+𝑛%2 2
● Sum of odd numbers : ( 2
)
𝑛
( 2 * (2 + 𝑛 − 𝑛 % 2))
● Sum of even numbers:
2

2
−𝑏± 𝑏 −4𝑎𝑐
● Quadratic Formula :
2𝑎
𝑛
● (1 + 𝑡) = ∑
𝑛

𝑘=0
() 𝑛
𝑘
𝑘
𝑡 , 𝑡 == 1 => 2
𝑛

𝑛 𝑛
● (𝑥 + 𝑦)
𝑛
=
𝑘=0
∑ ()
𝑛
𝑘 𝑥
𝑛−𝑘 𝑘
𝑦 = ∑ 𝑥𝑦
𝑘=0
𝑘 𝑛−𝑘

●
𝑛!
● NPR =
(𝑛 − 𝑟)!
𝑛!
● NCR =
(𝑛 − 𝑟)! * 𝑟!

51
 Sum of the first n odd numbers is .

Sum from 1 to n n(n+1) / 2

PERFECT NUMBERS
28

496

8128

33550336

8589869056

137438691328

2305843008139952128

2658455991569831744654692615953842176

DOT AND CROSS

Dot product: a · b = |a| × |b| × cos(θ)

Cross product: a × b = |a| |b| sin(θ) n

STARS AND BARS

The number of ways to place n indistinguishable balls into k labelled
urns is

(n+k-1)C(n) = (n+k-1)C(k-1)

53