// Sieve of Eresthostenes o(nlog(logn))

#include <bits/stdc++.h>
using namespace std;
void sieve(int n)
{
vector<bool>isprime(n+1,true);
for(int i=2;i<=n;i++)
{
if(isprime[i])
{
cout<<i<<" ";
for(int j=i*i;j<=n;j+=i)
{
isprime[j]=false;
}
}
}
}
int main() {
int n;
cin>>n;
sieve(n);
return 0;
}

// matrix multiplication o(n^3)

#include <iostream>
using namespace std;

int main() {
int n;
cin >> n;
int a1[n][n], a2[n][n], f[n][n];

// Input first matrix

for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cin >> a1[i][j];
}
}

// Input second matrix

for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cin >> a2[i][j];
}
}

// Initialize result matrix to zeros

for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
f[i][j] = 0;
}
}
int steps=0;
// Matrix multiplication
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
for(int k = 0; k < n; k++) {
 f[i][j] += a1[i][k] * a2[k][j];
steps++;
}
}
}

// Output the result matrix

for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cout << f[i][j] << " ";
}
cout << endl;
}
cout<<"steps"<<steps<<endl;

return 0;
}

//transpose 0(n^2)
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int a1[n][n], f[n][n];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cin >> a1[i][j];
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
f[i][j]=a1[j][i];
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cout<< a1[i][j]<<" ";
}
cout<<endl;
}
cout<<"transpose"<<endl;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cout << f[i][j] << " ";
}
cout << endl;
}

return 0;
}
//bin and ter o(logn)2 and 3
#include <iostream>
using namespace std;

int binsearch(int a[], int x, int n) {

int s = 0, e = n - 1;
while (s <= e) {
int mid = s + (e - s) / 2; // Corrected calculation of mid
 if (a[mid] == x) {
return mid;
} else if (a[mid] < x) {
s = mid + 1;
} else {
e = mid - 1;
}
}
return -1; // Return -1 if element not found
}

int tersearch(int a[], int x, int n) {

int s = 0, e = n - 1;
while (s <= e) {
int mid1 = s + (e - s) / 3;
int mid2 = e - (e - s) / 3;
if (a[mid1] == x) {
return mid1;
} else if (a[mid2] == x) {
return mid2;
} else if (a[mid1] > x && a[mid2] < x) {
s = mid1 + 1;
e = mid2 - 1;
} else if (a[mid1] < x) {
s = mid1 + 1;
} else {
e = mid2 - 1;
}
}
return -1; // Return -1 if element not found
}

int main() {
int n, x;
cout << "Enter the size of the array: ";
cin >> n;
int a[n];
cout << "Enter the elements of the array in sorted order:" << endl;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
cout << "Enter the element to search: ";
cin >> x;
cout << "Binary Search: " << binsearch(a, x, n)+1 << endl;
cout << "Ternary Search: " << tersearch(a, x, n)+1 << endl;
return 0;
}

//linked list merge sort

#include <iostream>
using namespace std;

// Node structure for the linked list

struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
// Merge function to merge two sorted linked lists
Node* merge(Node* q, Node* r) {
Node* head = nullptr;
Node* k = nullptr;

while (q != nullptr && r != nullptr) {

if (q->data <= r->data) {
if (head == nullptr) {
head = k = q;
} else {
k->next = q;
k = q;
}
q = q->next;
} else {
if (head == nullptr) {
head = k = r;
} else {
k->next = r;
k = r;
}
r = r->next;
}
}

if (q == nullptr) {
k->next = r;
} else {
k->next = q;
}

return head;
}

// Merge sort function to sort a linked list

Node* mergeSort(Node* head)
{
if (head == nullptr || head->next == nullptr) {
return head;
}

// Find middle of the list

Node* slow = head;
Node* fast = head->next;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
Node* mid = slow->next;
slow->next = nullptr;

// Recursively sort both halves

Node* q = mergeSort(head);
Node* r = mergeSort(mid);

// Merge the sorted halves

return merge(q, r);
}
// Function to print the linked list
void printList(Node* head) {
while (head != nullptr) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}

int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;

cout << "Enter the elements: ";

Node* head = nullptr;
Node* tail = nullptr;
for (int i = 0; i < n; ++i) {
int num;
cin >> num;
Node* newNode = new Node(num);
if (head == nullptr) {
head = tail = newNode;
} else {
tail->next = newNode;
tail = newNode;
}
}

head = mergeSort(head);

cout << "Sorted linked list: ";

printList(head);

// Free the memory allocated to nodes

Node* temp;
while (head != nullptr) {
temp = head;
head = head->next;
delete temp;
}

return 0;
}

//2nd quick sort

#include <bits/stdc++.h>
using namespace std;

int medianOfThree(vector<int> &arr, int low, int high) {

int mid = low + (high - low) / 2;
if (arr[low] < arr[mid])
swap(arr[low], arr[mid]);
if (arr[low] < arr[high])
swap(arr[low], arr[high]);
if (arr[mid] < arr[high])
swap(arr[mid], arr[high]);
swap(arr[mid], arr[high - 1]);
return arr[high - 1];
}

int partition(vector<int> &arr, int low, int high) {

int pivot = medianOfThree(arr, low, high);
int i = low, j = high - 1;
for (;;) {
while (arr[++i] < pivot) {}
while (pivot < arr[--j]) {}
if (i < j)
swap(arr[i], arr[j]);
else
break;
}
swap(arr[i], arr[high - 1]);
return i;
}

void quickSort(vector<int> &arr, int low, int high) {

if (low + 10 <= high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
} else {
// Use insertion sort
for (int i = low + 1; i <= high; i++) {
int key = arr[i];
int j = i - 1;
while (j >= low && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
}

int main() {
vector<int> arr = {10, 7, 8, 9, 1, 5};
int n = arr.size();
quickSort(arr, 0, n - 1);
cout << "Sorted array: \n";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
//1st
#include <bits/stdc++.h>
using namespace std;

int partition(vector<int> &arr, int low, int high) {

int pivot = arr[low + rand() % (high - low + 1)];
int i = low - 1;
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
 return (i + 1);
}

void quickSort(vector<int> &arr, int low, int high) {

if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

int main() {
vector<int> arr = {10, 7, 8, 9, 1, 5};
int n = arr.size();
quickSort(arr, 0, n - 1);
cout << "Sorted array: \n";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}

//magic square
#include <iostream>
using namespace std;

int main() {
int n;
cin >> n;
int a[n][n], f = 0;
int c[n] = {0}, r[n] = {0}, d1 = 0, d2 = 0; // Initialize arrays and variables
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
if (i == j) // Calculate diagonal sums
d1 += a[i][j];
if (i + j == n - 1) // Calculate other diagonal sum
d2 += a[i][j];
c[i] += a[i][j]; // Calculate column sums
r[j] += a[i][j]; // Calculate row sums
}
}

// Check if sums of all rows, columns, and diagonals are equal

if (d1 == d2) {
for (int i = 0; i < n; i++) {
if (c[i] != d1 || r[i] != d1) { // If any row or column sum is not
equal to diagonal sum
f = 1;
break;
}
}
if (f == 0) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
} else {
cout << "NO" << endl;
}
 return 0;
}
//bst height ,no of nodes
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

struct Node {
int data;
Node* left;
Node* right;

Node(int val) : data(val), left(nullptr), right(nullptr) {}

};

Node* insert(Node* root, int data) {

if (root == nullptr) {
root = new Node(data);
return root;
}
if (data <= root->data) {
root->left = insert(root->left, data);
} else {
root->right = insert(root->right, data);
}
return root;
}

int height(Node* root) {

if (root == nullptr) return -1;

int leftHeight = height(root->left);

int rightHeight = height(root->right);

return max(leftHeight, rightHeight) + 1;

}

int countNodes(Node* root) {

if (root == NULL) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}

int main() {
Node* root = nullptr;
int n;
cout << "Enter the number of nodes in the BST: ";
cin >> n;
cout << "Enter the nodes of the BST: ";
for (int i = 0; i < n; ++i) {
int data;
cin >> data;
root = insert(root, data);
}

int bstHeight = height(root);

cout << "Height of the BST is: " << bstHeight << endl;

int nodeCount = countNodes(root);

 cout << "Number of nodes in the BST is: " << nodeCount << endl;

return 0;
}

//union intersection
#include <iostream>
#include <algorithm>
using namespace std;

// Function to find union of two arrays

void findUnion(int arr1[], int m, int arr2[], int n) {
int i = 0, j = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j]) {
cout << arr1[i] << " ";
i++;
} else if (arr1[i] > arr2[j]) {
cout << arr2[j] << " ";
j++;
} else {
cout << arr1[i] << " ";
i++;
j++;
}
}
while (i < m) {
cout << arr1[i++] << " ";
}
while (j < n) {
cout << arr2[j++] << " ";
}
}

// Function to find intersection of two arrays

void findIntersection(int arr1[], int m, int arr2[], int n) {
int i = 0, j = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j]) {
i++;
} else if (arr1[i] > arr2[j]) {
j++;
} else {
cout << arr1[i] << " ";
i++;
j++;
}
}
}

int main() {
int arr1[] = {1, 3, 4, 5, 7};
int arr2[] = {2, 3, 5, 6};
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
sort(arr1, arr1 + m);
sort(arr2, arr2 + n);
cout << "Union of sorted arrays: ";
findUnion(arr1, m, arr2, n);
 cout << endl;
cout << "Intersection of sorted arrays: ";
findIntersection(arr1, m, arr2, n);
cout << endl;

return 0;
}
//merge
#include <iostream>
using namespace std;

void merge(int a[], int s, int mid, int e) {

int n = e - s + 1;
int i = s, j = mid + 1, k = 0;
int temp[n]; // Create a temporary array to store merged elements
while (i <= mid && j <= e) {
if (a[i] < a[j]) {
temp[k++] = a[i++];
} else if (a[i] > a[j]) {
temp[k++] = a[j++];
} else {
temp[k++] = a[i++];
j++;
}
}
while (i <= mid) {
temp[k++] = a[i++];
}
while (j <= e) {
temp[k++] = a[j++];
}
for (int x = 0; x < n; x++) {
a[s + x] = temp[x]; // Copy the merged elements back into the original
array
}
}

void mergeSort(int a[], int s, int e) {

if (s < e) {
int mid = (s + e) / 2; // Calculate the middle index
mergeSort(a, s, mid); // Sort the left subarray
mergeSort(a, mid + 1, e); // Sort the right subarray
merge(a, s, mid, e); // Merge the sorted subarrays
}
}

int main() {
int n;
cout << "Enter the size of the array: ";
cin >> n;
int a1[n];
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> a1[i];
}
mergeSort(a1, 0, n - 1); // Sort the array
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << a1[i] << " ";
 }
cout << endl;
return 0;
}
//quick sort
#include <iostream>
using namespace std;

int partition(int a[], int s, int e) {

int p=a[e];
int i=s-1,j=s;
for(j=s;j<=e;j++)
{
if(a[j]<p)
{
i++;
swap(a[i],a[j]);
}
}
swap(a[i+1],a[e]);
return i+1;
}

void quicksort(int a[], int s, int e) {

if(s<e)
{
int pi=partition(a,s,e);
quicksort(a,s,pi-1);
quicksort(a,pi+1,e);

}
}

int main() {
int n;
cout << "Enter the size of the array: ";
cin >> n;
int a1[n];
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> a1[i];
}
quicksort(a1, 0, n - 1); // Sort the array
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << a1[i] << " ";
}
cout << endl;
return 0;
}
//3 median of 3
#include <iostream>
using namespace std;
int medianof3(int a[], int s, int e) {
int mid = (s + e) / 3;
int a1 = a[s], a2 = a[mid], a3 = a[e];
if ((a1 > a2 && a2 > a3) || (a1 < a2 && a2 < a3)) {
return mid;
} else if (a1 < a2 && a2 > a3) {
 return s;
} else {
return e;
}
}

int partition(int a[], int s, int e) {

int index = medianof3(a, s, e);
swap(a[index], a[s]);
int p = a[s];
int i = s;
for (int j = s + 1; j <= e; j++) {
if (a[j] < p) {
i++;
swap(a[i], a[j]);
}
}
swap(a[i], a[s]);
return i;
}

void quicksort(int a[], int s, int e) {

if (s < e) {
int pi = partition(a, s, e);
quicksort(a, s, pi - 1);
quicksort(a, pi + 1, e);
}
}

int main() {
int n;
cout << "Enter the size of the array: ";
cin >> n;
int a1[n];
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> a1[i];
}
quicksort(a1, 0, n - 1); // Sort the array
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << a1[i] << " ";
}
cout << endl;
return 0;
}

//insertion +quick sort

#include <iostream>
using namespace std;

void insertionSort(int a[], int s, int e) {

for (int i = s + 1; i <= e; i++) {
int j = i - 1;
int key = a[i];
while (j >= s && a[j] > key) {
a[j + 1] = a[j];
j--;
}
 a[j + 1] = key;
}
}

int partition(int a[], int s, int e) {

int pivot = a[e];
int i = s - 1;
for (int j = s; j < e; j++) {
if (a[j] < pivot) {
i++;
swap(a[i], a[j]);
}
}
swap(a[i + 1], a[e]);
return i + 1;
}

void quickSort(int a[], int s, int e, int k) {

if (s < e) {
if (e - s + 1 > k) {
int pi = partition(a, s, e);
quickSort(a, s, pi - 1, k);
quickSort(a, pi + 1, e, k);
} else {
insertionSort(a, s, e);
}
}
}

void printArray(int arr[], int size) {

for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}

int main() {
int n, k;
cout << "Enter the size of the array: ";
cin >> n;
int arr[n];
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "Enter the value of k for switching to insertion sort: ";
cin >> k;
quickSort(arr, 0, n - 1, k);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}

1. Greedy for coin change

include <bits/stdc++.h>
using namespace std;

// All denominations of Indian Currency

int denomination[]
 = { 1, 2, 5, 10, 20, 50, 100, 500, 1000 };

int n = sizeof(denomination) / sizeof(denomination[0]);

void findMin(int V)
{
sort(denomination, denomination + n);

// Initialize result

vector<int> ans;

// Traverse through all denomination

for (int i = n - 1; i >= 0; i--) {

// Find denominations

while (V >= denomination[i]) {

V -= denomination[i];

ans.push_back(denomination[i]);

// Print result

for (int i = 0; i < ans.size(); i++)

cout << ans[i] << " ";

}
O(n)

// C++ program to implement

// Optimal File Merge Pattern
#include <bits/stdc++.h>
using namespace std;

// Function to find minimum computation

int minComputation(int size, int files[])
{

// Create a min heap

priority_queue<int, vector<int>, greater<int> > pq;

for (int i = 0; i < size; i++) {

// Add sizes to priorityQueue

pq.push(files[i]);
}

// Variable to count total Computation

int count = 0;

while (pq.size() > 1) {

 // pop two smallest size element
// from the min heap
int first_smallest = pq.top();
pq.pop();
int second_smallest = pq.top();
pq.pop();

int temp = first_smallest + second_smallest;

// Add the current computations

// with the previous one's
count += temp;

// Add new combined file size

// to priority queue or min heap
pq.push(temp);
}
return count;
}

// Driver code
int main()
{

// No of files
int n = 6;

// 6 files with their sizes

int files[] = { 2, 3, 4, 5, 6, 7 };

// Total no of computations
// do be done final answer
cout << "Minimum Computations = "
<< minComputation(n, files);

return 0;
}
Time 0nlogn