Getting Started

INTRODUCTION TO PROGRAMMING LANGUAGES:

A program is a set of instructions that tells a computer what to do in order to come up with a solution to a particular problem. Programs are written using a programming language.A programming language is a formal language designed to communicate instructions to a computer. There are two major types of programming languages: low-level languages and high-level languages.

TYPES OF LANGUAGES:

Low-Level Languages : Low-level languages are referred to as 'low' because they are very close to how different hardware elements of a computer actually communicate with each other. Low-level languages are machine oriented and require extensive knowledge of computer hardware and its configuration. There are two categories of low-level languages: machine language and assembly language.

Machine language : or machine code, is the only language that is directly understood by the computer, and it does not need to be translated. All instructions use binary notation and are written as a string of 1s and 0s. A program instruction in machine language may look something like this:

However, binary notation is very difficult for humans to understand. This is where assembly languages come in.

An assembly language : is the first step to improve programming structure and make machine language more readable by humans. An assembly language consists of a set of symbols and letters. A translator is required to translate the assembly language to machine language called the 'assembler.' While easier than machine code, assembly languages are still pretty difficult to understand. This is why high-level languages have been developed.

High-Level Languages : A high-level language is a programming language that uses English and mathematical symbols, like +, -, % and many others, in its instructions. When using the term 'programming languages,' most people are actually referring to high-level languages. High-level languages are the languages most often used by programmers to write programs. Examples of high-level languages are C++, Fortran, Java and Python. Learning a high-level language is not unlike learning another human language - you need to learn vocabulary and grammar so you can make sentences. To learn a programming language, you need to learn commands, syntax and logic, which correspond closely to vocabulary and grammar. The code of most high-level languages is portable and the same code can run on different hardware without modification. Both machine code and assembly languages are hardware specific which means that the machine code used to run a program on one specific computer needs to be modified to run on another computer. A high-level language cannot be understood directly by a computer, and it needs to be translated into machine code. There are two ways to do this, and they are related to how the program is executed: a high-level language can be compiled or interpreted.

COMPILER VS INTERPRETER

A compiler is a computer program that translates a program written in a high-level language to the machine language of a computer.
The high-level program is referred to as 'the source code.' The compiler is used to translate source code into machine code or compiled code. This does not yet use any of the input data. When the compiled code is executed, referred to as 'running the program,' the program processes the input data to produce the desired output.
An interpreter is a computer program that directly executes instructions written in a programming language, without requiring them previously to have been compiled into a machine language program.

HOW TO START WRITING PROGRAMS?

Algorithm:
Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.
Qualities of a good algorithm
1. Input and output should be defined precisely.
2. Each step in the algorithm should be clear and unambiguous.
3. An algorithm shouldn’t include computer codes. Instead it should be written in such a way that it can be used in different programming languages. Good, logical programming is developed through good pre-code planning and organization. This is assisted by the use of pseudocode and program flowcharts.

Flowcharts:
Flowcharts are written with program flow from the top of a page to the bottom. Each command is placed in a box of the appropriate shape, and arrows are used to direct program flow.

4.This is what we use when our program has to make a decision. This is the only block that has more than one exit arrow. The rhombus symbol has one(or several) entrance points and exactly two outputs.

5.Junction flow chart symbol : You can connect two arrows with a junction

Here are examples of a short algorithm, using each flowcharts

VARIABLES

A variable is a container (storage area) used to hold data.
Each variable should be given a unique name (identifier).
int a=2;

Here a is the variable name that holds the integer value 2.
The value of a can be changed, hence the name variable.
There are certain rules for naming a variable in C++
1. Can only have alphabets, numbers and underscore.
2. Cannot begin with a number.
3. Cannot begin with an uppercase character.
4. Cannot be a keyword defined in C++ language (like int is a keyword).

FUNDAMENTAL DATATYPES IN C++ :

Data types are declarations for variables. This determines the type and size of
data associated with variables which is essential to know since different data
types occupy different size of memory.

2. float and double:
● Used to store floating-point numbers (decimals and exponentials)
● Size of float is 4 bytes and size of double is 8 bytes.
● Float is used to store upto 7 decimal digits whereas double is used to store upto 15 decimal digits.
Eg. float pi = 3.14
double distance = 24E8 // 24 x 108

3. char:
● This data type is used to store characters.
● It occupies 1 byte in memory.
● Characters in C++ are enclosed inside single quotes ͚ ͚.
● ASCII code is used to store characters in memory.
Eg͘ char ch с ͚a͖͛

4. bool
● This data type has only 2 values ʹ true and false.
● It occupies 1 byte in memory.
● True is represented as 1 and false as 0.

Eg. bool flag = false

C++ TYPE MODIFIERS

Type modifiers are used to modify the fundamental data types.

DERIVED DATATYPES:

These are the data types that are derived from fundamental (or built-in) data
types. For example, arrays, pointers, function, reference.

USER-DEFINED DATATYPES:
These are the data types that are defined by user itself.For example, class, structure, union, enumeration, etc.

1. Comments
The two slash(//) signs are used to add comments in a program. It does not have any effect on the behavior or outcome of the program. It is used to give a description of the program you’re writing.

2. #include<iostream>
#include is the pre-processor directive that is used to include files in our program. Here we are including the iostream standard file which is necessary for the declarations of basic standard input/output library in C++.

3. Using namespace std
All elements of the standard C++ library are declared within namespace. Here we are using std namespace.

4. int main()
The execution of any C++ program starts with the main function, hence it is necessary to have a main function in your program. ‘int’ is the return value of this function. (We will be studying about functions in more detail later).

5. {}
The curly brackets are used to indicate the starting and ending point of any function. Every opening bracket should have a corresponding closing Bracket.

6. Cout<< ”Hello World!\n”;
This is a C++ statement. cout represents the standard output stream in C++. It is declared in the iostream standard file within the std namespace. The text between quotations will be printed on the screen. \n will not be printed, it is used to add line break. Each statement in C++ ends with a semicolon (;)

7. return 0;
return signifies the end of a function. Here the function is main, so when we hit return 0, it exits the program. We are returning 0 because we mentioned the return type of main function as integer (int main). A zero indicates that everything went fine and a one indicates that something has gone wrong.

                                                        
// Hello world program in C++
#include<iostream>
using namespace std;
int main()
{
      cout << "Hello World!\n";
      return 0;
}
                                                    

Operator Operation Example

+ Adds two operands A+B = 15
- Subtracts right operand from left operand B-A = 5
* Multiplies two operands A*B = 50
/ Divides left operand by right operand B/A = 2
% Finds the remainder after integer division B%A = 0

Pre-incrementer : It increments the value of the operand instantly.

Post-incrementer : It stores the current value of the operand temporarily and only after that statement is completed, the value of the operand is incremented.

Pre-decrementer : It decrements the value of the operand instantly.

Post-decrementer : It stores the current value of the operand temporarily and only after that statement is completed, the value of the operand is decremented.

                                                        
int a=10;
int b;
b = a++;
cout<<a<<" "<<b<<endl;
Output : 11 10
int a=10;
int b;
b = ++a;
cout<<a<<" "<<b<<endl;
Output : 11 11
                                                    

2. Relational Operators

Relational operators define the relation between 2 entities. They give a boolean value as result i.e true or false.

Suppose : A=5 and B=10

Operator Operation Example
== Gives true if two operands are equal A==B is not true
!= Gives true if two operands are not equal A!=B is true
> Gives true if left operand is more than right operand A>B is not true
< Gives true if left operand is less than right operand A<B is true
>= Gives true if left operand is more than right operand or equal to it A>=B is not true
<= Gives true if left operand is more than right operand or equal to it A<=B is true

3. Logical Operators

Logical operators are used to connect multiple expressions or conditions together.
We have 3 basic logical operators.

Suppose : A=0 and B=1

&& AND operator. Gives true if both operands are non-zero.(A && B) is false
|| OR operator. Gives true if atleast one of the two operands are non-zero.(A || B) is true
! NOT operator. Reverse the logical state of operand !A is true

Example -

If we need to check whether a number is divisible by both 2 and 3, we will use AND operator
(num%2==0) && num(num%3==0)
If this expression gives true value then that means that num is divisible by both 2 and 3.

(num%2==0) || (num%3==0)
If this expression gives true value then that means that num is divisible by 2 or 3 or both.

Suppose : A=5(0101) and B=6(0110)

& Binary AND. Copies a bit to the result if it exists in both operands.
0101 & 0110 => 0100

| Binary OR. Copies a bit if it exists in either operand.
0101 | 0110 => 0111

^ Binary XOR. Copies the bit if it is set in one operand but not both.
0101^ 0110 => 0011

~ Binary Ones Complement. Flips the bit.
~0101 =>1010

<< Binary Left Shift. Shifts left by the number of places specified by the right operand.
4 (0100)
4<<1=1000 = 8

>> Binary Right Shift. Shifts right by the number of places specified by the right operand.
4>>1=0010 = 2

If shift operator is applied on a number N then,
x N<<a will give a result N*2^a
x N>>a will give a result N/2^a

Why are functions used?

x If some functionality is performed at multiple places in software, then rather than writing the same code, again and again, we create a function and call it everywhere. This helps reduce code redundancy. x Functions make maintenance of code easy as we have to change at one place if we make future changes to the functionality. x Functions make the code more readable and easy to understand.

The syntax for function declaration is-
return-type function_name (parameter 1, parameterϮ ...... parameter n){

//function_body
}
return-type

The return type of a function is the data type of the variable that that function returns.
For eg. if we write a function that adds 2 integers and returns their sum then the return type of this function will be ‘int’ as we will returning sum that is an integer value.
When a function does not return any value, in that case the return type of the function is ‘void’.

function_name
It is the unique name of that function. It is always recommended to declare a function before it is used.

Parameters
A function can take some parameters as inputs. These parameters are specified along with their datatypes.
For eg. if we are writing a function to add 2 integers, the parameters would be passed like – int add (int num1, int num2)

Main function:
The main function is a special function as the computer starts running the code from the beginning of the main function. Main function serves as the entry point for the program.

MODULAR ARITHMETIC

You must have stumbled across problems where you see a large number like 10^9+7 and you tend to skip these ones. After reading this section, handling these would become a cakewalk for you. Let’s start with some basics of modular arithmetic.

INTRODUCTION

Subtraction:

(a - b) % m =(a % m - b % m + m) % m

Here, m is added to make the result positive.
(6 - 8) % 5 = (6 % 5 - 8 % 5 +5) % 5
= (1 -3 + 5) % 5 = 3 % 5 = 3

__________________________________

Multiplication:

(a * b) % m = ((a % m) * (b % m)) % m
(6 * 8) % 5 = ((6 % 5) * (8 % 5)) % 5
= (1 * 3) % 5
= 3 % 5
= 3

__________________________________

Division:

Modular division is totally different from modular addition, subtraction and multiplication. It also does not exist always.

(a / b) % m is not equal to ((a % m) / (b % m)) % m

(a / b) % m = ((a % m) * (b^(-1) % m)) % m
Note: b^(-1)is the multiplicative modulo inverse of b and m.

__________________________________

Modular multiplicative inverse:

What is modular multiplicative inverse? If you have two numbers A and M, you are required to find B such it that satisfies the following equation:

(A.B)%M=1

Here B is the modular multiplicative inverse of A under modulo M.
Formally, if you have two integers A and M, B is said to be modular multiplicative inverse of A under modulo M if it satisfies the following equation:
\
A.B≡1(modM) where B is in the range [1,M-1]

Why is B in the range [1,M-1]?

Since we have B%M, the inverse must be in the range [0,M-1]. However, since 0 is invalid, the inverse must be in the range [1,M-1]. An inverse exists only when A and M are coprime i.e. GCD( A ,M )=1.

According to inclusion-exclusion principle, to count unique ways for doing a task, the number of ways to do it in one way (n1) and number of ways to do it in some other way (n2) should be added, and the number of ways that are common to both set should be subtracted.

For two finite sets A1 and A2
| A1 ∪ A2 |= |A1 |+ | A2| – |A1 ∩ A2|

Have a look at these examples:

Example 1 :

How many numbers between 10 and 100, including both, have the first digit as 3 and the last digit as 5?

Solution :

The numbers with 1st digit as 3 are from 30,31,32.…..39. So, the number of numbers with 1st digit as 3 is equal to 10. The numbers with last digit as 5 are 15,25,35…..95. Hence, the number of numbers with last digit as 5 is equal to 9.
So, is 10 + 9 = 19 the answer? No.
Because, we haven’t subtracted the common part between the two sets. We need to find the numbers who have both the first digit as 3 and the last digit as 5. Here, there’s only 1 such number, i.e. 35.
Therefore, the final answer = 10 + 9 - 1 = 18.

Example 2 :

How many numbers between 1 and 100, including both, are divisible by 3 and 7?

Solution :

Number of numbers divisible by 3 = 100 / 3 = 33.
Number of numbers divisible by 7 = 100 / 7 = 14.

Number of numbers divisible by 3 and 7 = 100 / (3 * 7) = 100 / 21 = 4.

Hence, number of numbers divisible by 3 or 7 = 33 + 14 - 4 = 43.

If there are more than two sets, the following general formula is applicable:

For a given set A of n sets A_1,A_2,....A_n, let S_nbe the number of ways to do the task :

Here, we can observe that odd number of terms are added while even number of terms are subtracted.
Actually, each subset of is considered exactly once in the formula, thus the formula for a set of n sets has 2^n components.

Problem :

Given two positive integers n and r . Count the number of integers in the interval [1,r] that are relatively prime to n (their GCD is 1).

Solution:

Let’s first find the number of integers between 1 and r that are not relatively prime with n ( i.e they share atleast one prime factor with n ).

So, the first step is to find the prime factors of n. Let the prime factors of n be p_i(i = 1...k )
How many numbers in the interval [1,r] are divisible by p_i? The answer is :

However, if we simply sum these numbers, some numbers will be summarized several times (those that share multiple pias their factors). Therefore, it is necessary to use the inclusion-exclusion principle.

We will iterate over all 2ksubsets of pis, calculate their product and add or subtract the number of multiples of their product.
Below is the C++ implementation of the above idea:

                                                        
// CPP program to count the
// number of integers in range
// 1-r that are relatively
// prime to n
#include <bits/stdc++.h>
using namespace std;
 
// function to count the
// number of integers in range
// 1-r that are relatively
// prime to n
int count (int n, int r) {

    vector<int> p; // vector to store prime factors of n

   
    // prime factorisation of n
    for (int i=2; i*i<=n; ++i)
        if (n % i == 0) {
            p.push_back (i);
            while (n % i == 0)
                n /= i;
        }
    if (n > 1)
        p.push_back (n);

    int sum = 0;
    for (int mask=1; mask<(1<<p.size()); ++mask) {
        int mult = 1,
            bits = 0;
        for (int i=0; i<(int)p.size(); ++i)
            // Check if ith bit is set in mask
            if (mask & (1<<i)) {
                ++bits;
                mult *= p[i];
            }

        int cur = r / mult;
        if (bits % 2 == 1)
            sum += cur; // if odd number of prime factors are selected
        else
            sum -= cur; // if even number of prime factors are selected

    }

    return r - sum;
}

// Driver Code
int main()
{
    int n=30;
    int r=30;
    cout << count(n, r);
    return 0;
}

//OUTPUT : 22
                                                    

PERMUTATIONS :
● Permutation: It is the different arrangements of a given number of elements taken one by one, or some, or all at a time.
● For example, if we have two elements A, B and C, then there are 6 possible permutations, ABC, ACB, BAC, BCA, CAB, CBA.

Basic Formula for permuting r items from a collection of n items is represented in mathematics by nPr. The mathematical formula for the same is:

Formula for Permutations of r elements of n elements:


Permutations with repetitions :
If we have n objects, p1 of one kind, p2 of another kind, p3 are another kind and rest are different.
Then the number of permutations for this condition are,
Permutations = n! / (p1! + p2! + p3! + …)

Circular Permutations :
Circular permutation is the total number of ways in which n distinct objects can be arranged around a fix circle. It is of two types:

Clockwise and Anticlockwise orders are different:
Permutations = (n−1)!

Clockwise and Anticlockwise orders are same.
Permutations = (n−1)!/2!

COMBINATIONS :
● Combination: It is the different selections of a given number of elements taken one by one, or some, or all at a time.
● For example, if we have two elements A and B, then there is only one way select two items, we select both of them.

Basic Formula for selecting r items from a collection of n items is represented in mathematics by nCr. The mathematical formula for the same is:

Remember in combination the order of the combination does not matter at all. It is more about the distinct items we are choosing from the set of given items (there is no repetition here in the n items as of now

Here are some useful formulas to use in combination:
● nCr = nCn-r
● nCn = nC0 = 1

As we all know by now, Probability is how likely something is about to happen.

Let’s denote an event by A, for which we need to find the probability of how likely the event is going to happen. We denote this by using P(A).
And mathematically, P(A) = Number of outcomes where A happens / Total outcomes.

Basic probability calculations

Complement of A : Complement of an event A means not A. Probability of complement event of A means the probability of all the outcomes in sample space other than the ones in A.

P(Ac) = 1 − P(A).

Union and Intersection : The probability of intersection of two events A and B is P(A∩B). When event A occurs in union with event B then the probability together is defined as P(A∪B) = P(A) + P(B) − P(A∩B) which is also known as the addition rule of probability.

Mutually exclusive : Any two events are mutually exclusive when they have non-overlapping outcomes i.e. if A and B are two mutually exclusive events then, P(A∩B) = 0. From the addition rule of probability

P(A∪B) = P(A) + P(B)

as A and B are disjoint or mutually exclusive events.

Independent : Any two events are independent of each other if one has zero effect on the other i.e. the occurrence of one event does not affect the occurrence of the other. If A and B are two independent events then, P(A∩B) = P(A) ∗ P(B).

Conditional Probability
The conditional probability of an event B is the probability that the event will occur given the knowledge that an event A has already occurred. This probability is written P(B|A), notation for the probability of B given A. In the case where events A and B are independent (where event A has no effect on the probability of event B), the conditional probability of event B given event A is simply the probability of event B, that is P(B).

If events A and B are not independent, then the probability of the intersection of A and B (the probability that both events occur) is defined by P(A and B) = P(A)P(B|A).

From this definition, the conditional probability P(B|A) is easily obtained by dividing by P(A):

Binomial Distribution

To get started first we need to learn about something called Bernoulli Trial. Bernoulli Trial is a random experiment with only two possible, mutually exclusive outcomes. And each Bernoulli Trial is independent of the other.

To better understand stuff, let’s see an example.
Suppose we toss a fair coin three times. And we need to find the probability of two heads in all the possible outcomes.

Now, we can see that the probability of getting heads is ½, and tails is also ½, for a fair coin. And here all the tosses of the coin are independent to each other. So, we may say that the single tossing of the coin is a Bernoulli Trial, with the two possible outcomes of heads and tails. Let p denote the probability of getting heads in a fair coin toss. And the other possibility of getting tails is denoted by q. We can see that, p = ½ and q = ½.

The coin is tossed three times, so we have to select two events out of three, where heads will occur. And the total events are three. So, the number of ways to select them is 3C2. And the so can denote the total probability as = 3C2 p2q

Now let’s generalise the approach to problems like these involving Bernoulli Trials.
We saw that the Bernoulli Trial involves two mutually exclusive outcomes. Now for convenience they are often labelled as, “success” and “failure”. The binomial distribution is used to obtain the probability of observing x successes in N trials, with the probability of success on a single trial denoted by p. The binomial distribution assumes that p is fixed for all trials.

GCD(Greatest Common Divisor) or HCF(Highest Common Factor) of 2 integers a and b refers to the greatest possible integer which divides both a and b.
GCD plays a very important part in solving several types of problems(both easy and difficult) which makes it a very important topic for Competitive Programming.

Algorithms to find GCD:

Brute Force Approach:
An approach is possible to start from the smaller number and iterate to 1. As soon as we find a number that divides both a and b, we can return it as the result.

Time complexity: O(min(a,b))
Space complexity: O(1)

Euclidean Algorithm:
The Euclidean Algorithm for calculating the GCD of two numbers builds on several facts:
If we subtract the smaller number from the larger number then the GCD is not changed.
i.e,gcd(a,b)=gcd(b,a-b)[considering a>=b]

If a is 0 and b is non-zero, the GCD is by definition b(or vice versa). If both are zero, then the GCD is undefined; but we can consider it to be zero, which gives us a very basic rule:
If one of the numbers is 0, then the GCD is the other number.

We can build upon these facts and further define GCD as(since the algorithm terminates as soon as one of the numbers become 0):
gcd(a,b)=gcd(b,a%b)

L.C.M:

LCM (Least Common Multiple) of 2 integers u and v refers to the smallest possible integer which is divisible by both u and v.

Important Properties:

1. gcd(a,b)=gcd(b,a)

2. gcd(a,b,c)=gcd(a,gcd(b,c))=gcd(gcd(a,b),c)=gcd(b,gcd(a,c))

3. Depending on the parity of a and b, the following cases may arise:

(a). If both the numbers are even, then we can say,

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

(b). If only one of the numbers is even, while the other is odd,

gcd(2*a,b)=gcd(a,b) [b is odd]

(c). If both numbers are odd,

gcd(a,b)=gcd(b,a−b) [provided a>=b]

Extended Euclidean Algorithm:

The Extended Euclidean Algorithm allows us to find a linear combination of a and b which results in the GCD to a and b.
i,e, a*x+b*y=gcd(a,b) [x,y are integer coefficients]

e.g, a=15, b=35

Therefore,
gcd(a,b)=5
x=-2
y=1

Since, 15*(-2)+35*1=5

Another important topic, Linear Diophantine Equations, will also build upon this algorithm.

Algorithm:

The key factor in understanding the algorithm is figuring out how the coefficients (x,y) change during the change from the function call of gcd(a,b) to gcd(b,a%b) [i.e, following the recursive implementation].

Let us assume we have the coefficients (x1,y1) for (b,a%b);

∴ b*x1+(a%b)*y1=gcd(b,a%b)........(i)

We finally want to find the pair (x,y) for (a,b);

∴ a*x+b*y=gcd(a,b)........(ii)

Again, we know from the rules of modulus:

a%b=a-floor(a/b)*b........(iii)

[floor() function represents the mathematical floor function]

Therefore from equations (i),(ii) and (iii), we can say:

x=y1

y=x1-y1*floor(a/b)

                                                        
//Recursive implementation
int extended_euclid_recursive(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int gcd = extended_euclid_recursive(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return gcd;
}

//Iterative implementation
int extended_euclid_iterative(int a, int b, int& x, int& y) {
    x = 1, y = 0;
    int x1 = 0, y1 = 1, a1 = a, b1 = b;
    while (b1) {
        int q = a1 / b1;
        tie(x, x1) = make_tuple(x1, x - q * x1);
        tie(y, y1) = make_tuple(y1, y - q * y1);
        tie(a1, b1) = make_tuple(b1, a1 - q * b1);
    }
    return a1;
}
                                                    

What is Sieve:

Sieve of Eratosthenes is an algorithm for finding all the prime numbers in a segment in range 1 to n in
0(n log(log n)) operations

Native approach:

USING SIEVE:

In the sieve algorithm, we create an integer array of length n+1(for numbers from 1 to n) and mark all of them as prime. Then we iterate from 2 till square root of n. We mark all proper multiples of 2 (since 2 is the smallest prime number) as composite. A proper multiple of a number num is a number greater than num and divisible by num. Then we find the next number that hasn't been marked as composite, in this case, it is 3. This means 3 is prime, and we mark all proper multiples of 3 as composite and we continue this procedure.

For n=50, this is the list of primes we are going to get

                                                        
#include <bits/stdc++.h> 
using namespace std; 
int main() 
{ 
	int n;
	cin>>n;
	vector<int> prime(n+1, 1);
	prime[0] = prime[1] = 0;
	for (int i = 2; i * i <= n; i++) {
    	if (prime[i]==1) {
        	for (int j = i * i; j <= n; j += i)
            	prime[j] = 0;
    	}
	}
	for(int i=1;i<=n;i++)if(prime[i]==1)cout<<i<<endl;
}
                                                    

The time complexity of the above code is 0(n*log(log n))

In the above code, we can reduce the number of operations performed by the algorithm by stopping checking for even numbers as all even numbers (except 2) are composite numbers for we can check for odd numbers only.

                                                        
#include <bits/stdc++.h> 
using namespace std; 
int main() 
{ 
	int n;
	cin>>n;
	vector<int> prime(n+1, 1);
	prime[0] = prime[1] = 0;
	for (int i = 3; i * i <= n; i+=2) {
    	if (prime[i]==1) {
        	for (int j = i * i; j <= n; j += i)
            	prime[j] = 0;
    	}
	}
	if(n>=2)
	cout<<2<<endl;//as 2 is a prime number
	for(int i=3;i<=n;i+=2)if(prime[i]==1)cout<<i<<endl;
}
                                                    

                                                        
#include<bits/stdc++.h>
using namespace std;
vector<int>ar(100000,0);
void sieve(int maxn)
{
	for(int i=0;i<=maxn;i++)ar[i]=i;
	for(int i=2;i*i<=maxn;i++)
	{
		if(ar[i]==i)
		{
			for(int j=i*i;j<=maxn;j+=i)
				ar[j]=i;}
	}
}
int main()
{	sieve(100000);
	int t;
	cin>>t;
	while(t--)
	{	int n;
		cin>>n;
		while(n>=1)
		{	cout<<ar[n]<<endl;
			if(n==1)break;
			n/=ar[n];
		}
	}
}
                                                    

SEGMENTED SIEVE

The idea of a segmented sieve is to divide the range [0..n-1] in different segments and compute primes in all segments one by one. This algorithm first uses Simple Sieve to find primes smaller than or equal to √(n). Below are steps used in Segmented Sieve.

1. Use Simple Sieve to find all primes up to the square root of ‘n’ and store these primes in an array “prime[]”. Store the found primes in an array ‘prime[]’.

2. we need to find all prime numbers in a range [L, R] of small size (e.g., R−L+1≈1e7), where R can be very large (e.g.10^12)

To solve such a problem, we can use the idea of the Segmented sieve. We pre-generate all prime numbers up to sqrt(R) and use those primes to mark all composite numbers in the segment [L, R].

                                                        
vector<bool> segmentedSieve(long long L, long long R) { // generate all primes up to sqrt(R) 
long long lim = sqrt(R); 
vector<bool> mark(lim + 1, false); 
vector<long long> primes; 
for (long long i = 2; i <= lim; ++i) { 
if (!mark[i]) { 
primes.emplace_back(i); 
for (long long j = i * i; j <= lim; j += i) 
mark[j] = true; 
} 
} 
vector<bool> isPrime(R - L + 1, true); 
for (long long i : primes) 
for (long long j = max(i * i, (L + i - 1) / i * i); j <= R; j += i) 
isPrime[j - L] = false; 
if (L == 1) 
isPrime[0] = false; 
return isPrime; 
}

//Time complexity of this approach is O((R-L+1)loglog(R)+sqrt(R)loglog(sqrt(R)))
                                                    

Linear Diophantine Equations

Introduction:

A General Diophantine equation is a polynomial equation, having two(or more) integral variables i.e. if a solution of the equation exists, it possesses integral values.
A linear Diophantine equation is a Diophantine equation of degree 1 i.e. each integral variable in the equation is either of degree 0 or degree 1.

General form:

A Linear Diophantine Equation(in two variables) is an equation of the general form:

ax + by = c

Where a,b,c are integral constants and x,y are integral variables.

Homogeneous Linear Diophantine equation:

A Homogeneous Linear Diophantine Equation(in two variables) is an equation of the general form:

ax + by = 0

Where a,b are integral constants and x,y are the integral variables.
By looking at the equation we can easily observe that x=0 and y=0 is a solution to the equation. This is called the Trivial solution.
Though more solutions can exist for the same.

Condition for the solution to exist:

For a linear diophantine equation, the integral solution exists if and only if:

c%gcd(a,b)=0

i.e. c must be divisible by the greatest common divisor of a and b. This is because

Let, a = gcd(a,b).A, where A is an integral divisor of a. Similarly, b = gcd(a,b).B.
Therefore the Linear Diophantine equation can be written as:

gcd(a,b).A + gcd(a,b).B = c
gcd(a,b).(A + B) = c

This means that c must be a multiple of gcd(a,b).
For the Homogeneous Linear Diophantine equation, a solution always exists i.e. the trivial solution.This is because c=0, and we know 0 is divisible by every integer.

Finding a solution:
A solution can easily be found using the Extended Euclidean algorithm.
.
ax1 + by1 = gcd(a,b)
a.x1.c + by1.c = gcd(a,b).c (multiplying both sides by c)
a.x1.{c/gcd(a,b)} + by1.{c/gcd(a,b)} = c
a.{x1.(c/gcd(a,b))} + b.{y1.(c/gcd(a,b))} = c ….. (1)

Now, by comparing the equation (1) with the general Linear Diophantine equation we get:

x0 = x1 . c/gcd(a,b)
y0 = y1 . c/gcd(a,b)

Where x0 and y0 is a solution of the Linear Diophantine equation.

Implementation:
Program to find a solution of a given Linear Diophantine equation.

                                                        
#include<bits/stdc++.h>
using namespace std;
// function to find the gcd of a,b and coefficient x,y
//using Extended Euclidean Algorithm
int extended_gcd(int a, int b, int &x, int &y)
{
	if(a == 0)// base case
	{
		x = 0;
		y = 1;
		return b;// here b will be the gcd.
	}
	int x1, y1;
	int g = extended_gcd(b%a, a, x1, y1);
	x = y1 - (b/a) * x1;
	y = x1;
	return g;
}
// function to find a solution of the Diophantine equation if any
int one_solution(int a, int b, int c, int &x, int &y)
{
   int g = extended_gcd(a, b, x, y);
   if(c%g == 0) // condition for a solution to exist
   {
   	  //solution to the Diophantine equation
   	  x = x * c/g; 
   	  y = y * c/g;
   	  return 1;  // Atleast 1 solution exist
   } 
   return 0;   // no solution exists
}

int main()
{
   int a,b,c,x,y;
   cin>>a>>b>>c;
   if(one_solution(a,b,c,x,y))// if solution exists
   {
   	 cout<< "Solution are: "
   	 cout<<x<< " "<<y;
   }
   else// if no solution exists
   {
   	cout<< "Solution does not Exist";
   }
}
                                                    

Time Complexity - O(log(max(a,b)))
Auxiliary Space - O(1)

Finding all solutions:

Let, C0 be any arbitrary integer.
Add and subtract {C0.a.b/gcd(a,b)} in the general Linear Diophantine equation we get,

a.x0 + b.y0 + C0.a.b/gcd(a,b) - C0.a.b/gcd(a,b) = c
(Where x0 and y0 is a solution of the Linear Diophantine)

a.x0 + C0.a.b/gcd(a,b)+ b.y0 - C0.a.b/gcd(a,b) = c
a.(x0 + C0.b/gcd(a,b)) + b.(y0 - C0.a/gcd(a,b)) = c ….. (2)

Comparing equation (2) with general equation of Linear Diophantine equation
we get,

x = x0 + C0.b/gcd(a,b)
y = y0 - C0.a/gcd(a,b)

Where x,y are the solutions of the Linear Diophantine equation.

Chinese Remainder Theorem

Introduction:
Given set of n equations:

x % q[1] = r[1] or x ≡ r[1] (mod q[1])

x % q[2] = r[2]

x % q[3] = r[3]
.
.
.
x % q[n] = r[n]

Where, q[1], q[2]... q[n] are pairwise coprime positive integers i.e, for any 2 numbers q[i] and q[j] (i≠j)

GCD(q[i] , q[j]) = 1

And r[1].. r[n] are remainders when x is divided by q[1]... q[n] respectively .So, according to the Chinese Remainder theorem, there always exists a solution of a given set of equations and the solution is always unique modulo N, where

N = q[1].q[2]...q[n]

Finding solution:

Assume, C0 be a solution to the set of equations i.e C0 satisfies each and every equation belonging to the set. Then Xi = C0 ± K is also a solution to the set of equations if

K = LCM(q[1],q[2],q[3]....q[n]

LCM denotes the least common multiple of q[1] ,q[2]... q[n].
But ,we know that q[1] ,q[2]...q[n] are pairwise coprime therefore,

LCM(q[1],q[2]...q[n]) = q[1].q[2].q[3]...q[n]

Therefore, positive solutions to the set of equations are

Xi = C0 + K

Where C0 is the minimum positive solution that exists. So to find the solutions of the given set of equations we just need to find the minimum positive solution that exists.

Finding minimum positive solution:

Brute Force Approach:

A simple solution to find the minimum positive solution is to iterate from 1 till we find first value C0 such that all n equations are satisfied.

Implementation: function to find minimum positive solution.

                                                        
int Find_x(int q[] ,int r[] ,int n)
{
    int x=1;// initializing minimum positive solution
    bool flag;
    while(1)// we iterate till we get a solution
    {
        flag=true; 
        for(int i=0;i<n;i++)
        {
           if(x % q[i] == r[i] )//check if x gives remainder r[i] when divided by q[i]
             continue;
           flag=false;// if remainder is not r[i], this x cannot be the answer 
           break; 
        }
        if(flag) // if x satisfies all n equations ,then we have found the answer.
          break;
        x++; // check for further values
    }
    return x;
}
                                                    

Efficient Approach:

The general solution of the set of equation looks like

Xi = r[1].y[1].inv[1] + r[2].y[2].inv[2] . . . . . r[n].y[n].inv[n] .... (1)

Where,
y[1] = q[2].q[3].q[4]....q[n] or y[1] = N/q[1]

y[2] = q[1].q[3].q[4]....q[n]
.
.
.
y[n] = q[1].q[2].q[3].....q[n-1]

and,

inv[1] = y[1]-1 mod q[1]

inv[2] = y[2]-1 mod q[2]
.
.
.
inv[n] = y[n]-1 mod q[n]

We, know that the Chinese Remainder theorem states that there always exists a solution and this solution is always unique modulo N.So, to find the minimum positive solution we take (Xi mod N) where N = q[1].q[2]....q[n]. Therefore

x = Xi %N or

x = (r[1].y[1].inv[1] + r[2].y[2].inv[2] . . . . . r[n].y[n].inv[n]) % N …. (2)

Implementation: function to find minimum positive solution.

                                                        
// function to find gcd and coefficients using Extended Euclidean Algorithm
int Extended_gcd(int a ,int b, int &x, int &y)
{
    if(a==0)
    {
        x = 0;
        y = 1;
        return b;
    }
    int x1 ,y1;
    int g = Extended_gcd(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return g;
}
//function to find inverse of val w.r.t m
int inv(int val ,int m)
{
    int x ,y;
    int g = Extended_gcd(val ,m ,x ,y);
    if(x < 0)
        x = (x % m + m) % m;
    return x;
}
int Find_x(int q[] ,int r[] ,int n) //function to find minimum positive solution
{
    int x=0 ,N=1;
    for(int i=0;i<n;i++)
        N *= q[i]; // compute N = q[0].q[1]..q[n-1] 
    for(int i=0;i<n;i++)
    {
       int y = N / q[i];
       x = ( x + r[i] * y * inv(y ,q[i]) ) % N; //computing x according to equation 2
    }
    return x;
}
                                                    

FERMAT’S LITTLE THEOREM

Fermat’s little theorem states that if p is a prime number, then for any integer a, the number ap – a is an integer multiple of p.

ap ≡ a (mod p), where p is prime.

If a is not divisible by p, Fermat’s little theorem is equivalent to the statement that ap-1 -1 is an integer multiple of p.

ap - 1 ≡ 1 (mod p)

1. Applications of Fermat’s little theorem

Modular multiplicative Inverse

If we know p is prime, then we can also use Fermats’s little theorem to find the inverse.
ap-1 ≡ 1 (mod p)

If we multiply both sides with a-1, we get
a-1 ≡ a p-2 (mod p)

                                                        
// C++ program to find modular multiplicative inverse 
//using fermat's little theorem.
#include <bits/stdc++.h> 
using namespace std; 

// Modular Exponentiation to compute x^y under modulo p
int power(int x, unsigned int y, unsigned int p) 
{ 
    if (y == 0) 
        return 1; 
    int res = power(x, y / 2, p) % p; 
    res = (res * res) % p; 

    return (y % 2 == 0) ? res : (x * res) % p; 
} 

// Function to find modular inverse of a under modulo p 
void modInverse(int a, int p) 
{ 
    if (__gcd(a, p) != 1) 
        cout << "Inverse doesn't exist"; 
    else { 
        // If a and p are relatively prime, then 
        // modulo inverse is a^(p-2) mode p 
        cout << "Modular multiplicative inverse is "
            << power(a, p - 2, p); 
    } 
} 

// Driver Program 
int main() 
{ 
    int a = 3, p = 11; 
    modInverse(a, p); 
    return 0; 
}
                                                    

2. Primality Test

In Fermat Primality Testing, k random integers are selected as the value of a (where all k integers follow gcd(a,k) = 1). If the statement of Fermat's Little Theorem is accepted for all these k values of a for a given number N, then N is said as a probable prime.

                                                        
// C++ program to check if N is prime.
#include <bits/stdc++.h>
using namespace std;

/* Iterative Function to calculate (a^n)%p in O(logy) */
int power(int a, unsigned int n, int p)
{
    int res = 1; // Initialize result
    a = a % p; // Update 'a' if 'a' >= p

    while (n > 0)
    {
        // If n is odd, multiply 'a' with result
        if (n & 1)
            res = (res*a) % p;

        // n must be even now
        n = n>>1; // n = n/2
        a = (a*a) % p;
    }
    return res;
}

// If n is prime, then always returns true, If n is
// composite then returns false with high probability
// Higher value of k increases probability of correct
// result.
bool isPrime(unsigned int n, int k)
{
    // Corner cases
    if (n <= 1 || n == 4) return false;
    if (n <= 3) return true;

    // Try k times
    while (k>0)
    {
        // Pick a random number in [2..n-2]  
        // Above corner cases make sure that n > 4
        int a = 2 + rand()%(n-4); 

        // Checking if a and n are co-prime
        if (__gcd((int)n, a) != 1)
            return false;

        // Fermat's little theorem
        if (power(a, n-1, n) != 1)
            return false;

        k--;
    }

    return true;
}

// Driver Program to test above function
int main()
{
    int k = 3;
    isPrime(11, k)? cout << " true\n": cout << " false\n";
    isPrime(15, k)? cout << " true\n": cout << " false\n";
    return 0;
}
                                                    

Introduction to Bits

We usually work with data types such as int, char, float, etc., or even data structures( i.e generally on bytes level) but sometimes programmers need to work at bit level for various purposes such as encryption, data compression, etc.
Apart from that operations on bits are time efficient and are used for optimizing programs.

Bitwise Operators

There are different operators that work on bits and are used for optimizing programs in terms of time.

Unary Operators

1. NOT (!) : Bitwise NOT is an unary operator that flips the bits of the number i.e., if the bit is 0, it will change it to 1 and vice versa.It gives the one’s complement of a number.
Example: - N = 5 = (101)2
~N = ~5 = ~(101)2 = (010)2 = 2

Binary Operators

1. AND (&) : Bitwise AND operates on two equal-length bit patterns. If both bits at the ith position of the bit patterns are 1, the bit in the resulting bit pattern is 1, otherwise 0.
Example:-
00001100 = (12)10
& 00011001 = (25)10
_________
00001000 = (8)10

2. OR ( | ) : Bitwise OR also operates on two equal-length bit patterns. If both bits at the ith position of the bit patterns are 0, the bit in the resulting bit pattern is 0, otherwise 1.
Example:-
00001100 = (12)10
| 00011001 = (25)10
_________
00011101 = (29)10

3. XOR ( ^ ) : Bitwise XOR also operates on two equal-length bit patterns. If both bits in the ith position of the bit patterns are 0 or 1, the bit in the resulting bit pattern is 0, otherwise 1.
Example:-
00001100 = (12)10
^ 00011001 = (25)10
_________
00010101 = (21)10

Basics Operations on Bits

Tricks with Bits

1. x ^ ( x & (x-1)) : Returns the rightmost 1 in binary representation of x.

(x & (x - 1)) will have all the bits equal to the x except for the rightmost 1 in x. So if we do bitwise XOR of x and (x & (x-1)), it will simply return the rightmost 1. Let’s see an Example:-
x = 10 = (1010)2 `
x & (x-1) = (1010)2 & (1001)2 = (1000)2
x ^ (x & (x-1)) = (1010)2 ^ (1000)2 = (0010)2

2. x & (-x) : Returns the rightmost 1 in binary representation of x

(-x) is the two’s complement of x. (-x) will be equal to one’s complement of x plus 1.
Therefore (-x) will have all the bits flipped that are on the left of the rightmost 1 in x. So x & (-x) will return rightmost 1.

Example:-
x = 10 = (1010)2
(-x) = -10 = (0110)2
x & (-x) = (1010)2 & (0110)2 = (0010)2

3. x | (1 << n) : Returns the number x with the nth bit set.

(1 << n) will return a number with only nth bit set. So if we OR it with x it will set the nth bit of x.
x = 10 = (1010)2 n = 2
1 << n = (0100)2
x | (1 << n) = (1010)2 | (0100)2 = (1110)2

In the programming world, we often need to find out whether an element is present in the given data set or not.
Formally, we have an array and we are asked to find the index of an element ‘k’ in the array. And if it is not present, inform that.

The simplest way to answer this question is Linear Search.
In linear search, we traverse the entire array and check each element one by one.

Binary Search is the most useful search algorithm. It has many applications too, mainly due to its logarithmic time complexity. For example, if there are 109 numbers and you want to search for a particular element, using binary search you can do this task in just around 32 steps!
The only thing that one must keep in mind is that binary search works only on sorted set of elements.

The main idea of the algorithm can be explained as follows:
Let we have a sorted array of n elements, and we want to search for k.
Let's compare k with the middle element of the array.
If k is bigger, it must lie on the right side of the middle element.
Else if it is smaller, it must lie on the left side of the middle element.
This means, in one step, we reduced the “search space” by half. We can continue this halfing-process recursively until we find the required element. That's it.
Remember, we could do this because the elements were sorted.

Here, in each step we half the length of the interval. In the worst case, we continue the process till the length becomes 1. Hence, the time complexity of binary search is O(log2 N), where N is the initial length of interval.

Sometimes a situation arises where we can’t calculate the answer directly from given data due to too many possibilities, but we can have a way to know if a number is possible as a solution or not. i.e. we ask a number and get a feedback as “yes” or “no”. And using the feedback we shorten our “search space”, and continue the search for our answer.
This technique is known as Binary Search the Answer.

Lower Bound: Lower bound of a number in a sorted array is the first element in that array that is not smaller than the given number. STL has a useful inbuilt function
lower_bound(start_ptr, end_ptr, num) to carry out this task. It returns the pointer pointing to the required element. As this function uses binary search in its working, its time complexity is O(log n).
Upper Bound: Upper bound of a number in a sorted array is the number that is just higher than the given number. STL provides an inbuilt function for this too:
upper_bound(start_ptr, end_ptr, num). Similar to lower_bound(), this function also returns the pointer pointing to the required element, and its time complexity is O(log n).
Note: These functions return the end pointer if the required element is not present in the array.
Note: If there are multiple occurrences of the required element in the array, these functions return the pointer to the first occurrence of it.

Just like the Binary search algorithm, Ternary search is also a divide and conquer algorithm. And the array needs to be sorted to perform ternary search.The only difference is, instead of dividing the segment into two parts, here we divide it into three parts, and find in which part our key element lies.

                                                        
int ternary_search(int l,int r, int k)
{
    if(r>=l)
    {
        int mid1 = l + (r-l)/3;
        int mid2 = r -  (r-l)/3;
        if(ar[mid1] == k)
            return mid1;
        if(ar[mid2] == k)
            return mid2;
        if(k<ar[mid1])		 // First part
            return ternary_search(l,mid1-1,k);
        else if(k>ar[mid2])	// Third part
            return ternary_search(mid2+1,r,k);
        else  			// Second part
            return ternary_search(mid1+1,mid2-1,k);
    }
    return -1;
}
                                                    

The idea behind this algorithm is pretty simple. We divide the array into two parts: sorted and unsorted. The left part is a sorted subarray and the right part is an unsorted subarray. Initially, the sorted subarray is empty and the unsorted array is the complete given array.
We perform the steps given below until the unsorted subarray becomes empty:
(Assuming we want to sort it in non-decreasing order)
Pick the minimum element from the unsorted subarray.
Swap it with the leftmost element of the unsorted subarray.
Now the leftmost element of the unsorted subarray becomes a part (rightmost) of the sorted subarray and will not be a part of the unsorted subarray.

Bubble sort, sometimes referred to as sinking sort, is based on the idea of repeatedly comparing pairs of adjacent elements and then swapping their positions if they exist in the wrong order. In one iteration of the algorithm the smallest/largest element will result at its final place at end/beginning of an array. So in some sense movement of an element in an array during one iteration of bubble sort algorithm is similar to the movement of an air bubble that raises up in the water, hence the name.

Lets try to understand the algorithm with an example: Arr[ ] = {9,2,7,5}.
At first our array looks like this:
{9,2,7,5}
In the first step, we compare the first 2 elements, 2 and 9, As 9>2 , we swap them.
{2,9,7,5}
Next, we compare 9 and 7 and similarly swap them.
{2,7,9,5}
Again, we compare 9 and 5 and swap them.
{2,7,5,9}
Now as we have reached the end of the array, the second iteration starts.
In the first step, we compare 2 and 7. As 7>2, we need not swap them.
{2,7,5,9}
In the Next step, we compare 7 and 5 and swap them.
{2,5,7,9}

In this way, the process continues.
In this example, there will not be any more swaps as the array is sorted after the steps shown above.

Insertion sort is the sorting mechanism where the sorted array is built having one item at a time. The array elements are compared with each other sequentially and then arranged simultaneously in some particular order. The analogy can be understood from the style we arrange a deck of cards in our hand. This sort works on the principle of inserting an element at a particular position, hence the name Insertion Sort.

To sort an array of size n in ascending order:
1: Iterate from arr[1] to arr[n] over the array.
2: Compare the current element (key) to its predecessor.
3: If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.
Lets try to understand the algorithm with an example: Arr[ ] = {69, 55, 2, 22, 1}.

At first our array looks like this:
{69,55,2,22,1}
Let us loop from index 1 to index 4

For index=1, Since 55 is smaller than 69, move 69 and insert 55 before 69
{55,69,2,22,1}
For index=2, 2 is smaller than both 55 and 69. So shift 55 and 69 to right and insert 2 before them.
{2,55,69,22,1}
For index=3, 22 is smaller than both 55 and 69. So shift 55 and 69 to right and insert 22 before them.
{2,22,55,69,1}
For index=4, 22 is smaller than both 55 and 69. So shift 55 and 69 to right and insert 22 before them.
{1,2,22,55,69}

Merge sort algorithm works on the principle of Divide and Conquer.
It is one of the most efficient sorting algorithms. It is one of the most respected algorithms due to many reasons. Also, it is a classic example of divide and conquer technique.

The main idea behind the algorithm is to divide the given array into two parts recursively until it becomes a single element, trivial to sort. The most important part of the algorithm is to merge two sorted arrays into a single array.
Let us first understand how to merge two sorted arrays:
1.We will take two pointers which will point to the starting of the two arrays initially.
2.Then we will take a new, empty auxiliary array with length equal to the sum of lengths of the two sorted arrays.
3.Now, we will compare the elements pointed by our two pointers. And insert the smaller element into the new array and increment that pointer (Assuming we are sorting in non-decreasing order).
4.We continue this process till any of the pointers reach the end of the respective array. Then we insert the remaining elements of the other array in the new array one by one.
(Have a look at the merge function in the following implementation of merge sort)

Now let's understand the merge sort algorithm:
>First of all, we call the mergesort function on the first half and second half of the array.
>Now the two halves are sorted, the only thing to do is to merge them. So we call the merge function.
>We do this process recursively, with the base case that, when the array consists of just one element, it is already sorted and we can return the function call from there.
It's time for an example:
>Let's take an array, Arr[ ]={14,7,3,12,9,11,6,2}.
>Following figure shows each step of dividing and merging the array.
>In the figure, segment (p to q) is the first part and segment (q+1 to r) is the second part of the array at each step.

Competitive programmers love C++, STL is one of the reasons. STL i.e. Standard Template Library provides us many in-built useful functions, sort() is one of them. In other words, sort() is one of the most useful STL functions.
Basically, sort() sorts the elements in a range, with time complexity O(N log2N) where N is the length of that range.
It generally takes two parameters , the first one being the point of the array/vector from where the sorting needs to begin and the second parameter being the point up to which we want the array/vector to get sorted. The third parameter is optional and can be used when we want to sort according to some custom rule. By default it sorts in non-decreasing order.

The third parameter of sort() function, called as the comparator, acts as an operator to compare two elements.
If we did not provide it sort() uses “<” as an operator.

This “comparator” function returns a value; convertible to bool, which tells the sort() function whether the passed “first” argument should be placed before the passed “second” argument or not.

Hash Function:
Hash function is a function that takes a key as an input and converts it to another small practical integer value which is then used as an index in the hash table.
Key -> Hash Function -> Address in hash table

There are various methods to generate/make hash functions, but the trivial and most often used method is, Division Method (Take modulo of given key with another number and use this as index in hash table )

For a good hash function we should consider that it is efficiently computed and the various index positions in the table are equally likely for each key.

Similar to the direct access table, it is an array to store pointers/data corresponding to the index location generated for a key by hash function.
Hash table is different from a direct access table for the original range of key as the hash function reduces the range of the original key to a small practical range.

Why to use Hashing ?
In various real life situations we deal with very large values and their associated data for which we need to do insertion,deletion and searching operations.

To search for a given element we have two techniques:
1.Linear Search - Time complexity O(n)
2.Binary Search - Time complexity O(log n)

For storing data, we can use:

1.Array: If we use array and store information then insertion, deletion and searching will have time complexity of O(n).
2.Sorted Array: Searching can be done in O(log n) but we need to sort after each insertion or deletion which increases the time complexity of O(n) to O(n*log n) or more.
3.LinkedList: Insertion, deletion and searching can be done in O(n) time.
4.AVL Tree: Insertion, deletion and searching can be done in O(log2n) time.
5.Direct address table: We can create a list of the size of maximum value we will be dealing with and then use value as index to store data in the array or list, this will make insertion, deletion and searching in O(1) constant time. But it will cost us in terms of memory as to store x data pointers with highest value h (1<= h <= 1050) ,space complexity is of order O(x*h), which is not a feasible solution.

So from the above discussion it can be noticed for such cases, best case for searching is O(log n) and worst case is O(n).
We use Hashing to get the best and average case to be done in O(1) and in the worst case O(n).

Performance of Hash Function:
The performance of hashing can be evaluated under the assumption that each key is equally likely to be hashed to any slot of the table.
n = Number of keys to be inserted in the hash table
m = Number of slots in the hash table

Load factor α = n/m

Collision in Hashing:
Using a hash function we get a smaller number for a big key, so there might be a possibility that after processing different keys through a hash function we get the same value. This situation where a newly inserted key maps to an already occupied slot in the hash table is called collision.
Hash(key1) = value
Hash(key2) = value
To handle such situations we use some collision handling technique.
We can use following collision handling technique:
Linear probing
Quadratic probing
Chaining
Double hashing

1. Linear Probing:

We have a hash table of size, more than the number of values to be stored.
In linear probing if there is something stored already at the index v in the hash table, we then check for the (v + 1)%Table_Size th index and so on (increment index by 1) till we find an empty slot in the hash table.
For example, You have a hash function x % 8 and you need to insert values 80,86,88,93,91,102,105,121:

2. Quadratic Probing:

We have a hash table of size L, more than the number of values to be stored.
In quadratic probing if there is something stored already at the index v in the hash table, we then check for the (v + 1*1) %Table_Size index and so on till we find an empty slot in the hash table.
Pattern for finding empty slot:
(v + 1*1) %Table_Size → (v + 2*2) %Table_Size → …... → (v + i*i) %Table_Size

Performance of Linear and Quadratic Probing:
Load factor α = n/m ( < 1 )
Search, Insert and Delete take (1/(1 - α)) time

Problems faced during Linear and Quadratic Probing:
Can be used only when the number of frequencies and keys are known.
A slot can be used even if an input key doesn’t map to it using the hash function.
After some collision resolution it starts taking time to find a free slot or to search an element.

3. Chaining:

In the chaining method of Collision resolution we make each cell of the hash table point to a linked list of records that have the same hash function value. Chaining is simple, but requires additional memory outside the table.
Some points to remember:
This way the Hash table never fills up and we can remove the factor that we need to know the number of keys and frequencies as we have to know in linear and quadratic probing.
As some space in hash table are never used, there is wastage of space.
If the chain becomes long then search time can become O(n) in the worst case.

C++ program to use chaining as Collision resolution method
Performance of Chaining:
If, Load factor α = n/m
Expected time to search = O(1 + α)
Expected time to delete = O(1 + α)
Time complexity of search insert and delete is O(1) if α is O(1)

For example, You have a hash function x % 8 and you need to insert values 80,86,88,93,91,102,105,121:

4. Double Hashing:

Double hashing is another collision handling technique in which we apply another hash function to key when a collision occurs.
Let, hash1() and hash2() are the hashing functions.
If using first hashing function there is a collision, we do double hashing using (hash1(key) + i * hash2(key)) % Table_Size, we increment the value of i, till collision is resolved.
Choose such a hash2() function which never evaluates value to zero and also probe all maximum possible indexes in the hash table.

A linked list is a data structure in which the objects are arranged in a linear order. Unlike an array, though, in which the linear order is determined by the array indices, the order in a linked list is determined by a pointer in each object. Linked lists provide a simple, flexible representation for dynamic sets.

Linked list data set :

General Linked list :

Singly Linked List
Singly-linked lists contain nodes which have a data field as well as 'next' field, which points to the next node in line of nodes. Operations that can be performed on singly-linked lists include insertion, deletion and traversal.
A singly linked list whose nodes contain two fields: an integer value and a link to the next node

The following code demonstrates how to add a new node with data "value" to the end of a singly linked list:

                                                        
node addNode(node head, int value) {
    node temp, p;  // declare two nodes temp and p
    temp = createNode(); // assume createNode creates a new node with data = 0 and next
			       //  pointing to NULL
    temp->data = value;   // add element's value to data part of node
    if (head == NULL)
   {
        head = temp;     // when linked list is empty
    }
    else {
        p = head; // assign head to p 
        while (p->next != NULL) {
            p = p->next; // traverse the list until p is the last node. The last node always points
			// to NULL
        }
        p->next = temp; // Point the previous last node to the new node created.
    }
    return head;
}
                                                    

Stacks and Queues are dynamic sets in which the element can be added or removed by some predefined operations.

In a stack, it implements LAST IN, FIRST OUT (LIFO). It means whichever element is added at the last will be the one to be removed first.

In a queue, it implements FIRST IN, FIRST OUT (FIFO). It means whichever element is added first will be removed first.

There are several ways to implement stacks and queues on a computer.

Stacks
The insert operation on a stack is often called PUSH, and the delete operation is called POP. These names are allusions to physical stacks, such as the spring-loaded stacks of plates used in cafeterias. The order in which plates are popped from the stack is the reverse of the order in which they were pushed onto the stack since only the top plate is accessible. Below is a visual of how stack data structures work, by inserting and removing elements, which expresses the LIFO property. Let’s define a stack named S.

Stack Definition in c++ : stack < <data type> > <stack name>;

Here we are defining stack if Integer Data Type :

                                                        
stack< int > S
                                                    

Push Operations :

Pop Operations :

Other Basic operations of Stack :

1 . empty() : checks if the stack is empty.
2. size() : returns the count of elements present in the stack.
3. top() : return the topmost element present in the stack.

When the stack contains no elements, it is said to be empty. The stack can be tested for emptiness by the query operation empty(). If an empty stack is popped, we call it
stack underflows, which is normally an error. And if the count of elements exceeds the maximum limit, we call it stack overflow. We do not worry about stack overflow in the code implementations shown below.

Code Implementations with various operations :

Queues

We call the insert operation on a queue as enque, and we call the delete operation dequeue(It is the same as pop in the stack) . The FIFO property of a queue causes it to operate as a line of people in the registrar's office. The queue has a head and a tail. When an element is enqueued, it takes its place at the tail of the queue, just as a newly arriving student takes a place at the end of the line. The element dequeued is always the one at the head of the queue, like the student at the head of the line who has waited the longest.
Below is a visual of how queue data structure works, by inserting and removing elements, which expresses the FIFO property. Let’s define a queue named q.

Queue definition : queue < <data type> > <queue name>;

Here we are defining queue of Integer Data Type :

                                                        
queue< int > q
                                                    

Push and Pop Operation :

Other Basic Operations in Queue :

1. size() : returns the number of elements in the queue.
2. empty() : checks if the queue is empty.
3. front() : returns the element in front of the queue
4. back() : returns the element at the back of the queue.

Code implementation with various operations :

Binary Tree Representation
Each node contains three components :
1. Pointer to left child
2. Pointer to right child
3. Data element
Code :-

                                                        
struct node {
   int data;   
   struct node *left;
struct node *right;
};
                                                    

Types of Binary Trees

1.Full Binary Tree : A full binary tree is A binary tree in which all the nodes have either zero or two children.

2. Complete Binary tree : A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

3.Perfect Binary tree : A perfect binary tree is a binary tree in which every internal node has exactly two child nodes and all the leaf nodes are at the same level

Binary tree traversals:-
A binary Tree can be traversed in two ways:
1. Breadth First Traversal (Or Level Order Traversal)
2. Depth First Traversals
A.Inorder Traversal (Left-Root-Right)
B.Preorder Traversal (Root-Left-Right)
C.Postorder Traversal (Left-Right-Root)

Breadth First Traversal
In BFS, For each node, first the node is visited and then it’s child nodes are put in a queue.This process is repeated till the queue becomes empty.

Code :

                                                        
void LevelOrder(Node *root)
{
    // Base Case
    if (root == NULL)  return;
 
    // Create an empty queue for level order traversal
    queue<Node *> q;
 
    // Enqueue Root 
    q.push(root);
 
    while (q.empty() == false)
    {
        // Print front of queue and remove it from queue
        Node *node = q.front();
        cout << node->data << " ";
        q.pop();
 
        /* Enqueue left child */
        if (node->left != NULL)
            q.push(node->left);
 
        /*Enqueue right child */
        if (node->right != NULL)
            q.push(node->right);
    }
}
                                                    

Depth First Traversals

Inorder traversal
1.First, visit all the nodes in the left subtree
2.Then the root node
3.Visit all the nodes in the right subtree

Code:-

                                                        
void Inorder(struct Node* node)
{ 
    if (node == NULL) 
        return; 
  
    /* first recur on left child */
    Inorder(node->left); 
  
    /* then print the data of node */
    cout << node->data << " "; 
  
    /* now recur on right child */
    Inorder(node->right); 
}
                                                    

Preorder traversal
1.Visit root node
2.Visit all the nodes in the left subtree
3.Visit all the nodes in the right subtree
Code:-

                                                        
void Preorder(struct Node* node) 
{ 
    if (node == NULL) 
        return; 
  
    /* first print data of node */
    cout << node->data << " "; 
  
    /* then recur on left subtree */
    Preorder(node->left);  
  
    /* now recur on right subtree */
    Preorder(node->right); 
}
                                                    

Postorder traversal

1.Visit all the nodes in the left subtree
2.Visit all the nodes in the right subtree
3.Visit the root node

Code:-

                                                        
void Postorder(struct Node* node) 
{ 
    if (node == NULL) 
        return; 
  
    // first recur on left subtree 
    Postorder(node->left); 
  
    // then recur on right subtree 
    Postorder(node->right); 
  
    // now deal with the node 
    cout << node->data << " "; 
}
                                                    

Binary Search Tree(BST)

A binary search tree (BST)is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.The left and right subtree each must also be a binary search tree.

The basic operations of BST are as follows:-

1. Search : For searching an element in the binary search tree.

The algorithm works on the property that in a binary search tree,all the values in the left subtree are less than the particular node and all the values in the right subtree are greater than the particular node.If the value we are searching is less than the root,then the right subtree is not considered and if the value is greater than the root,then the left subtree is not considered.This is done recursively.

Code for the search operation is given below:

                                                        
struct node* find(struct node* root, int key) 
{
    if (root == NULL ) //If the key is not present in the tree
      return NULL; 
     
    if( root->key == key) // key is present at the root
      return root;
    
    if (root->key < key) //root's key is less than the key
      return find(root->right, key); 
  
   //root's key is greater than the key
    return find(root->left, key); 
}
                                                    

2. Insert : Inserting an element into the binary search tree.

The new element is inserted in such a way that even after adding the element,the properties of the BST hold true. We Start searching from the root node, if the value to be inserted is less than the data, search for an empty location in the left subtree and insert the data. Otherwise, search for an empty location in the right subtree and insert the data.

Code for insert operation is given below:-

                                                        
struct node *insert(struct node *node, int key) {
 
  // Return a new node if the tree is empty
  if (node == NULL) return newNode(key);
 
  if (key < node->key)
    node->left = insert(node->left, key);
  else
    node->right = insert(node->right, key);
 
  return node;
}
                                                    

3.Delete : Deleting an element present in the BST.

When we have to delete a node in BST,three cases arise:-
i)the node to be deleted is the leaf node
ii)the node to be deleted lies has a single child node
iii)the node to be deleted has two children

Code for the delete operation is given below:-

                                                        
struct node *delete(struct node *root, int key) {
  // Return if the tree is empty
  if (root == NULL) return root;
 
  // Find the node to be deleted
  if (key < root->key)
    root->left = Node(root->left, key);
  else if (key > root->key)
    root->right = Node(root->right, key);
  else {
 
    // If the node is with only one child or no child
    if (root->left == NULL) {
      struct node *temp = root->right;
      free(root);
      return temp;
    } else if (root->right == NULL) {
      struct node *temp = root->left;
      free(root);
      return temp;
    }
 
    // If the node has two children
    struct node *temp = minValueNode(root->right);
 
    // Place the inorder successor in position of the node to be deleted
    root->key = temp->key;
 
    // Delete the inorder successor
    root->right = deleteNode(root->right, temp->key);
  }
  return root;
}
                                                    

Heap

A Heap is a tree-based data structure in which all the nodes of the tree are in a specific order.

There are two types of Heap :-

1.Max Heap:- In Max Heap, the key of the parent node will always be greater than or equal to the key of the child node across the tree.

2.Min Heap:- In Min Heap, the key of the parent node will always be less than or equal to the key of the child node across the tree.

Heap in C++ STL

The heap operations are as follows:-

1.make_heap() : This function converts a range in a container to a heap.
2.front() : This function returns the first element of the heap which is the largest number.
3.push_heap() : This function is used to insert an element into the heap. The size of the heap is increased by 1.
4.pop_heap() : this function is used to delete the largest element of the heap.After deleting an element, the heap elements are reorganized accordingly. The size of heap is decreased by 1.
5.sort_heap() : This function is used to sort the heap in ascending order.
6.is_heap() : This function is used to check whether the container is a heap or not.
7.is_heap_until() : This function returns the iterator to the position till the container is the heap.

Code implementation with various operations :

Priority queue

A priority queue is an extension of a queue in which each element has a priority associated with it and is served according to its priority. If elements with the same priority occur, they are served according to their order in the queue.

Priority Queue in C++ STL

Syntax for creating priority queue.

                                                        
priority_queue<int> pq;
                                                    

Default C++ creates a max heap for priority queue.

The heap operations are as follows :-

1.push() : This function inserts an element in the priority_queue.Its time complexity is O(logN) where N is the size of the priority queue.

2.pop() : This function removes the topmost element from the priority queue, i.e, greatest element.Its time complexity is O(logN) where N is the size of the priority queue.

3.top() : This function returns the element at the top of the priority queue which is the greatest element present in the queue.Its time complexity is O(1).

4.size() : this function returns the size of the priority queue.Its time complexity is O(1).

5.empty() : this function returns boolean true if the priority queue is empty and false, if it’s not empty.Its time complexity is O(1).

6.swap() : This function is used to swap the contents of one priority queue with another priority queue of the same type and size.

Code implementation with various operations :

The C++ STL (Standard Template Library) is a powerful set of C++ template classes to provide general-purpose classes and functions with templates that implement many popular and commonly used algorithms and data structures like vectors, lists, queues, and stacks.

C++ Standard Template Library is made up of following three well-structured components −

Containers : Containers are used to manage collections of objects of a certain kind. There are several different types of containers like deque, list, vector, map etc.

Algorithms : Algorithms are defined as collections of functions especially designed to be used on ranges of elements.They act mainly on containers and provide means for various operations for the contents of containers.

Iterators : Iterators are used for working upon a sequence of different elements.These sequences may be containers.They are major features that allow generality in STL.

Iterator:
An iterator is any object that, points to some element in a range of elements (such as an array or a container) and has the ability to iterate through those elements using a set of operators (with at least the increment (++) and dereference (*) operators).
A pointer is a form of an iterator. A pointer can point to elements in an array, and can iterate over them using the increment operator (++). There can be other types of iterators as well. For each container class, we can define an iterator which can be used to iterate through all the elements of that container.

Example:

                                                        
vector<int>::iterator it;       // creates iterator it for vector container
                                                    

Implementation:

Pair:
Pair is a container that can be used to bind together two values which may be of different types. Pair provides a way to store two heterogeneous objects as a single unit.
One must include a <utility> header file to use the pair.

Different ways to declare and initialize pair are:

                                                        
pair < char , int > p1;         //creates a default pair
pair < char , int >p2 (‘a’,1);      //initialisation of pair p2  
pair < char , int > p3(p2);      //creates a copy of p2
                                                    

Implementation:

String:
C++ provides a powerful alternative for the char*. It is not a built-in data type, but is a container class in the Standard Template Library. String class provides different string manipulation functions like concatenation, find, replace etc.
<string> is a header file that contains functions of string containers.

Different ways to declare strings are:

string s ;
Creates empty string s
string s1(“Hello World”);
Creates string s1 storing Hello World
string s1(s2) ;
Creates a copy s1 of another string s2
string s1( s2,1,3);
Creates a string s1 storing substring of s2 from index 1 to index 3
string s1(“Hello World”,5);
Creates a string s1 storing “Hello” that is only 5 characters of passed string
string s1(5,”*”);
Creates string s1 storing “*****”
string s2(s1.begin(),s1.end());
Creates a copy of s1 using iterators.

Some of the member functions of string:

•append(): Inserts additional characters at the end of the string (can also be done using ‘+’ or ‘+=’ operator). Its time complexity is O(N) where N is the size of the new string.
Syntax to add str2 at the end of str1:
str1.append(str2)
•assign(): Assigns new string by replacing the previous value (can also be done using ‘=’ operator).
Syntax to assign str2 to str1:
str1.assign(str2)
•at(): Returns the character at a particular position (can also be done using ‘[ ]’ operator). Its time complexity is O(1).
Syntax to print character at index idx of string str:
str.at(idx)
•begin(): Returns an iterator pointing to the first character. Its time complexity is O(1).
Syntax:
string_name.begin()
•clear(): Erases all the contents of the string and assign an empty string (“”) of length zero. Its time complexity is O(1).
Syntax:
string_name.clear()
•compare(): Compares the value of the string with the string passed in the parameter and returns an integer accordingly. If both the strings are equal then it returns 0,if string s2 is greater than that of s1 then it returns value greater than zero otherwise it returns value less than zero.Its time complexity is O(N + M) where N is the size of the first string and M is the size of the second string.
Syntax to compare two strings:
s1.compare(s2)
Syntax to compare string s1 with s2 from idx index of s2 for len characters:
s2.compare(idx,len,s1)
•copy(): Copies the substring of the string in the string passed as parameter and returns the number of characters copied. Its time complexity is O(N) where N is the size of the copied string.
Syntax to copy s2 to s1:
s1.copy(s2)
•c_str(): Convert the string into a C-style string (null terminated string) and return the pointer to the C-style string. Its time complexity is O(1).
•empty(): Returns a boolean value, true if the string is empty and false if the string is not empty. Its time complexity is O(1).
Syntax:
string_name.empty()
•end(): Returns an iterator pointing to a position which is next to the last character. Its time complexity is O(1).
Syntax:
string_name.end()
•erase(): Deletes a substring of the string. Its time complexity is O(N) where N is the size of the new string.
Syntax to delete a character at position pos from string:
string_name.erase(pos)
Syntax to delete characters from a given range [pos1,pos2):
string_name.erase(pos1,pos2)
Syntax to remove substring of length len from index idx:
string_name.erase(idx,len)
•find(): Searches the string and returns the first occurrence of the parameter in the string. Its time complexity is O(N) where N is the size of the string.
Syntax to find str2 from str1:
str1.find(str2)
•insert(): Inserts additional characters into the string at a particular position. Its time complexity is O(N) where N is the size of the new string.
•length(): Returns the length of the string. Its time complexity is O(1).
Syntax:
string_name.length()
•replace(): Replaces the particular portion of the string. Its time complexity is O(N) where N is the size of the new string.
Syntax to replace len characters from pos position of str1 with str2:
str1(pos,len,str2)
•resize(): Resize the string to the new length which can be less than or greater than the current length.If new size is greater than that of original one then character passed as parameter is added to string to make it of new size. Its time complexity is O(N) where N is the size of the new string.
Syntax :
string_name.resize(new_size,character)
•size(): Returns the length of the string. Its time complexity is O(1).
Syntax:
string_name.size()
•substr(): Returns a string which is the copy of the substring of range [pos,pos+len) where pos is position and len is length given as parameters.Its time complexity is O(N) where N is the size of the substring.
Syntax:
string_name.substr(pos,len)

Implementation:

Same as dynamic arrays,vectors are STL containers having the ability to resize itself automatically when an element is inserted or deleted, with their storage being handled automatically by the container. Vector elements are placed in contiguous storage so that its elements can be accessed and traversed using iterators just as efficiently as in arrays.
One must include a <vector> header file to use vectors.

Ways to create vectors:

vector<data_type> v;
Creates an empty vector v without any element.
vector<data_type> v1(v2) ;
Creates a copy of another vector of the same type.(all elements of v2 is copied to v1)
vector<data_type> v(n);
Creates a vector v with n elements that are created by the default constructor.
vector<data_type> v(n,element);
Creates a vector v initialised with n copies of element elem.
vector<data_type> v(beg,end);
Creates a vector v initialised with the elements of range [beg,end).

Some of the member functions of vectors are:
•at():It returns a reference to the element at specified position in the vector.Its time complexity is O(1).
Syntax:
vector_name.at(val)
where val is the position to be fetched.
•insert():Inserts new elements into the vector at a particular position. Its time complexity is O(N + M) where N is the number of elements inserted and M is the number of the elements moved .
Syntax to insert element val at position pos:
vector_name.insert(pos,val)
•push_back():Inserts a new element at the end of the vector. Its time complexity is O(1).
Syntax:
vector_name.push_back(val)
where val is the element to be inserted.
•pop_back():Removes the last element from the vector. Its time complexity is O(1).
Syntax:
vector_name.pop_back()
•begin():It is a function which returns an iterator pointing to the first element of the vector.Its time complexity is O(1).
Syntax:
vector_name.begin()
•end():It is a function which returns an iterator pointing to next to the last element of the vector.Its time complexity is O(1).
Syntax:
vector_name.end()
•back():It returns a reference to the last element in the vector.Its time complexity is O(1).
Syntax:
vector_name.back()
•front():It returns a reference to the element at specified position in the vector.Its time complexity is O(1).
Syntax:
vector_name.front()
•clear():Deletes all the elements from the vector and assigns an empty vector. Its time complexity is O(N) where N is the size of the vector.
Syntax:
vector_name.clear()
•size():It is a function which returns the number of elements present in the vector.Its time complexity is O(1).
Syntax:
vector_name.size()
•empty():It is a function which is used to check whether the vector is empty or not.It returns true if the vector is empty otherwise returns false.Its time complexity is O(1).
Syntax:
vector_name.empty()
•erase():It is a function used to remove elements from the specified position of the vector.
Its time complexity is O(N + M) where N is the number of the elements erased and M is the number of the elements moved.
Syntax to remove element at a specified position pos:
vector_name.erase(pos);
Syntax to remove elements from a given range [pos1,pos2):
vector_name.erase(pos1,pos2)
•resize():This function resizes the container so that its size becomes n.This function alters the container by removing or inserting values in the vector.Its time complexity is O(N) where N is the size of the resized vector.
Syntax:
vector_name.resize(n,val)
where n is the new container size and val is the value to be inserted if the new size exceeds current one.

Implementation:

Lists are sequence containers that allow non-contiguous memory allocation. As compared to vector, list has slow traversal, but once a position has been found, insertion and deletion are quick.It is implemented as Doubly linked list in STL.
One must include a <list> header file to use list.

Syntax to declare list:
list<data_type> list_name

Some of the member function of List:

•begin():It is a function which returns an iterator pointing to next to the last element of the list.Its time complexity is O(1).
Syntax:
list_name.end()

•end():It is a function which returns an iterator pointing to next to the last element of the list.Its time complexity is O(1).
Syntax:
list_name.end()

•push_back():It adds a new element at the end of the list, after its current last element. Its time complexity is O(1).
Syntax to insert val at the end of the list:
list_name.push_back(val)

•pop_back():It removes the last element of the list, thus reducing its size by 1. Its time complexity is O(1).
Syntax to remove the last element of the list
list_name.pop_back()

•push_front():It adds a new element at the front of the list, before its current first element. Its time complexity is O(1).
Syntax to insert val at the beginning of the list:
list_name.push_front(val)

•pop_front():It removes the first element of the list, thus reducing its size by 1. Its time complexity is O(1).
Syntax to remove first element of the list:
list_name.pop_front()

•front():It returns a reference to the element at specified position in the list.Its time complexity is O(1).
Syntax:
list_name.front()

•back():It returns a reference to the last element in the list.Its time complexity is O(1).
Syntax:
list_name.back()

•assign(): It assigns new elements to the list by replacing its current elements and changing its size accordingly.It time complexity is O(N).
Syntax to replace n number of elements from beginning with val
list_name.assign(n,val)

•insert():It inserts new elements in the list before the element on the specified position. Its time complexity is O(N).
Syntax for inserting n elements having value val before pos
list_name.insert(pos,n,val)

•erase():It removes all the elements from the list, which are equal to the given element. Its time complexity is O(N).
Syntax to remove element from a specified position:
list_name.erase(pos)
Syntax to remove element from given range [pos1,pos2):
list_name.erase(pos1,pos2)

•remove():It removes all the elements from the list, which are equal to the given element passed as parameter. Its time complexity is O(N).
Syntax:
list_name.remove(val)

•empty():It is a function which is used to check whether the list is empty or not.It returns 1 if the list is empty otherwise it returns 0.Its time complexity is O(1).
Syntax:
list_name.empty()

•size():It returns the number of elements in the list. Its time complexity is O(1).
Syntax :
list_name.size()

•reverse():It reverses the order of elements in the list. Its time complexity is O(N).
Syntax:
list_name.reverse()

Implementation:

Sets are associative containers which store unique values in sorted order. The value of the element cannot be modified once it is added to the set, though it is possible to remove and add the modified value of that element.
One must include a <set> header file to use set.

Ways to create set are:

set<data_type> set_name
Creates an empty set
set<data_type> s1(arr,arr+n)
Creates set s1 from a given array arr of size n
set<data_type> s2(s1)
Creates a copy s2 of set s1
set<data_type> s2(s1.begin(),s1.end())
Creates a copy s2 of set s1 using iterators

Some of the member functions of set are:

•begin():It is a function which returns an iterator pointing to the first element of the set.Its time complexity is O(1).
Syntax:
set_name.begin()

•end():It is a function which returns an iterator pointing to next to the last element of the set.Its time complexity is O(1).
Syntax:
set_name.end()

•insert():It inserts new elements in the set passed as parameter.Its time complexity is O(logN) where N is the size of the set.
Syntax:
set_name,insert(val)

•count():It returns 1 if the element passed as parameter is present otherwise 0.Its time complexity is O(logN) where N is the size of the set.
Syntax:
set_name.count(val)

•find():It returns the iterator pointing to the position where the value passed as parameter is present.If the value is not present in the set then it returns iterator pointing to s.end()
where s is the name of the set.Its time complexity is O(logN) where N is the size of the set.
Syntax:
set_name.find(val)

•erase():Deletes a particular element or a range of elements from the set. Its time complexity is O(N) where N is the number of elements deleted.
Syntax to remove element at position pos:
set_name.erase(pos)
Syntax to remove elements from a given range [pos1,pos2):
set_name.erase(pos1,pos2)

•empty():Returns true if the set is empty and false if the set has at least one element. Its time complexity is O(1).
Syntax:
set_name.empty()

•clear():Deletes all the elements in the set and the set will be empty. Its time complexity is O(N) where N is the size of the set.
Syntax:
set_name.clear()

•size():It returns the number of elements in the set. Its time complexity is O(1).
Syntax :
set_name.size()

Implementation:

Multiset is a set container which has all the functions same as that of set but with an exception that it can hold the same value multiple times.

Syntax for creating a multiset:
multiset<data_type> multiset_name

Some of the member functions of set are:

•begin():It is a function which returns an iterator pointing to the first element of the multiset.Its time complexity is O(1).
Syntax:
set_name.begin()

•end():It is a function which returns an iterator pointing to next to the last element of the multiset.Its time complexity is O(1).
Syntax:
set_name.end()

•insert():It inserts new elements in the multiset passed as parameter.Its time complexity is O(log N) where N is the size of the multiset.
Syntax:
set_name.insert(val)

•count():It returns the count of numbers of elements whose values are equal to the value passed as parameter.Its time complexity is O(log N) where N is the size of the multiset.
Syntax:
set_name.count(val)

•find():It returns the iterator pointing to the position where the value passed as parameter is present.If the value is not present in the set then it returns iterator pointing to s.end()
where s is the name of the multiset.Its time complexity is O(log N) where N is the size of the size of the multiset.
Syntax:
set_name.find(val)

•erase():Deletes a particular element or a range of elements from the set. Its time complexity is O(N) where N is the number of elements deleted.
Syntax to remove element at position pos:
set_name.erase(pos)
Syntax to remove elements from a given range [pos1,pos2):
set_name.erase(pos1,pos2)

•empty():Returns true if the set is empty and false if the set has at least one element. Its time complexity is O(1).
Syntax:
set_name.empty()

•clear():Deletes all the elements in the set and the set will be empty. Its time complexity is O(N) where N is the size of the set.
Syntax:
set_name.clear()

•size():It returns the number of elements in the set. Its time complexity is O(1).
Syntax :
set_name.size()

Implementation:

It is an associative container that contains an unordered set of data inserted randomly. Each element may occur only once, so duplicates are not allowed. A user can create an unordered set by inserting elements in any order and an unordered set will return data in any order i.e. unordered form.The main reasons when unordered set can be used are when no sorted data is required means the data is available in an unordered format,when only unique data is needed,when we want to use hash table instead of a binary search tree and when a faster search is required as it take O(1) in average case and O(n) in worst case.
One must include <unordered_set> header file to use unordered_set.

Syntax for creating unordered_set:

unordered_set<int> s; //creates an empty unordered set
unordered_set<int> s={1,2,3,4}; //creates an unordered set containing 1,2,3 and 4

Some of the member functions of set are:
begin():It is a function which returns an iterator pointing to the first element of the unordered set.Its time complexity is O(1).
Syntax:
unordered_set_name.begin()
end():It is a function which returns an iterator pointing to next to the last element of the unordered set.Its time complexity is O(1).
Syntax:
unordered_set_name.end()
insert():It inserts new elements in the unordered set passed as parameter.Its time complexity is O(1) in average case but O(N) in worst case where N is the size of the unordered set.
Syntax:
unordered_set_name,insert(val)
count():It returns 1 if the element passed as parameter is present otherwise 0.Its time complexity is O(1) in average case but O(N) in worst case where N is the size of the unordered set.
Syntax:
unordered_set_name.count(val)
find():It returns the iterator pointing to the position where the value passed as parameter is present.If the value is not present in the unordered set then it returns iterator pointing to s.end() where s is the name of the set.Its time complexity is O(1) in average case but O(N) in worst case where N is the size of the unordered set.
Syntax:
unordered_set_name.find(val)
erase():Deletes a particular element or a range of elements from the unordered set. Its time complexity is O(N) where N is the number of elements deleted.
Syntax to remove element at position pos:
unordered_set_name.erase(pos)
Syntax to remove elements from a given range [pos1,pos2):
unordered_set_name.erase(pos1,pos2)
empty():Returns true if the unordered set is empty and false if the unordered set has at least one element. Its time complexity is O(1).
Syntax:
unordered_set_name.empty()
clear():Deletes all the elements in the unordered set and the unordered set will be empty. Its time complexity is O(N) where N is the size of the unordered set.
Syntax:
unordered_set_name.clear()
size():It returns the number of elements in the unordered set. Its time complexity is O(1).
Syntax :
unordered_set_name.size()

Implementation:

Unordered Multiset:
Unordered multiset is an associative container that contains a set of possibly non-unique objects of type Key. Search, insertion, and removal have average constant-time complexity.
Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its value.This allows fast access to individual elements, since once hash is computed, it refers to the exact bucket the element is placed into.
One must include <unordered_set> header file to use multiset.

Syntax for creating unordered_multiset:

                                                        
unordered_multiset<int> s;     //creates an empty unordered multiset
unordered_multiset<int> s={1,2,3,4};   //creates an unordered multiset containing 1,2,3 and 4
                                                    

Some of the member functions of set are:
begin():It is a function which returns an iterator pointing to the first element of the unordered multiset.Its time complexity is O(1).
Syntax:
unordered_multiset_name.begin()
end():It is a function which returns an iterator pointing to next to the last element of the unordered multiset.Its time complexity is O(1).
Syntax:
unordered_multiset_name.end()
insert():It inserts new elements in the unordered multiset passed as parameter.Its time complexity is O(1) in average case but O(N) in worst case where N is the size of the unordered multiset.
Syntax:
unordered_multiset_name,insert(val)
count():It returns the count of the element passed as parameter. Its time complexity is O(N) where N is the number of elements counted.
Syntax:
unordered_multiset_name.count(val)
find():It returns the iterator pointing to the position where the value passed as parameter is present.If the value is not present in the unordered multiset then it returns iterator pointing to s.end() where s is the name of the unordered multiset.Its time complexity is O(1) in average case but O(N) in worst case where N is the size of the unordered multiset.
Syntax:
unordered_multiset_name.find(val)
erase():Deletes a particular element or a range of elements from the unordered multiset. Its time complexity is O(N) where N is the number of elements deleted.
Syntax to remove element at position pos:
unordered_multiset_name.erase(pos)
Syntax to remove elements from a given range [pos1,pos2):
unordered_multiset_name.erase(pos1,pos2)
empty():Returns true if the unordered multiset is empty and false if the unordered multiset has at least one element. Its time complexity is O(1).
Syntax:
unordered_multiset_name.empty()
clear():Deletes all the elements in the unordered multiset and the unordered multiset will be empty. Its time complexity is O(N) where N is the size of the unordered multiset.
Syntax:
unordered_multiset_name.clear()
size():It returns the number of elements in the unordered multiset. Its time complexity is O(1).
Syntax :
unordered_multiset_name.size()

Implementation:

Maps are associative containers that store elements in a mapped fashion. Each element has a key value and a mapped value. Here key values are used to uniquely identify the elements mapped to it. The data type of key value and mapped value can be different. Elements in the map are always in sorted order by their corresponding key and can be accessed directly by their key using bracket operator ([ ]).
One must include <map> header file to use the map

Declaration of map:

                                                        
map<char,int> m;     //creates map m where key is char type and value is int type
m[‘a’]=2;                   //assign 2 to key a
                                                    

Some Member Functions of map:

begin( ): returns an iterator(explained above) referring to the first element of map.Its time complexity is O(1).
Syntax:
map_name.begin()
insert( ): insert a single element or the range of elements in the map.Its time complexity is O(logN)where N is the number of elements in the map, when only element is inserted and O(1) when position is also given.
Syntax:
map_name.insert({key,element})
end( ): It returns an iterator referring to the theoretical element(doesn’t point to an element) which follows the last element.Its time complexity is O(1).
Syntax:
map_name.end()
count( ):It searches the map for the elements mapped by the given key and returns the number of matches.As map stores each element with unique key, then it will return 1 if match if found otherwise return 0.Its time complexity is O(logN) where N is the number of elements in the map.
Syntax:
map_name.count(k) //k is the key
find( ): It searches the map for the element with the given key, and returns an iterator to it, if it is present in the map otherwise it returns an iterator to the theoretical element which follows the last element of map.Its time complexity is O(logN) where N is the number of elements in the map.
Syntax:
map_name.find(key)
clear( ): It clears the map, by removing all the elements from the map and leaving it with its size 0.Its time complexity is O(N) where N is the number of elements in the map.
Syntax:
map_name.clear()
empty( ): It checks whether the map is empty or not. It doesn’t modify the map.It returns 1 if the map is empty otherwise returns 0.Its time complexity is O(1).
Syntax:
map_name.empty()
erase( ): It removes a single element or the range of elements from the map.
Syntax for erasing a key:
map_name.erase(key)
Syntax for erasing the value from a particular position pos:
map_name.erase(pos)
Syntax for erasing values within a given range [pos1,pos2):
map_name.erase(pos1,pos2)

Implementation:

Multimap is an associative container that contains a sorted list of key-value pairs, while permitting multiple entries with the same key. Sorting is done according to the comparison function Compare, applied to the keys. Search, insertion, and removal operations have logarithmic complexity.
One must include <map> header file to use multimap.

Syntax to create multimap:

multimap<int,int> m1;
Creates empty multimap m1 that stores key and mapped value both of int data type.
multimap<int,int> m2={{1,20},{2,50}};
Creates initialised multimap m2
multimap<int,int> m3(m2.begin(),m2.end());
Creates a copy of multimap m2 using iterators.
multimap<int,int> m4=m2;
Creates a copy of multimap m2

Some Member Functions of map:

begin( ): It returns an iterator(explained above) referring to the first element of multimap.Its time complexity is O(1).
Syntax:
multmap_name.begin()
insert( ):It inserts a single element or the range of elements in the multmap.Its time complexity is O(logN)where N is the number of elements in the map, when only element is inserted and O(1) when position is also given.
Syntax:
multmap_name.insert({key,element})
end( ): It returns an iterator referring to the theoretical element(doesn’t point to an element) which follows the last element.Its time complexity is O(1).
Syntax:
multmap_name.end()
count( ):It searches the multmap for the elements mapped by the given key and returns the number of matches..Its time complexity is O(logN) where N is the number of elements in the map.
Syntax:
multmap_name.count(k) //k is the key
find( ): It searches the multmap for the element with the given key, and returns an iterator to it, if it is present in the multimap otherwise it returns an iterator to the theoretical element which follows the last element of the multmap.Its time complexity is O(logN) where N is the number of elements in the multimap.
Syntax:
multmap_name.find(key)
clear( ): It clears the multimap, by removing all the elements from the multmap and leaving it with its size 0.Its time complexity is O(N) where N is the number of elements in the multimap.
Syntax:
multmap_name.clear()
empty( ): It checks whether the multimap is empty or not. It doesn’t modify the multimap.It returns 1 if the multimap is empty otherwise it returns 0.Its time complexity is O(1).
Syntax:
multimap_name.empty()
erase( ): It removes a single element or the range of elements from the multimap.
Syntax for erasing a key:
multimap_name.erase(key)
Syntax for erasing the value from a particular position pos:
multimap_name.erase(pos)
Syntax for erasing values within a given range [pos1,pos2):
multimap_name.erase(pos1,pos2)

Implementation:

Unordered maps are associative containers that store elements formed by the combination of a key value and a mapped value, and which allows for fast retrieval of individual elements based on their keys.In an unordered map, the key value is generally used to uniquely identify the element, while the mapped value is an object with the content associated to this key.Internally unordered_map is implemented using hash table, the key provided to map are hashed into indices of hash table that is why performance of data structure depends on hash function a lot but on an average the cost of search, insert and delete from the hash table is O(1).
One must include <unordered_map> header file to use unordered map.

Syntax to create unordered map are:

                                                        
unordered_map<data_type,data_type> unordered_map_name;
                                                    

Some Member Functions of map:

begin( ): It returns an iterator referring to the first element of unordered map.Its time complexity is O(1).
Syntax:
map_name.begin()
insert( ): insert a single element or the range of elements in the unordered map.Its time complexity is O(1) ,when only element is inserted and O(N) when N numbers of elements are inserted.
Syntax:
map_name.insert({key,element})
end( ): It returns an iterator referring to the theoretical element(doesn’t point to an element) which follows the last element.Its time complexity is O(1).
Syntax:
map_name.end()
count( ):It searches the map for the elements mapped by the given key and returns the number of matches.As unordered map stores each element with unique key, then it will return 1 if match if found otherwise return 0.Its time complexity is O(N) where N is the number of elements counted.
Syntax:
map_name.count(k) //k is the key
find( ): It searches the unordered map for the element with the given key, and returns an iterator to it, if it is present in the unordered map otherwise it returns an iterator to the theoretical element which follows the last element of the unordered map.Its time complexity is O(1) in average case but in worst case it is O(N) where N is the number of elements in the unordered map.
Syntax:
map_name.find(key)
clear( ): It clears the unordered map, by removing all the elements from the unordered map and leaving it with its size 0.Its time complexity is O(N) where N is the number of elements in the unordered map.
Syntax:
map_name.clear()
empty( ): It checks whether the unordered map is empty or not. It doesn’t modify the unordered map.It returns 1 if the unordered map is empty otherwise it returns 0.Its time complexity is O(1).
Syntax:
map_name.empty()
erase( ): It removes a single element or the range of elements from the unordered map.
Syntax for erasing a key:
map_name.erase(key)
Syntax for erasing the value from a particular position pos:
map_name.erase(pos)
Syntax for erasing values within a given range [pos1,pos2):
map_name.erase(pos1,pos2)

Implementation:

Unordered multimaps are associative containers that store elements formed by the combination of a key value and a mapped value, much like unordered map containers, but allowing different elements to have equivalent keys.In an unordered_multimap, the key value is generally used to uniquely identify the element, while the mapped value is an object with the content associated to this key. Types of key and mapped value may differ.

Internally, the elements in the unordered_multimap are not sorted in any particular order with respect to either their key or mapped values,

Syntax to create unordered multimap:

                                                        
unordered_multimap<data_type,data_type> map_name;
                                                    

Some Member Functions of map:

begin( ): It returns an iterator(explained above) referring to the first element of unordered multimap.Its time complexity is O(1).
Syntax:
map_name.begin()
insert( ):It inserts a single element or the range of elements in the unordered multmap.Its time complexity is O(N) where N is the number of elements inserted.
Syntax:
map_name.insert({key,element})
end( ): It returns an iterator referring to the theoretical element(doesn’t point to an element) which follows the last element.Its time complexity is O(1).
Syntax:
map_name.end()
count( ):It searches the unordered multmap for the elements mapped by the given key and returns the number of matches..Its time complexity is O(N) where N is the number of elements counted.
Syntax:
map_name.count(k) //k is the key
find( ): It searches the unordered multmap for the element with the given key, and returns an iterator to it, if it is present in the unordered multimap otherwise it returns an iterator to the theoretical element which follows the last element of the unordered multmap.Its time complexity is O(1) in average case and O(N) in worst case where N number of elements in the unordered multimap.
Syntax:
map_name.find(key)
clear( ): It clears the unordered multimap, by removing all the elements from the unordered multmap and leaving it with its size 0.Its time complexity is O(N) where N is the number of elements in the unordered multimap.
Syntax:
map_name.clear()
empty( ): It checks whether the unordered multimap is empty or not. It doesn’t modify the unordered multimap.It returns 1 if the unordered multimap is empty otherwise it returns 0.Its time complexity is O(1).
Syntax:
map_name.empty()
erase( ): It removes a single element or the range of elements from the unordered multimap.
Syntax for erasing a key:
map_name.erase(key)
Syntax for erasing the value from a particular position pos:
map_name.erase(pos)
Syntax for erasing values within a given range [pos1,pos2):
map_name.erase(pos1,pos2)

Implementation:

Queues are a type of container adaptors which operate in a first in first out (FIFO) type of arrangement. Elements are inserted at the back (end) and are deleted from the front.

Stacks are a type of container adaptors with LIFO(Last In First Out) type of working, where a new element is added at one end and (top) an element is removed from that end only.