Umang Sonthaliya

1MS21EC127

ECL75- ADVANCED COMPUTATIONAL ALGORITHMS

1. Subarray with given sum

Algorithm:

1. Start with two pointers, start and end, initialized to the beginning of the array.

2. Maintain a variable currentSum to store the sum of elements between the two pointers.

3. Iterate through the array using the end pointer:

o Add the current element to currentSum.

o If currentSum exceeds the target S, move the start pointer to the right until
currentSum is less than or equal to S.

o If currentSum equals S, return the subarray indices.

4. If no such subarray is found, return a message indicating no solution exists.

Code:

#include <iostream>

#include <vector>

using namespace std;

vector<int> subarrayWithGivenSum(vector<int> &arr, int S) {

int start = 0, currentSum = 0;

for (int end = 0; end < arr.size(); end++) {

currentSum += arr[end];

while (currentSum > S && start < end) {

currentSum -= arr[start];

start++;

if (currentSum == S) {

return {start, end};

1
 return {};

int main()
{

vector<int> arr = {1, 2, 3, 7, 5};

int target = 12;

vector<int> result = subarrayWithGivenSum(arr, target);

if (!result.empty()) {

cout << "Subarray found from index " << result[0] << " to " << result[1] << endl;

} else {

cout << "No subarray with the given sum found." << endl;

return 0;

Input and Output:

1. Input
Array: [1, 2, 3, 7, 5]

Target Sum: 12
Output
Subarray found from index 2 to 4

2. Merge Two Sorted Arrays

Algorithm:

1. Use two pointers, i for the first array and j for the second array.

2. Traverse both arrays:

o Compare the current elements of both arrays.

o Append the smaller element to the result array.

o Move the pointer of the smaller element's array forward.

3. Append remaining elements from either array to the result.

4. Return the merged array.

2
 Code:

#include <iostream>

#include <vector>

using namespace std;

vector<int> mergeSortedArrays(vector<int> &arr1, vector<int> &arr2) {

vector<int> mergedArray;

int i = 0, j = 0;

while (i < arr1.size() && j < arr2.size()) {

if (arr1[i] <= arr2[j]) {

mergedArray.push_back(arr1[i++]);

} else {

mergedArray.push_back(arr2[j++]);

while (i < arr1.size()) {

mergedArray.push_back(arr1[i++]);

while (j < arr2.size()) {

mergedArray.push_back(arr2[j++]);

return mergedArray;

int main() {

vector<int> arr1 = {1, 3, 5};

vector<int> arr2 = {2, 4, 6};

vector<int> result = mergeSortedArrays(arr1, arr2);

cout << "Merged Array: ";

for (int num : result) {

cout << num << " ";

cout << endl; return 0; }

3
Input and Output:

Input 1:

Array 1: [1, 3, 5]

Array 2: [2, 4, 6]

Output 1:

Merged Array: 1 2 3 4 5 6

Input 2:

Array 1: [1, 2, 3]

Array 2: [4, 5, 6]

Output 2:

Merged Array: 1 2 3 4 5 6

3. Inversion of Array
Algorithm:

1. Use a modified merge sort:

o Split the array into two halves recursively.

o Count the inversions in the left half, right half, and while merging.

o During merge, count pairs where the left element is greater than the right element.

2. Return the total count of inversions.

Code:

#include <iostream>

#include <vector>

using namespace std;

int mergeAndCount(vector<int> &arr, int left, int mid, int right) {

int i = left, j = mid + 1, k = 0, inversions = 0;

vector<int> temp(right - left + 1);

while (i <= mid && j <= right) {

if (arr[i] <= arr[j]) {

temp[k++] = arr[i++];

} else {

temp[k++] = arr[j++];

4
 inversions += (mid - i + 1);

while (i <= mid) temp[k++] = arr[i++];

while (j <= right) temp[k++] = arr[j++];

for (i = left, k = 0; i <= right; i++, k++) {

arr[i] = temp[k];

return inversions;

int countInversions(vector<int> &arr, int left, int right) {

if (left >= right) return 0;

int mid = left + (right - left) / 2;

int inversions = 0;

inversions += countInversions(arr, left, mid);

inversions += countInversions(arr, mid + 1, right);

inversions += mergeAndCount(arr, left, mid, right);

return inversions;

int main() {

vector<int> arr = {8, 4, 2, 1};

cout << "Number of inversions: " << countInversions(arr, 0, arr.size() - 1) << endl;

return 0;

Input and Output:

Input 1:

Array: [8, 4, 2, 1]

Output 1:

Number of inversions: 6

Input 2:

5
 Array: [3, 1, 2]

Output 2:

Number of inversions: 2

4. Parenthesis Checker
Algorithm:

1. Use a stack to keep track of opening parentheses.

2. Traverse the string:
1. Push opening parentheses ((, {, [) onto the stack.
2. For closing parentheses (), }, ]), check the top of the stack:
3. If the stack is empty or the top doesn't match the closing parenthesis, return
false. Otherwise, pop the stack.
3. After traversal, if the stack is empty, the string is balanced; otherwise, it isn't.

Code:
#include <iostream>

#include <stack>

using namespace std;

bool isBalanced(string s) {

stack<char> st;

for (char c : s) {

if (c == '(' || c == '{' || c == '[') {

st.push(c);

} else {

if (st.empty()) return false;

char top = st.top();

if ((c == ')' && top == '(') ||

(c == '}' && top == '{') ||

(c == ']' && top == '[')) {

st.pop();

} else {

return false;

6
 }

return st.empty();

int main() {

string s = "{[()]}";

cout << (isBalanced(s) ? "Balanced" : "Not Balanced") << endl;

s = "{[(])}";

cout << (isBalanced(s) ? "Balanced" : "Not Balanced") << endl;

return 0;

Input and Output:

Input 1:

String: {[()]}

Output 1:

Balanced

Input 2:

String: {[(])}

Output 2:

Not Balanced

5. Stack Using Two Queues

Algorithm:

1. Use two queues q1 and q2.

2. For push(x):
o Enqueue x to q2.
o Dequeue all elements from q1 and enqueue them to q2.
o Swap q1 and q2.
3. For pop():
o Dequeue an element from q1.
4. For top():
o Return the front element of q1.
5. For isEmpty():
o Check if q1 is empty.

7
Code:

#include <iostream>

#include <queue>

using namespace std;

class StackUsingQueues {

queue<int> q1, q2;

public:

void push(int x) {

q2.push(x);

while (!q1.empty()) {

q2.push(q1.front());

q1.pop();

swap(q1, q2);

void pop() {

if (!q1.empty()) q1.pop();

int top() {

return q1.empty() ? -1 : q1.front();

bool isEmpty() {

return q1.empty();

};

int main() {

StackUsingQueues stack;

stack.push(1);

stack.push(2);

stack.push(3);

cout << "Top element: " << stack.top() << endl;

8
 stack.pop();

cout << "Top element: " << stack.top() << endl;

cout << "Is stack empty? " << (stack.isEmpty() ? "Yes" : "No") << endl;

return 0;

Input and Output:

Input:

Operations: push(1), push(2), push(3), top(), pop(), top()

Output:

Top element: 3

Top element: 2

Is stack empty? No

6. First Non-Repeating Character in a Stream

Algorithm:

1. Use a queue to maintain the order of characters in the stream.

2. Use a map to count the occurrences of each character.

3. For each character in the stream:

o Increment its count in the map.

o Add it to the queue.

o Remove characters from the front of the queue while their count in the map is
greater than 1.

4. The front of the queue represents the first non-repeating character.

Code:

#include <iostream>

#include <queue>

#include <unordered_map>

using namespace std;

9
 void firstNonRepeating(string stream) {

unordered_map<char, int> count;

queue<char> q;

for (char c : stream) {

count[c]++;

q.push(c);

while (!q.empty() && count[q.front()] > 1) {

q.pop();

if (q.empty()) {

cout << "-1 ";

} else {

cout << q.front() << " ";

cout << endl;

int main() {

string stream = "aabc";

firstNonRepeating(stream);

stream = "xyzxyz";

firstNonRepeating(stream);

return 0;

Input and Output:

Input 1:

Stream: aabc

Output 1:

a -1 b b

Input 2:

Stream: xyzxyz

10
 Output 2:

x x x -1 -1 -1

6. Reverse a Linked List

Algorithm:

1. Initialize three pointers: prev as NULL, current as the head, and next as NULL.

2. Traverse the list:

o Store the next node of current in next.

o Change the next pointer of current to point to prev.

o Move prev to current and current to next.

3. When the traversal is complete, set the head to prev.

Code:

#include <iostream>

using namespace std;

struct Node {

int data;

Node* next;

Node(int val) : data(val), next(NULL) {}

};

Node* reverseLinkedList(Node* head) {

Node* prev = NULL;

Node* current = head;

Node* next = NULL;

while (current != NULL) {

next = current->next;

current->next = prev;

prev = current;

current = next;

return prev;

11
void printList(Node* head) {

while (head != NULL) {

cout << head->data << " ";

head = head->next;

cout << endl;

int main() {

Node* head = new Node(1);

head->next = new Node(2);

head->next->next = new Node(3);

head->next->next->next = new Node(4);

cout << "Original List: ";

printList(head);

head = reverseLinkedList(head);

cout << "Reversed List: ";

printList(head);

return 0;

Input and Output:

Input:

List: 1 -> 2 -> 3 -> 4

Output:

Original List: 1 2 3 4

Reversed List: 4 3 2 1

7. Merge Two Sorted Linked Lists

Algorithm:

1. Create a dummy node to serve as the starting point of the merged list.

2. Use a pointer current to track the tail of the merged list.

12
 3. Traverse both lists:

o Compare the current nodes of both lists.

o Append the smaller node to current and move the pointer in that list forward.

4. Append any remaining nodes from either list to the merged list.

5. Return the merged list starting from the node after the dummy node.

Code:

#include <iostream>

using namespace std;

struct Node {

int data;

Node* next;

Node(int val) : data(val), next(NULL) {}

};

Node* mergeSortedLists(Node* l1, Node* l2) {

Node dummy(0);

Node* current = &dummy;

while (l1 != NULL && l2 != NULL) {

if (l1->data <= l2->data) {

current->next = l1;

l1 = l1->next;

} else {

current->next = l2;

l2 = l2->next;

current = current->next;

current->next = (l1 != NULL) ? l1 : l2;

return dummy.next;

13
void printList(Node* head) {

while (head != NULL) {

cout << head->data << " ";

head = head->next;

cout << endl;

int main() {

Node* l1 = new Node(1);

l1->next = new Node(3);

l1->next->next = new Node(5);

Node* l2 = new Node(2);

l2->next = new Node(4);

l2->next->next = new Node(6);

cout << "List 1: ";

printList(l1);

cout << "List 2: ";

printList(l2);

Node* mergedList = mergeSortedLists(l1, l2);

cout << "Merged List: ";

printList(mergedList);

return 0;

Input and Output:

Input:

List 1: 1 -> 3 -> 5

List 2: 2 -> 4 -> 6

Output:

Merged List: 1 2 3 4 5 6

14
8. Check if Linked List is a Palindrome

Algorithm:

1. Use two pointers (slow and fast) to find the middle of the list.

2. Reverse the second half of the list starting from slow.

3. Compare the first half and the reversed second half node by node.

4. If all nodes match, the list is a palindrome; otherwise, it isn't.

Code:

#include <iostream>

using namespace std;

struct Node {

int data;

Node* next;

Node(int val) : data(val), next(NULL) {}

};

Node* reverseList(Node* head) {

Node* prev = NULL;

while (head != NULL) {

Node* next = head->next;

head->next = prev;

prev = head;

head = next;

return prev;

bool isPalindrome(Node* head) {

if (head == NULL || head->next == NULL) return true;

Node *slow = head, *fast = head;

while (fast != NULL && fast->next != NULL) {

slow = slow->next;

15
 fast = fast->next->next;

slow = reverseList(slow);

Node* firstHalf = head;

Node* secondHalf = slow;

while (secondHalf != NULL) {

if (firstHalf->data != secondHalf->data) return false;

firstHalf = firstHalf->next;

secondHalf = secondHalf->next;

return true;

int main() {

Node* head = new Node(1);

head->next = new Node(2);

head->next->next = new Node(2);

head->next->next->next = new Node(1);

cout << (isPalindrome(head) ? "Palindrome" : "Not Palindrome") << endl;

return 0;

Input and Output:

Input:

List: 1 -> 2 -> 2 -> 1

Output:

Palindrome

Input:

List: 1 -> 2 -> 3

Output:

Not Palindrome

16
9. Inorder Traversal of a Binary Tree

Algorithm:

1. Recursively traverse the left subtree.

2. Visit the root node and process it.

3. Recursively traverse the right subtree.

Code:

#include <iostream>

using namespace std;

struct Node {

int data;

Node* left;

Node* right;

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

};

void inorderTraversal(Node* root) {

if (root == NULL) return;

inorderTraversal(root->left);

cout << root->data << " ";

inorderTraversal(root->right);

int main() {

Node* root = new Node(1);

root->left = new Node(2);

root->right = new Node(3);

root->left->left = new Node(4);

root->left->right = new Node(5);

cout << "Inorder Traversal: ";

inorderTraversal(root);

cout << endl;

return 0; }

17
Input and Output:

Input:

Tree:

/\

2 3

/\

4 5

Output:

Inorder Traversal: 4 2 5 1 3

10. Convert Binary Tree to Doubly Linked List

Algorithm:

1. Perform an in-order traversal of the binary tree.

2. Use a pointer to keep track of the previous node in the traversal.

3. Update the left and right pointers of the current node to establish the doubly linked list
connections.

Code:

#include <iostream>

using namespace std;

struct Node {

int data;

Node* left;

Node* right;

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

};

void treeToDoublyLinkedList(Node* root, Node*& head, Node*& prev) {

if (root == NULL) return;

treeToDoublyLinkedList(root->left, head, prev);

18
 if (prev == NULL) {

head = root;

} else {

prev->right = root;

root->left = prev;

prev = root;

treeToDoublyLinkedList(root->right, head, prev);

void printDoublyLinkedList(Node* head) {

while (head != NULL) {

cout << head->data << " ";

head = head->right;

cout << endl;

int main() {

Node* root = new Node(1);

root->left = new Node(2);

root->right = new Node(3);

root->left->left = new Node(4);

root->left->right = new Node(5);

Node* head = NULL;

Node* prev = NULL;

treeToDoublyLinkedList(root, head, prev);

cout << "Doubly Linked List: ";

printDoublyLinkedList(head);

return 0;

19
Input and Output:

Input:

Tree:

/\

2 3

/\

4 5

Output:

Doubly Linked List: 4 2 5 1 3

11. Print Bottom View of a Binary Tree

Algorithm:

1. Perform a level-order traversal using a queue.

2. Keep track of horizontal distances (HDs) from the root:

o Assign HD = 0 to the root, HD - 1 to the left child, and HD + 1 to the right child.

3. Use a map to store the last node seen at each horizontal distance.

4. Print the values in the map sorted by horizontal distance.

Code:

#include <iostream>

#include <queue>

#include <map>

using namespace std;

struct Node {

int data;

Node* left;

Node* right;

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

};

void bottomView(Node* root) {

if (root == NULL) return;

20
 map<int, int> hdMap;

queue<pair<Node*, int>> q;

q.push({root, 0});

while (!q.empty()) {

auto [node, hd] = q.front();

q.pop();

hdMap[hd] = node->data;

if (node->left) q.push({node->left, hd - 1});

if (node->right) q.push({node->right, hd + 1});

for (auto [hd, value] : hdMap) {

cout << value << " ";

cout << endl;

int main() {

Node* root = new Node(1);

root->left = new Node(2);

root->right = new Node(3);

root->left->left = new Node(4);

root->left->right = new Node(5);

root->right->left = new Node(6);

root->right->right = new Node(7);

cout << "Bottom View: ";

bottomView(root);

return 0;

21
Input and Output:

Input:

Tree:

/ \

2 3

/\ /\

4 56 7

Output:

Bottom View: 4 2 6 3 7

12. Heap Sort

Algorithm:

1. Build a max heap from the array.

2. Extract the largest element (root of the heap) and place it at the end of the array.

3. Reduce the heap size and heapify the remaining elements.

4. Repeat until the array is sorted.

Code:
#include <iostream>

#include <vector>

using namespace std;

void heapify(vector<int>& arr, int n, int i) {

int largest = i;

int left = 2 * i + 1;

int right = 2 * i + 2;

if (left < n && arr[left] > arr[largest])

largest = left;

if (right < n && arr[right] > arr[largest])

largest = right;

22
 if (largest != i) {

swap(arr[i], arr[largest]);

heapify(arr, n, largest);

void heapSort(vector<int>& arr) {

int n = arr.size();

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

heapify(arr, n, i);

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

swap(arr[0], arr[i]);

heapify(arr, i, 0);

void printArray(const vector<int>& arr) {

for (int num : arr)

cout << num << " ";

cout << endl;

int main() {

vector<int> arr1 = {4, 10, 3, 5, 1};

vector<int> arr2 = {20, 15, 30, 5, 10, 40}

cout << "Original Array 1: ";

printArray(arr1);

heapSort(arr1);

cout << "Sorted Array 1: ";

printArray(arr1);

cout << "Original Array 2: ";

printArray(arr2);

heapSort(arr2);

cout << "Sorted Array 2: ";

23
 printArray(arr2);

return 0;

Input and Output:

Input 1:

Array: 4, 10, 3, 5, 1

Output 1:

Sorted Array: 1 3 4 5 10

Input 2:

Array: 20, 15, 30, 5, 10, 40

Output 2:

Sorted Array: 5 10 15 20 30 40

13. Relative Sorting

Algorithm:

1. Use a hash map to store the frequency of each element in the first array (arr1), which helps
in tracking how many times each element appears.
2. Iterate through the second array (arr2) and collect the elements from arr1 based on their
order in arr2, inserting each element according to its frequency in arr1.
3. Identify the elements in arr1 that are not present in arr2 and sort these remaining elements
in ascending order.
4. Append the sorted remaining elements to the result array, which already contains the
elements sorted based on the order in arr2.

Code:

#include <iostream>

#include <unordered_map>

#include <vector>

#include <algorithm>

using namespace std;

vector<int> relativeSort(vector<int>& arr1, vector<int>& arr2) {

unordered_map<int, int> freq;

for (int num : arr1)

freq[num]++;

24
 vector<int> result;

for (int num : arr2) {

while (freq[num] > 0) {

result.push_back(num);

freq[num]--;

freq.erase(num);

vector<int> remaining;

for (auto [num, count] : freq)

while (count--)

remaining.push_back(num);

sort(remaining.begin(), remaining.end());

result.insert(result.end(), remaining.begin(), remaining.end());

return result;

void printArray(const vector<int>& arr) {

for (int num : arr)

cout << num << " ";

cout << endl;

int main() {

vector<int> arr1_1 = {2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8};

vector<int> arr2_1 = {2, 1, 8, 3};

vector<int> arr1_2 = {5, 3, 1, 2, 2, 6, 7};

vector<int> arr2_2 = {2, 3};

vector<int> sorted1 = relativeSort(arr1_1, arr2_1);

cout << "Sorted Array 1: ";

printArray(sorted1);

vector<int> sorted2 = relativeSort(arr1_2, arr2_2);

cout << "Sorted Array 2: ";

25
 printArray(sorted2);

return 0;

Input and Output:

Input 1:

Array 1: 2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8

Array 2: 2, 1, 8, 3

Output 1:

Sorted Array: 2 2 1 1 8 8 3 5 6 7 9

Input 2:

Array 1: 5, 3, 1, 2, 2, 6, 7

Array 2: 2, 3

Output 2:

Sorted Array: 2 2 3 1 5 6 7

14. Implement a Priority Queue

Algorithm:

1. Count the frequency of each element in arr1 using an unordered map.

2. Add elements from arr2 to the result based on their frequency in arr1.
3. Insert remaining elements from arr1 (not in arr2) into a min-heap.
4. Append the elements from the min-heap to the result, ensuring the remaining elements are
sorted.

Code:

#include <iostream>

#include <queue>

using namespace std;

int main() {

priority_queue<int> pq;

vector<int> elements1 = {10, 20, 15, 30, 5};

vector<int> elements2 = {40, 25, 35, 10};

26
for (int num : elements1)

pq.push(num);

cout << "Priority Queue after inserting elements 1: ";

while (!pq.empty()) {

cout << pq.top() << " ";

pq.pop();

cout << endl;

for (int num : elements2)

pq.push(num);

cout << "Priority Queue after inserting elements 2: ";

while (!pq.empty()) {

cout << pq.top() << " ";

pq.pop();

cout << endl;

return 0;

Input and Output:

Input 1:

Elements: 10, 20, 15, 30, 5

Output 1:

Priority Queue: 30 20 15 10 5

Input 2:

Elements: 40, 25, 35, 10

Output 2:

Priority Queue: 40 35 25 10

27
15.Implement Hash Table

Algorithm:

1. Define a Hash Table: Create an array of linked lists (or arrays) to store key-value pairs.

2. Hash Function: Define a hash function to map a key to an index in the hash table.

3. Insert Operation: Insert key-value pairs into the hash table by hashing the key and placing
the pair in the corresponding bucket.

4. Search Operation: Search for a key by hashing it and checking the corresponding bucket for
the value.

Code:

#include <iostream>

#include <list>

using namespace std;

class HashTable {

private:

static const int SIZE = 10;

list<pair<int, int>> table[SIZE];

int hashFunction(int key) {

return key % SIZE;

public:

void insert(int key, int value) {

int index = hashFunction(key);

table[index].push_back(make_pair(key, value));

int search(int key) {

int index = hashFunction(key);

for (auto& pair : table[index]) {

if (pair.first == key) {

return pair.second;

28
 return -1;

void display() {

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

if (!table[i].empty()) {

cout << "Index " << i << ": ";

for (auto& pair : table[i]) {

cout << "[" << pair.first << ", " << pair.second << "] ";

cout << endl;

};

int main() {

HashTable ht;

ht.insert(1, 100);

ht.insert(11, 200);

ht.insert(21, 300);

ht.display();

cout << "Value for key 11: " << ht.search(11) << endl;

cout << "Value for key 21: " << ht.search(21) << endl;

cout << "Value for key 5 (not inserted): " << ht.search(5) << endl;

return 0;

Input/Output:

Input 1:

• Insert keys: 1, 11, 21

• Search for keys: 11, 21, 5 (not inserted)

Output 1:

Index 1: [1, 100] [11, 200]

29
Index 0: [21, 300]

Value for key 11: 200

Value for key 21: 300

Value for key 5 (not inserted): -1

Input 2:

• Insert keys: 5, 15, 25

• Search for keys: 15, 5, 10 (not inserted)

Output 2:

Index 5: [5, 100] [15, 200]

Index 5: [25, 300]

Value for key 15: 200

Value for key 5: 100

Value for key 10 (not inserted): -1

16. Sorting Elements of an Array by Frequency

Algorithm:

1. Count Frequencies: Traverse the array and count the frequency of each element using a
simple array or a frequency counter array.

2. Group Elements by Frequency: Store elements with the same frequency together.

3. Sort by Frequency: Sort the elements first by frequency in descending order, and in case of
ties, by element value in ascending order.

4. Rebuild Sorted Array: Rebuild the array based on sorted frequencies and element values.

Code:

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

void sortByFrequency(vector<int>& arr) {

int n = arr.size();

vector<int> freq(101, 0);

30
 for (int num : arr)

freq[num]++;

vector<pair<int, int>> freqVec;

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

if (freq[i] > 0) {

freqVec.push_back({i, freq[i]});

sort(freqVec.begin(), freqVec.end(), [](pair<int, int>& a, pair<int, int>& b) {

if (a.second == b.second)

return a.first < b.first;

return a.second > b.second;

});

arr.clear();

for (auto& p : freqVec) {

for (int i = 0; i < p.second; i++) {

arr.push_back(p.first);

void printArray(const vector<int>& arr) {

for (int num : arr)

cout << num << " ";

cout << endl;

int main() {

vector<int> arr1 = {3, 3, 3, 2, 2, 1};

vector<int> arr2 = {4, 5, 6, 6, 5, 4, 4};

cout << "Original Array 1: ";

printArray(arr1);

sortByFrequency(arr1);

31
 cout << "Sorted Array 1 by Frequency: ";

printArray(arr1);

cout << "Original Array 2: ";

printArray(arr2);

sortByFrequency(arr2);

cout << "Sorted Array 2 by Frequency: ";

printArray(arr2);

return 0;

Input and Output:

Input 1:

Array: 3, 3, 3, 2, 2, 1

Output 1:

Sorted Array: 3 3 3 2 2 1

Input 2:

Array: 4, 5, 6, 6, 5, 4, 4

Output 2:

Sorted Array: 4 4 4 5 5 6 6

17. Longest Consecutive Subsequence

Algorithm:

1. Sort the Array: First, sort the array to bring consecutive elements together.

2. Find Consecutive Sequences: Traverse the sorted array and keep track of the longest
subsequence where consecutive numbers appear.

3. Check Consecutive Numbers: For each number, check if the next number is consecutive (i.e.,
num + 1).

4. Track Maximum Length: Track the length of the current consecutive subsequence and
update the maximum length.

Code:

#include <iostream>

#include <vector>

32
#include <algorithm>

using namespace std;

int longestConsecutiveSubsequence(vector<int>& arr) {

if (arr.empty()) return 0;

sort(arr.begin(), arr.end());

int longest = 1, current_len = 1;

for (int i = 1; i < arr.size(); i++) {

if (arr[i] == arr[i - 1]) continue; // Skip duplicates

if (arr[i] == arr[i - 1] + 1) {

current_len++;

} else {

longest = max(longest, current_len);

current_len = 1;

longest = max(longest, current_len);

return longest;

int main() {

vector<int> arr1 = {100, 4, 200, 1, 3, 2};

vector<int> arr2 = {10, 5, 1, 3, 9, 2};

cout << "Longest Consecutive Subsequence Length (Array 1): "

<< longestConsecutiveSubsequence(arr1) << endl;

cout << "Longest Consecutive Subsequence Length (Array 2): "

<< longestConsecutiveSubsequence(arr2) << endl;

return 0;

Input and Output:

Input 1:

Array: 100, 4, 200, 1, 3, 2

Output 1:

33
Longest Consecutive Subsequence Length: 4

Input 2:

Array: 10, 5, 1, 3, 9, 2

Output 2:

Longest Consecutive Subsequence Length: 3

18. Check if Two Arrays are Equal or Not

Algorithm:

1. Check Length: First, check if the arrays have the same length.

2. Sort Both Arrays: Sort both arrays.

3. Compare Elements: Compare each element of both sorted arrays.

4. Return Result: If all elements are equal, return true; otherwise, return false.

Code:

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

bool areArraysEqual(vector<int>& arr1, vector<int>& arr2) {

if (arr1.size() != arr2.size()) return false;

sort(arr1.begin(), arr1.end());

sort(arr2.begin(), arr2.end());

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

if (arr1[i] != arr2[i]) return false;

return true;

int main() {

vector<int> arr1 = {1, 2, 3, 4, 5};

vector<int> arr2 = {5, 4, 3, 2, 1};

vector<int> arr3 = {1, 2, 3, 6};

34
 cout << "Are Array 1 and Array 2 equal? "

<< (areArraysEqual(arr1, arr2) ? "Yes" : "No") << endl;

cout << "Are Array 1 and Array 3 equal? "

<< (areArraysEqual(arr1, arr3) ? "Yes" : "No") << endl;

return 0;

Input and Output:

Input 1:

Array 1: 1, 2, 3, 4, 5

Array 2: 5, 4, 3, 2, 1

Output 1:

Are Arrays equal? Yes

Input 2:

Array 1: 1, 2, 3, 4, 5

Array 3: 1, 2, 3, 6

Output 2:

Are Arrays equal? No

19. Quick Sort

Algorithm:

1. Choose a Pivot: Select a pivot element from the array. Typically, the last element is chosen as
the pivot.

2. Partition the Array: Rearrange the array so that elements less than the pivot are on the left
and elements greater than the pivot are on the right.

3. Recursively Apply Quick Sort: Recursively apply the quick sort on the left and right sub-
arrays formed by the partition.

4. Base Case: If the sub-array has one or zero elements, it's already sorted.

Code:

#include <iostream>

#include <vector>

35
using namespace std;

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

int pivot = arr[high];

int i = low - 1;

for (int j = low; j < high; 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);

void printArray(const vector<int>& arr) {

for (int num : arr)

cout << num << " ";

cout << endl;

int main() {

vector<int> arr1 = {10, 7, 8, 9, 1, 5};

vector<int> arr2 = {12, 11, 13, 5, 6, 7};

cout << "Original Array 1: ";

printArray(arr1);

quickSort(arr1, 0, arr1.size() - 1);

36
 cout << "Sorted Array 1: ";

printArray(arr1);

cout << "Original Array 2: ";

printArray(arr2);

quickSort(arr2, 0, arr2.size() - 1);

cout << "Sorted Array 2: ";

printArray(arr2);

return 0;

Input and Output for Quick Sort:

Input 1:

Array: 10, 7, 8, 9, 1, 5

Output 1:

Sorted Array: 1 5 7 8 9 10

Input 2:

Array: 12, 11, 13, 5, 6, 7

Output 2:

Sorted Array: 5 6 7 11 12 13

20. Insertion Sort

Algorithm:

1. Start from the Second Element: Consider the second element in the array as the key.

2. Compare and Shift: Compare the key with the element before it and shift all greater
elements one position to the right.

3. Insert the Key: Insert the key at its correct position in the sorted part of the array.

4. Repeat for All Elements: Repeat this process for all elements until the entire array is sorted.

Code:

#include <iostream>

#include <vector>

using namespace std;

37
void insertionSort(vector<int>& arr) {

int n = arr.size();

for (int i = 1; i < n; i++) {

int key = arr[i];

int j = i - 1;

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];

j = j - 1;

arr[j + 1] = key;

void printArray(const vector<int>& arr) {

for (int num : arr)

cout << num << " ";

cout << endl;

int main() {

vector<int> arr1 = {12, 11, 13, 5, 6};

vector<int> arr2 = {5, 9, 2, 8, 1, 3};

cout << "Original Array 1: ";

printArray(arr1);

insertionSort(arr1);

cout << "Sorted Array 1: ";

printArray(arr1);

cout << "Original Array 2: ";

printArray(arr2);

insertionSort(arr2);

cout << "Sorted Array 2: ";

printArray(arr2);

38
 return 0;

Input and Output for Insertion Sort:

Input 1:

Array: 12, 11, 13, 5, 6

Output 1:

Sorted Array: 5 6 11 12 13

Input 2:

Array: 5, 9, 2, 8, 1, 3

Output 2:

Sorted Array: 1 2 3 5 8 9

21. Merge Sort

Algorithm:

1. Divide the Array: Recursively divide the array into two halves until each sub-array contains a
single element.

2. Merge Sub-arrays: Merge the sub-arrays by comparing their elements and placing the
smaller element first.

3. Repeat the Merge: Continue the merging process until all sub-arrays are merged into a single
sorted array.

4. Base Case: When the sub-array has only one element, it is already sorted.

Code:

#include <iostream>

#include <vector>

using namespace std;

void merge(vector<int>& arr, int left, int mid, int right) {

int n1 = mid - left + 1;

int n2 = right - mid;

vector<int> leftArr(n1), rightArr(n2);

for (int i = 0; i < n1; i++)

leftArr[i] = arr[left + i];

39
 for (int i = 0; i < n2; i++)

rightArr[i] = arr[mid + 1 + i];

int i = 0, j = 0, k = left;

while (i < n1 && j < n2) {

if (leftArr[i] <= rightArr[j]) {

arr[k] = leftArr[i];

i++;

} else {

arr[k] = rightArr[j];

j++;

k++;

while (i < n1) {

arr[k] = leftArr[i];

i++;

k++;

while (j < n2) {

arr[k] = rightArr[j];

j++;

k++;

void mergeSort(vector<int>& arr, int left, int right) {

if (left < right) {

int mid = left + (right - left) / 2;

mergeSort(arr, left, mid);

mergeSort(arr, mid + 1, right);

merge(arr, left, mid, right);

40
 }

void printArray(const vector<int>& arr) {

for (int num : arr)

cout << num << " ";

cout << endl;

int main() {

vector<int> arr1 = {38, 27, 43, 3, 9, 82, 10};

vector<int> arr2 = {12, 11, 13, 5, 6};

cout << "Original Array 1: ";

printArray(arr1);

mergeSort(arr1, 0, arr1.size() - 1);

cout << "Sorted Array 1: ";

printArray(arr1);

cout << "Original Array 2: ";

printArray(arr2);

mergeSort(arr2, 0, arr2.size() - 1);

cout << "Sorted Array 2: ";

printArray(arr2);

return 0;

Input and Output for Merge Sort:

Input 1:

Array: 38, 27, 43, 3, 9, 82, 10

Output 1:

Sorted Array: 3 9 10 27 38 43 82

Input 2:

Array: 12, 11, 13, 5, 6

Output 2:

Sorted Array: 5 6 11 12 13

41
22. Fibonacci Sequence
Without Using Memo Table (Recursion):

Algorithm:

1. Base Cases: If n == 0, return 0, and if n == 1, return 1.

2. Recursive Calls: For any other value of n, return the sum of the Fibonacci numbers for n-1
and n-2.

3. Repeat: Keep calling the function recursively until reaching the base cases.

Code:

#include <iostream>

using namespace std;

int fibonacci(int n) {

if (n <= 1)

return n;

return fibonacci(n - 1) + fibonacci(n - 2);

int main() {

int n1 = 6;

int n2 = 10;

cout << "Fibonacci of " << n1 << ": " << fibonacci(n1) << endl;

cout << "Fibonacci of " << n2 << ": " << fibonacci(n2) << endl;

return 0;

Input and Output:

Input:

Fibonacci of 6 and 10

Output:

Fibonacci of 6: 8

Fibonacci of 10: 55

42
With Memo Table (Memoization):

Algorithm:

1. Base Cases: If n == 0, return 0, and if n == 1, return 1.

2. Memoization: Store previously computed Fibonacci values in an array or vector to avoid

redundant calculations.

3. Recursive Calls: For any other value of n, if it has already been computed, return the stored
value; otherwise, compute it and store it.

Code:

#include <iostream>

#include <vector>

using namespace std;

int fibonacci(int n, vector<int>& dp) {

if (n <= 1)

return n;

if (dp[n] != -1)

return dp[n];

dp[n] = fibonacci(n - 1, dp) + fibonacci(n - 2, dp);

return dp[n];

int main() {

int n1 = 6;

int n2 = 10;

vector<int> dp1(n1 + 1, -1);

vector<int> dp2(n2 + 1, -1);

cout << "Fibonacci of " << n1 << ": " << fibonacci(n1, dp1) << endl;

cout << "Fibonacci of " << n2 << ": " << fibonacci(n2, dp2) << endl;

return 0;

Input and Output:

Input:

Fibonacci of 6 and 10

43
Output:

Fibonacci of 6: 8

Fibonacci of 10: 55

23. Tower of Hanoi Problem

Algorithm:

1. Base Case: If there is only one disk, move it from the source rod to the destination rod.

2. Recursive Case: Move n-1 disks from the source to the auxiliary rod, then move the nth disk
to the destination rod, and finally move the n-1 disks from the auxiliary rod to the
destination rod.

Code:

#include <iostream>

using namespace std;

void towerOfHanoi(int n, char source, char auxiliary, char destination) {

if (n == 1) {

cout << "Move disk 1 from " << source << " to " << destination << endl;

return;

towerOfHanoi(n - 1, source, destination, auxiliary);

cout << "Move disk " << n << " from " << source << " to " << destination << endl;

towerOfHanoi(n - 1, auxiliary, source, destination);

int main() {

int n1 = 3;

int n2 = 4;

cout << "Tower of Hanoi for " << n1 << " disks:" << endl;

towerOfHanoi(n1, 'A', 'B', 'C')

cout << "\nTower of Hanoi for " << n2 << " disks:" << endl;

towerOfHanoi(n2, 'A', 'B', 'C');

return 0;

44
Input and Output (Tower of Hanoi):

Input:

Tower of Hanoi for 3 disks and 4 disks

Output:

Tower of Hanoi for 3 disks:

Move disk 1 from A to C

Move disk 2 from A to B

Move disk 1 from C to B

Move disk 3 from A to C

Move disk 1 from B to A

Move disk 2 from B to C

Move disk 1 from A to C

Tower of Hanoi for 4 disks:

Move disk 1 from A to D

Move disk 2 from A to B

Move disk 1 from D to B

Move disk 3 from A to C

Move disk 1 from B to A

Move disk 2 from B to C

Move disk 1 from A to C

Move disk 4 from A to D

Move disk 1 from C to B

Move disk 2 from C to D

Move disk 1 from B to D

Move disk 3 from C to B

Move disk 1 from D to C

Move disk 2 from D to B

Move disk 1 from C to B

45