Advance Algorithmic & Problem Solving

Course Code: R1UC601B

Lab File
For
BACHELOR OF

ENGINEERING & TECHNOLOGY

SCHOOL OF COMPUTER SCIENCE AND ENGINEERING

GALGOTIAS UNIVERSITY, GREATER NOIDA

UTTAR PRADESH

Student Name: Ansh Tripathi

Admission No: 22SCSE1011726
Semester : VI

1|P a g e
 PROBLEM NO. : 1

AIM : WAP Missing number in array, Rotate Bits, Power of 2, Bit-Difference

PROGRAM :
#include <iostream>
#include <cmath>
using namespace std;

// Function to find the missing number in an array

int findMissingNumber(int arr[], int size) {
int total = (size + 1) * (size + 2) / 2;
for (int i = 0; i < size; i++)
total -= arr[i];
return total;
}

// Function to rotate bits to the left

unsigned int rotateLeft(unsigned int n, unsigned int d) {
return (n << d) | (n >> (32 - d));
}

// Function to rotate bits to the right

unsigned int rotateRight(unsigned int n, unsigned int d) {
return (n >> d) | (n << (32 - d));
}

// Function to check if a number is a power of 2

bool isPowerOfTwo(int n) {
return (n && !(n & (n - 1)));
}

// Function to calculate the bit difference between two numbers

int bitDifference(int a, int b) {
int x = a ^ b;
int count = 0;
while (x) {
count += x & 1;
x >>= 1;
}
return count;
}

int main() {
// Part 1: Missing Number in Array

2|P a g e
 int arr[] = {1, 2, 4, 5, 6};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Missing number: " << findMissingNumber(arr, size) << endl;

// Part 2: Rotate Bits

unsigned int n = 16; // 0001 0000
unsigned int d = 2;
cout << "Left Rotation of " << n << " by " << d << " is " << rotateLeft(n, d)
<< endl;
cout << "Right Rotation of " << n << " by " << d << " is " << rotateRight(n,
d) << endl;

// Part 3: Power of 2
int number = 16;
if (isPowerOfTwo(number))
cout << number << " is a power of 2." << endl;
else
cout << number << " is not a power of 2." << endl;

// Part 4: Bit Difference

int a = 10, b = 20;
cout << "Bit Difference between " << a << " and " << b << " is " <<
bitDifference(a, b) << endl;

return 0;
}

OUTPUT :

3|P a g e
 PROBLEM NO. : 2

AIM : WAP Set kth bit, Toggle bits given range, Find first set bit, Check whether
K-th bit is set, Rightmost different bit

PROGRAM :

#include <iostream>
#include <cmath>
using namespace std;

// Function to set the k-th bit

int setKthBit(int n, int k) {
return (n | (1 << k));
}

// Function to toggle bits in a given range [l, r]

int toggleBitsInRange(int n, int l, int r) {
int num = ((1 << (r - l + 1)) - 1) << (l - 1);
return n ^ num;
}

// Function to find the first set bit

int findFirstSetBit(int n) {
return log2(n & -n) + 1;
}

// Function to check whether the k-th bit is set

bool isKthBitSet(int n, int k) {
return (n & (1 << k)) != 0;
}

// Function to find the rightmost different bit

int rightmostDifferentBit(int m, int n) {
return log2((m ^ n) & -(m ^ n)) + 1;
}

int main() {
// Part 1: Set K-th Bit
int n = 5, k = 1;
cout << "Number after setting " << k << "th bit: " << setKthBit(n, k) <<
endl;

4|P a g e
 // Part 2: Toggle Bits Given Range
n = 50; // 110010
int l = 2, r = 5;
cout << "Number after toggling bits from " << l << " to " << r << " is " <<
toggleBitsInRange(n, l, r) << endl;

// Part 3: Find First Set Bit

n = 18; // 10010
cout << "First set bit is at position " << findFirstSetBit(n) << endl;

// Part 4: Check Whether K-th Bit is Set

n = 5; // 0101
k = 2;
if (isKthBitSet(n, k))
cout << "The " << k << "th bit is set." << endl;
else
cout << "The " << k << "th bit is not set." << endl;

// Part 5: Rightmost Different Bit

int m = 11, b = 9; // 1011, 1001
cout << "Rightmost different bit is at position " << rightmostDifferentBit(m,
b) << endl;

return 0;
}

OUTPUT :

5|P a g e
 PROBLEM NO. :3

AIM : WAP Detecting Duplicates in Array, Finding Unique element in Array, Finding Maximum
XOR Subarray, Longest Consecutive 1's (Hamming Weight)

PROGRAM :
#include <iostream>
#include <unordered_set>
#include <vector>
#include <algorithm>
using namespace std;

// Function to detect duplicates in an array

bool hasDuplicates(int arr[], int size) {
unordered_set<int> seen;
for (int i = 0; i < size; i++) {
if (seen.find(arr[i]) != seen.end()) {
return true;
}
seen.insert(arr[i]);
}
return false;
}
// Function to find the unique element in an array where every element except one
appears twice
int findUniqueElement(int arr[], int size) {
int unique = 0;
for (int i = 0; i < size; i++) {
unique ^= arr[i];
}
return unique;
}
// Function to find the maximum XOR subarray
int maxXORSubarray(vector<int>& nums) {
int max_xor = 0, curr_xor = 0;
unordered_set<int> prefixes;
prefixes.insert(0);
for (int num : nums) {
curr_xor ^= num;
for (int prefix : prefixes) {
max_xor = max(max_xor, curr_xor ^ prefix);
}
prefixes.insert(curr_xor);
}
return max_xor;
}

6|P a g e
 // Function to find the longest consecutive 1's (Hamming weight)
int longestConsecutiveOnes(int n) {
int max_count = 0, count = 0;
while (n) {
if (n & 1) {
count++;
max_count = max(max_count, count);
} else {
count = 0;
}
n >>= 1;
}
return max_count;
}
int main() {
// Part 1: Detecting Duplicates in Array
int arr1[] = {1, 2, 3, 4, 5, 3};
int size1 = sizeof(arr1) / sizeof(arr1[0]);
if (hasDuplicates(arr1, size1))
cout << "Array has duplicates." << endl;
else
cout << "Array has no duplicates." << endl;

// Part 2: Finding Unique Element in Array

int arr2[] = {1, 2, 3, 4, 3, 2, 1};
int size2 = sizeof(arr2) / sizeof(arr2[0]);
cout<<"Unique element in the array is:"<<findUniqueElement(arr2,size2)<<endl;

// Part 3: Finding Maximum XOR Subarray

vector<int> nums = {8, 1, 2, 12, 7, 6};
cout << "Maximum XOR of any subarray is: " << maxXORSubarray(nums) << endl;

// Part 4: Longest Consecutive 1's (Hamming Weight)

int n = 222; // Binary representation is 11011110
cout << "Longest consecutive 1's in binary representation of " << n << " is:
" << longestConsecutiveOnes(n) << endl;
return 0;
}

OUTPUT :

7|P a g e
 PROBLEM NO. :4

AIM : WAP Swap all odd and even bits/ Detecting Parity Bits, Generate all subsets of a given set
using bitwise operations.

PROGRAM :

#include <iostream>
#include <vector>
using namespace std;

// Function to swap all odd and even bits

unsigned int swapOddEvenBits(unsigned int n) {
unsigned int even_bits = n & 0xAAAAAAAA; // Get all even bits of n
unsigned int odd_bits = n & 0x55555555; // Get all odd bits of n
even_bits >>= 1; // Right shift even bits
odd_bits <<= 1; // Left shift odd bits
return (even_bits | odd_bits); // Combine even and odd bits
}

// Function to detect the parity of a number

bool detectParity(int n) {
bool parity = false;
while (n) {
parity = !parity;
n = n & (n - 1);
}
return parity;
}

// Function to generate all subsets of a given set using bitwise operations

void generateSubsets(vector<int>& set) {
int n = set.size();
int subset_count = 1 << n; // Total subsets is 2^n

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

cout << "{ ";
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
cout << set[j] << " ";
}
}
cout << "}" << endl;
}
}

8|P a g e
 int main() {
// Part 1: Swap all odd and even bits
unsigned int n = 23; // Binary: 00010111
cout << "Original number: " << n << endl;
cout << "Number after swapping odd and even bits: " << swapOddEvenBits(n) <<
endl;

// Part 2: Detecting Parity Bits

int num = 7; // Binary: 0111 (Odd parity)
cout << "The parity of " << num << " is " << (detectParity(num) ? "odd." :
"even.") << endl;

// Part 3: Generate all subsets of a given set using bitwise operations

vector<int> set = {1, 2, 3};
cout << "Subsets of the given set are: " << endl;
generateSubsets(set);

return 0;
}

OUTPUT :

9|P a g e
 PROBLEM NO. :5
AIM : WAP to find the Kth largest elements in an array, Move all zeroes to end of array, Rearrange
array such that even positioned are greater than odd.

PROGRAM :
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

// Function to find the Kth largest element in an array

int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> minHeap;
for (int num : nums) {
minHeap.push(num);
if (minHeap.size() > k) {
minHeap.pop();
}
}
return minHeap.top();
}

// Function to move all zeroes to the end of the array

void moveZeroesToEnd(vector<int>& nums) {
int index = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != 0) {
swap(nums[index++], nums[i]);
}
}
}

// Function to rearrange array such that even positioned elements are greater
than odd positioned elements
void rearrangeArray(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<int> result(nums.size());
int n = nums.size();
int left = 0, right = (n + 1) / 2;
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
result[i] = nums[left++];
} else {
result[i] = nums[right++];
}

10 | P a g e
 }
nums = result;
}

int main() {
// Example array
vector<int> arr = {3, 2, 1, 5, 6, 4, 0, 0, 3, 7};

// Part 1: Find the Kth largest element

int k = 3;
cout << "The " << k << "rd largest element is " << findKthLargest(arr, k) <<
endl;

// Part 2: Move all zeroes to end of array

moveZeroesToEnd(arr);
cout << "Array after moving all zeroes to the end: ";
for (int num : arr) {
cout << num << " ";
}
cout << endl;

// Part 3: Rearrange array such that even positioned elements are greater
than odd positioned elements
rearrangeArray(arr);
cout << "Array after rearrangement: ";
for (int num : arr) {
cout << num << " ";
}
cout << endl;

return 0;
}

OUTPUT :

11 | P a g e
 PROBLEM NO. :6

AIM : WAP to Rearrange an array in maximum minimum form using Two Pointer Technique,
Segregate even and odd numbers, Print All Distinct Elements of a given integer array.

PROGRAM :
#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

// Function to rearrange an array in maximum minimum form using Two Pointer

Technique
void rearrangeMaxMin(vector<int>& arr) {
int n = arr.size();
vector<int> result(n);
int left = 0, right = n - 1;
bool flag = true;

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

if (flag) {
result[i] = arr[right--];
} else {
result[i] = arr[left++];
}
flag = !flag;
}
arr = result;
}
// Function to segregate even and odd numbers
void segregateEvenOdd(vector<int>& arr) {
int left = 0, right = arr.size() - 1;
while (left < right) {
while (arr[left] % 2 == 0 && left < right)
left++;
while (arr[right] % 2 == 1 && left < right)
right--;
if (left < right) {
swap(arr[left], arr[right]);
left++;
right--;
}
}
}
// Function to print all distinct elements of a given integer array

12 | P a g e
 void printDistinctElements(const vector<int>& arr) {
unordered_set<int> seen;
for (int num : arr) {
if (seen.find(num) == seen.end()) {
cout << num << " ";
seen.insert(num);
}
}
cout << endl;
}
int main() {
// Example array
vector<int> arr = {1, 3, 5, 2, 8, 7, 6, 4};
// Part 1: Rearrange in maximum minimum form
sort(arr.begin(), arr.end()); // Sort array first
rearrangeMaxMin(arr);
cout << "Array in maximum minimum form: ";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
// Part 2: Segregate even and odd numbers
vector<int> arr2 = {12, 34, 45, 9, 8, 90, 3};
segregateEvenOdd(arr2);
cout << "Array after segregating even and odd numbers: ";
for (int num : arr2) {
cout << num << " ";
}
cout << endl;
// Part 3: Print all distinct elements of a given integer array
vector<int> arr3 = {4, 5, 4, 5, 6, 7, 8, 6, 7, 8};
cout << "Distinct elements in the array: ";
printDistinctElements(arr3);

return 0;
}

OUTPUT :

13 | P a g e
 PROBLEM NO. :7

AIM : WAP to find sub-array with given sum, Reorder an array according to given indexes, Search an
element in a sorted and rotated array

PROGRAM :
#include <iostream>
#include <vector>
using namespace std;
// Function to find a sub-array with a given sum
bool findSubarrayWithGivenSum(vector<int>& arr, int sum) {
int current_sum = arr[0], start = 0;
for (int i = 1; i <= arr.size(); i++) {
while (current_sum > sum && start < i - 1) {
current_sum -= arr[start];
start++;
}
if (current_sum == sum) {
cout <<"Sub-array found from index "<< start <<" to "<< i – 1 <<endl;
return true;
}
if (i < arr.size()) {
current_sum += arr[i];
}
}
cout << "No sub-array with given sum found." << endl;
return false;
}
// Function to reorder an array according to given indexes
void reorderArray(vector<int>& arr, vector<int>& indexes) {
vector<int> temp(arr.size());
for (int i = 0; i < arr.size(); i++) {
temp[indexes[i]] = arr[i];
}
for (int i = 0; i < arr.size(); i++) {
arr[i] = temp[i];
}
}
// Function to search an element in a sorted and rotated array
int searchInSortedRotatedArray(vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}

14 | P a g e
 if (arr[left] <= arr[mid]) {
if (target >= arr[left] && target < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (target > arr[mid] && target <= arr[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
int main() {
// Part 1: Find sub-array with given sum
vector<int> arr1 = {1, 4, 20, 3, 10, 5};
int sum = 33;
findSubarrayWithGivenSum(arr1, sum);
// Part 2: Reorder an array according to given indexes
vector<int> arr2 = {50, 40, 70, 60, 90};
vector<int> indexes = {3, 0, 4, 1, 2};
reorderArray(arr2, indexes);
cout << "Reordered array: ";
for (int num : arr2) {
cout << num << " ";
}cout << endl;
// Part 3: Search an element in a sorted and rotated array
vector<int> arr3 = {4, 5, 6, 7, 0, 1, 2};
int target = 6;
int index = searchInSortedRotatedArray(arr3, target);
if (index != -1) {
cout << "Element " << target << " found at index " << index << endl;
} else {
cout << "Element " << target << " not found in the array." << endl;
}
return 0;
}

OUTPUT :

15 | P a g e
 PROBLEM NO. :8

AIM : WAP to find the Rotation Count in Rotated Sorted array, Find the smallest missing number,
Merge two sorted arrays with O(1) extra space.

PROGRAM :
#include <iostream>
using namespace std;

// Function to find the rotation count in a rotated sorted array

int rotationCount(int arr[], int n) {
int low = 0, high = n - 1;
while (low <= high) {
if (arr[low] <= arr[high]) return low;
int mid = (low + high) / 2;
int next = (mid + 1) % n;
int prev = (mid - 1 + n) % n;
if (arr[mid] <= arr[next] && arr[mid] <= arr[prev])
return mid;
else if (arr[mid] <= arr[high])
high = mid - 1;
else if (arr[mid] >= arr[low])
low = mid + 1;
}
return -1; // Array not rotated
}

// Function to find the smallest missing number in a sorted array

int smallestMissing(int arr[], int n) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] != mid + 1 && (mid == 0 || arr[mid - 1] == mid))
return mid + 1;
else if (arr[mid] == mid + 1)
low = mid + 1;
else
high = mid - 1;
}
return -1; // No missing number found
}
// Function to merge two sorted arrays with O(1) extra space
void mergeArrays(int arr1[], int arr2[], int n, int m) {
for (int i = m - 1; i >= 0; i--) {
int j, last = arr1[n - 1];
for (j = n - 2; j >= 0 && arr1[j] > arr2[i]; j--)

16 | P a g e
 arr1[j + 1] = arr1[j];
if (j != n - 2 || last > arr2[i]) {
arr1[j + 1] = arr2[i];
arr2[i] = last;
}
}
}
int main() {
// Rotation Count in Rotated Sorted Array
int arr[] = {7, 9, 11, 12, 5};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Rotation count: " << rotationCount(arr, n) << endl;

// Smallest Missing Number

int arr_missing[] = {0, 1, 2, 4, 5, 6, 7, 8};
int m = sizeof(arr_missing) / sizeof(arr_missing[0]);
cout << "Smallest missing number: " << smallestMissing(arr_missing, m) <<
endl;
// Merge Two Sorted Arrays with O(1) Extra Space
int arr1[] = {1, 5, 9, 10, 15, 20};
int arr2[] = {2, 3, 8, 13};
int n_merge = sizeof(arr1) / sizeof(arr1[0]);
int m_merge = sizeof(arr2) / sizeof(arr2[0]);
mergeArrays(arr1, arr2, n_merge, m_merge);

cout << "Merged array 1: ";

for (int i = 0; i < n_merge; i++)
cout << arr1[i] << " ";
cout << endl;

cout << "Merged array 2: ";

for (int i = 0; i < m_merge; i++)
cout << arr2[i] << " ";
cout << endl;
return 0;
}

OUTPUT :

17 | P a g e
 PROBLEM NO. :9

AIM : WAP Mean of Array using Recursion, Sum of natural numbers using recursion, Decimal to
binary number using recursion.

PROGRAM :
#include <bits/stdc++.h>
using namespace std;
double arrayMean(const vector<int>& arr, int n, int sum = 0) {
if (n == 0)
return sum / static_cast<double>(arr.size());
else
return arrayMean(arr, n - 1, sum + arr[n - 1]);
}
int sumOfNaturalNumbers(int n) {
if (n == 0)
return 0;
else
return n + sumOfNaturalNumbers(n - 1);
}
long long decimalToBinary(int n) {
if (n == 0)
return 0;
else
return (n % 2) + 10 * decimalToBinary(n / 2);
}
int main() {
// Mean of Array using Recursion
vector<int> arr = {1, 2, 3, 4, 5};
cout << "Mean of array: " << arrayMean(arr, arr.size()) << endl;
// Sum of natural numbers using recursion
int n = 5;
cout<<"Sum of natural numbers up to"<< n<<": "<<sumOfNaturalNumbers(n)<<endl;
// Decimal to binary number using recursion
int decimal = 10;
cout<<"Binary representation of"<<decimal<<":"<<decimalToBinary(decimal)<<endl;
return 0;
}

OUTPUT :

18 | P a g e
 PROBLEM NO. :10

AIM : Program for length of a string using recursion, Sum of digit of a number using recursion, Tail
recursion to calculate sum of array elements. Program to print first n Fibonacci Numbers

PROGRAM :
#include <iostream>
#include <string>
#include <vector>
using namespace std;

// Function to calculate the length of a string using recursion

int stringLength(const string& str, int index = 0) {
if (str[index] == '\0')
return index;
else
return stringLength(str, index + 1);
}

// Function to calculate the sum of digits of a number using recursion

int sumOfDigits(int n) {
if (n == 0)
return 0;
else
return n % 10 + sumOfDigits(n / 10);
}

// Tail-recursive function to calculate the sum of array elements

int arraySumTail(const vector<int>& arr, int index, int sum = 0) {
if (index < 0)
return sum;
else
return arraySumTail(arr, index - 1, sum + arr[index]);
}

// Function to print the first n Fibonacci numbers

void printFibonacci(int n, int a = 0, int b = 1) {
if (n > 0) {
cout << a << " ";
printFibonacci(n - 1, b, a + b);
}
}

int main() {
// Length of a string using recursion
string str = "Hello, world!";

19 | P a g e
 cout << "Length of string: " << stringLength(str) << endl;

// Sum of digits of a number using recursion

int num = 12345;
cout << "Sum of digits of " << num << ": " << sumOfDigits(num) << endl;

// Tail-recursion to calculate the sum of array elements

vector<int> arr = {1, 2, 3, 4, 5};
cout << "Sum of array elements: " << arraySumTail(arr, arr.size() - 1) <<
endl;

// Printing the first n Fibonacci numbers

int n = 10;
cout << "First " << n << " Fibonacci numbers: ";
printFibonacci(n);

return 0;
}

OUTPUT :

20 | P a g e
 PROBLEM NO. :11

AIM : WAP to Sort the Queue using Recursion, Reversing a queue using recursion, Delete a linked
list using recursion

PROGRAM :
#include <iostream>
#include <queue>
using namespace std;

// Function to insert an element at the bottom of a queue

void insertAtBottom(queue<int>& q, int item) {
if (q.empty())
q.push(item);
else {
int temp = q.front();
q.pop();
insertAtBottom(q, item);
q.push(temp);
}
}

// Function to reverse a queue using recursion

void reverseQueue(queue<int>& q) {
if (!q.empty()) {
int temp = q.front();
q.pop();
reverseQueue(q);
insertAtBottom(q, temp);
}
}

// Function to sort a queue using recursion

void sortQueue(queue<int>& q) {
if (q.size() <= 1)
return;

// Move the elements smaller than pivot to left side of the queue and
// larger elements to right side using a pivot
int pivot = q.front();
q.pop();
queue<int> left, right;

while (!q.empty()) {
int curr = q.front();
q.pop();

21 | P a g e
 if (curr < pivot)
left.push(curr);
else
right.push(curr);
}

// Sort left and right queues

sortQueue(left);
sortQueue(right);

// Merge left, pivot, and right queues

while (!left.empty()) {
q.push(left.front());
left.pop();
}
q.push(pivot);
while (!right.empty()) {
q.push(right.front());
right.pop();
}
}

// Function to delete a linked list using recursion

struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};

void deleteLinkedList(Node* head) {

if (head == nullptr)
return;
deleteLinkedList(head->next);
delete head;
}

int main() {
// Sorting a queue using recursion
queue<int> q;
q.push(5);
q.push(3);
q.push(7);
q.push(1);
cout << "Queue before sorting: ";
while (!q.empty()) {
cout << q.front() << " ";
q.pop();

22 | P a g e
 }
cout << endl;

q.push(5);
q.push(3);
q.push(7);
q.push(1);
sortQueue(q);
cout << "Queue after sorting: ";
while (!q.empty()) {
cout << q.front() << " ";
q.pop();
}
cout << endl;

// Reversing a queue using recursion

queue<int> q2;
for (int i = 1; i <= 5; ++i)
q2.push(i);
cout << "Queue before reversing: ";
while (!q2.empty()) {
cout << q2.front() << " ";
q2.pop();
}
cout << endl;

for (int i = 1; i <= 5; ++i)

q2.push(i);
reverseQueue(q2);
cout << "Queue after reversing: ";
while (!q2.empty()) {
cout << q2.front() << " ";
q2.pop();
}
cout << endl;

// Deleting a linked list using recursion

Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(4);
head->next->next->next->next = new Node(5);
cout << "Linked list before deletion: ";
Node* temp = head;
while (temp) {
cout << temp->data << " ";
temp = temp->next;

23 | P a g e
 }
cout << endl;

deleteLinkedList(head);
cout << "Linked list after deletion: ";
if (!head)
cout << "Empty" << endl;

return 0;
}

OUTPUT :

24 | P a g e
 PROBLEM NO. :12

AIM : WAP for Length of longest palindromic sub-string: Recursion, Program for Tower of Hanoi
Algorithm Find geometric sum of the series using recursion

PROGRAM :

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

// Function to find the length of the longest palindromic sub-string using

recursion
int longestPalindromicSubstring(const string& str, int start, int end) {
if (start > end)
return 0;
if (start == end)
return 1;

if (str[start] == str[end])
return 2 + longestPalindromicSubstring(str, start + 1, end - 1);
else
return max(longestPalindromicSubstring(str, start, end - 1),
longestPalindromicSubstring(str, start + 1, end));
}

// Function to solve Tower of Hanoi problem using recursion

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);
}

// Function to find the geometric sum of a series using recursion

double geometricSum(int k) {
if (k == 0)
return 1;
return 1 / pow(2, k) + geometricSum(k - 1);
}

25 | P a g e
 int main() {
// Length of the longest palindromic sub-string using recursion
string str = "abcbad";
cout << "Length of the longest palindromic sub-string: " <<
longestPalindromicSubstring(str, 0, str.length() - 1) << endl;

// Tower of Hanoi Algorithm

int n = 3; // Number of disks
cout << "Steps to solve Tower of Hanoi with " << n << " disks:\n";
towerOfHanoi(n, 'A', 'B', 'C');

// Find geometric sum of the series using recursion

int k = 3; // Number of terms in the series
cout << "Geometric sum of the series: " << geometricSum(k) << endl;

return 0;
}

OUTPUT :

26 | P a g e
 PROBLEM NO. :13

AIM :WAP Problems related to Linear Search, Binary Search, Problems using Binary Search

PROGRAM :
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Function for linear search

int linearSearch(const vector<int>& arr, int target) {
for (int i = 0; i < arr.size(); ++i) {
if (arr[i] == target)
return i;
}
return -1;
}
// Function for binary search
int binarySearch(const vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
// Problem using binary search: Find the square root of a number
double squareRoot(double x) {
if (x == 0 || x == 1)
return x;

double left = 0, right = x, result = 0;

while (left <= right) {
double mid = left + (right - left) / 2;
if (mid * mid == x)
return mid;
else if (mid * mid < x) {
left = mid + 0.00001; // Accuracy up to 5 decimal places
result = mid;
} else

27 | P a g e
 right = mid - 0.00001; // Accuracy up to 5 decimal places
}
return result;
}
// Problem using binary search: Find the peak element in an array
int findPeakElement(const vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[mid + 1])
left = mid + 1;
else
right = mid;
}
return left;
}
int main() {
// Linear Search
vector<int> arr = {4, 2, 1, 5, 7, 3};
int targetLinear = 5;
cout << "Linear Search: Element " << targetLinear << " found at index " <<
linearSearch(arr, targetLinear) << endl;

// Binary Search
sort(arr.begin(), arr.end());
int targetBinary = 5;
cout << "Binary Search: Element " << targetBinary << " found at index " <<
binarySearch(arr, targetBinary) << endl;

// Find the square root of a number

double number = 8;
cout << "Square root of " << number << " is approximately " <<
squareRoot(number) << endl;

// Find the peak element in an array

vector<int> nums = {1, 2, 3, 1};
cout << "Peak element in the array: " << nums[findPeakElement(nums)] << endl;
return 0;
}

OUTPUT :

28 | P a g e
 PROBLEM NO. :14

AIM : WAP to Convert a String to an Integer using Recursion

PROGRAM :
#include <iostream>
#include <string>
using namespace std;

// Function to convert a string to an integer using recursion

int stringToInt(const string& str, int index = 0, int result = 0) {
// Base case: if index exceeds the length of the string
if (index == str.length())
return result;

// Multiply the current result by 10 and add the integer value of the current
character
result = result * 10 + (str[index] - '0');

// Recursively call the function for the next character

return stringToInt(str, index + 1, result);
}

int main() {
string str = "12345";
int num = stringToInt(str);
cout << "String \"" << str << "\" converted to integer: " << num << endl;
return 0;
}

OUTPUT :

29 | P a g e
 PROBLEM NO. :15

AIM : WAP Reverse a Doubly linked list using recursion, Check if a string is a scrambled form of
another string, N Queen Problem

PROGRAM :

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

// Definition for doubly linked list node

struct ListNode {
int val;
ListNode* next;
ListNode* prev;
ListNode(int x) : val(x), next(nullptr), prev(nullptr) {}
};

// Function to reverse a doubly linked list using recursion

ListNode* reverseDoublyLinkedList(ListNode* head) {
if (!head || !head->next)
return head;
ListNode* rest = reverseDoublyLinkedList(head->next);
head->next->prev = nullptr;
head->next->next = head;
head->prev = head->next;
head->next = nullptr;
return rest;
}

// Function to check if a string is a scrambled form of another string

unordered_map<string, bool> memo;
bool isScramble(string s1, string s2) {
if (s1 == s2)
return true;
if (s1.length() != s2.length())
return false;
string key = s1 + "_" + s2;
if (memo.find(key) != memo.end())
return memo[key];

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

30 | P a g e
 if ((isScramble(s1.substr(0, i), s2.substr(0, i)) &&
isScramble(s1.substr(i), s2.substr(i))) ||
(isScramble(s1.substr(0, i), s2.substr(n - i)) &&
isScramble(s1.substr(i), s2.substr(0, n - i)))) {
memo[key] = true;
return true;
}
}
memo[key] = false;
return false;
}

// Function to solve the N Queen Problem

bool isSafe(vector<vector<int>>& board, int row, int col, int n) {
// Check if there is a queen in the same column
for (int i = 0; i < row; ++i) {
if (board[i][col] == 1)
return false;
}
// Check upper left diagonal
for (int i = row, j = col; i >= 0 && j >= 0; --i, --j) {
if (board[i][j] == 1)
return false;
}
// Check upper right diagonal
for (int i = row, j = col; i >= 0 && j < n; --i, ++j) {
if (board[i][j] == 1)
return false;
}
return true;
}

bool solveNQueensUtil(vector<vector<int>>& board, int row, int n) {

if (row == n)
return true;

for (int col = 0; col < n; ++col) {

if (isSafe(board, row, col, n)) {
board[row][col] = 1;
if (solveNQueensUtil(board, row + 1, n))
return true;
board[row][col] = 0;
}
}
return false;
}

31 | P a g e
void printBoard(const vector<vector<int>>& board) {
for (auto& row : board) {
for (int cell : row)
cout << cell << " ";
cout << endl;
}
}

void solveNQueens(int n) {
vector<vector<int>> board(n, vector<int>(n, 0));
if (solveNQueensUtil(board, 0, n))
printBoard(board);
else
cout << "No solution exists for N = " << n << endl;
}

int main() {
// Reverse a doubly linked list using recursion
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->prev = head;
head->next->next = new ListNode(3);
head->next->next->prev = head->next;
head->next->next->next = new ListNode(4);
head->next->next->next->prev = head->next->next;
cout << "Doubly linked list before reversal:" << endl;
ListNode* temp = head;
while (temp) {
cout << temp->val << " ";
temp = temp->next;
}
cout << endl;
head = reverseDoublyLinkedList(head);
cout << "Doubly linked list after reversal:" << endl;
temp = head;
while (temp) {
cout << temp->val << " ";
temp = temp->next;
}
cout << endl << endl;

// Check if a string is a scrambled form of another string

string s1 = "great", s2 = "rgeat";
cout << "Is \"" << s1 << "\" a scrambled form of \"" << s2 << "\"? ";
cout << (isScramble(s1, s2) ? "Yes" : "No") << endl << endl;

// Solve the N Queen Problem

32 | P a g e
 cout << "Solutions for the N Queen Problem where N = 4:" << endl;
solveNQueens(4);

return 0;
}

OUTPUT :

33 | P a g e
 PROBLEM NO. :16

AIM : WAP How to Sort a Stack using Recursion

PROGRAM :
#include <iostream>
#include <stack>
using namespace std;

// Function to insert an element in a sorted order in a stack

void sortedInsert(stack<int>& s, int x) {
// Base case: Either stack is empty or newly inserted
// item is greater than top (more than all existing)
if (s.empty() || x > s.top()) {
s.push(x);
return;
}

// If top is greater, remove the top item and recursively

// call sortedInsert for the remaining stack
int temp = s.top();
s.pop();
sortedInsert(s, x);

// Put back the top item removed earlier

s.push(temp);
}

// Function to sort the stack using recursion

void sortStack(stack<int>& s) {
// Base case: stack is empty
if (!s.empty()) {
// Remove the top item
int x = s.top();
s.pop();

// Sort remaining stack

sortStack(s);

// Push the top item back in sorted stack

sortedInsert(s, x);
}
}

// Utility function to print contents of stack

void printStack(stack<int>& s) {

34 | P a g e
 if (s.empty())
return;

int x = s.top();
s.pop();
cout << x << " ";

printStack(s);

s.push(x);
}

int main() {
stack<int> s;
s.push(30);
s.push(20);
s.push(50);
s.push(40);
s.push(10);

cout << "Stack before sorting: ";

printStack(s);
cout << endl;

sortStack(s);

cout << "Stack after sorting: ";

printStack(s);
cout << endl;

return 0;
}

OUTPUT :

35 | P a g e
 PROBLEM NO. :17

AIM : WAP to Sort elements by frequency, Sort an array of 0s, 1s and 2s, Sort numbers stored on
different machines

PROGRAM :
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

// Utility function to print a vector

void printVector(const vector<int>& vec) {
for (int val : vec) {
cout << val << " ";
}
cout << endl;
}

// 1. Sort elements by frequency

vector<int> sortByFrequency(const vector<int>& arr) {
unordered_map<int, int> freq;
for (int num : arr) {
freq[num]++;
}

vector<pair<int, int>> freqVec;

for (const auto& p : freq) {
freqVec.push_back(p);
}

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

pair<int, int>& b) {
return (a.second == b.second) ? a.first < b.first : a.second > b.second;
});

vector<int> sortedArr;
for (const auto& p : freqVec) {
for (int i = 0; i < p.second; ++i) {
sortedArr.push_back(p.first);
}
}
return sortedArr;
}

36 | P a g e
// 2. Sort an array of 0s, 1s, and 2s (Dutch National Flag problem)
void sort012(vector<int>& arr) {
int low = 0, mid = 0, high = arr.size() - 1;
while (mid <= high) {
switch (arr[mid]) {
case 0:
swap(arr[low++], arr[mid++]);
break;
case 1:
mid++;
break;
case 2:
swap(arr[mid], arr[high--]);
break;
}
}
}

// 3. Sort numbers stored on different machines (using external merge sort

approach)
vector<int> mergeSortedVectors(const vector<vector<int>>& sortedVectors) {
vector<int> result;
vector<int> indices(sortedVectors.size(), 0);

bool done;
do {
done = true;
int minValue = INT_MAX;
int minIndex = -1;

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

if (indices[i] < sortedVectors[i].size()) {
done = false;
if (sortedVectors[i][indices[i]] < minValue) {
minValue = sortedVectors[i][indices[i]];
minIndex = i;
}
}
}

if (minIndex != -1) {
result.push_back(minValue);
indices[minIndex]++;
}
} while (!done);

return result;

37 | P a g e
 }

int main() {
// 1. Sort elements by frequency
vector<int> arr1 = {5, 5, 4, 6, 4, 4, 6, 6, 6, 5, 7, 7, 7, 7};
cout << "Array sorted by frequency: ";
vector<int> sortedByFreq = sortByFrequency(arr1);
printVector(sortedByFreq);

// 2. Sort an array of 0s, 1s, and 2s

vector<int> arr2 = {0, 1, 2, 0, 1, 2, 1, 0, 2, 1, 0, 2};
cout << "Array of 0s, 1s, and 2s before sorting: ";
printVector(arr2);
sort012(arr2);
cout << "Array of 0s, 1s, and 2s after sorting: ";
printVector(arr2);

// 3. Sort numbers stored on different machines

vector<vector<int>> sortedVectors = {
{1, 5, 9},
{2, 6, 10},
{3, 7, 11},
{4, 8, 12}
};
cout << "Merged sorted vectors: ";
vector<int> mergedSorted = mergeSortedVectors(sortedVectors);
printVector(mergedSorted);

return 0;
}

OUTPUT :

38 | P a g e
 PROBLEM NO. :18

AIM : WAP for Sorting Strings using Bubble Sort, Sort even-placed elements in increasing and odd-
placed in decreasing order

PROGRAM :
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Function to sort strings using bubble sort

void bubbleSort(vector<string>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < n - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}
// Utility function to print a vector of strings
void printVector(const vector<string>& vec) {
for (const string& str : vec) {
cout << str << " ";
}
cout << endl;
}
// Function to sort even-placed elements in increasing and odd-placed elements in
decreasing order
void sortEvenOdd(vector<int>& arr) {
vector<int> even, odd;
for (int i = 0; i < arr.size(); ++i) {
if (i % 2 == 0) {
even.push_back(arr[i]);
} else {
odd.push_back(arr[i]);
}
}
sort(even.begin(), even.end());
sort(odd.begin(), odd.end(), greater<int>());
for (int i = 0, j = 0, k = 0; i < arr.size(); ++i) {
if (i % 2 == 0) {
arr[i] = even[j++];

39 | P a g e
 } else {
arr[i] = odd[k++];
}
}
}
// Utility function to print a vector of integers
void printVector(const vector<int>& vec) {
for (int val : vec) {
cout << val << " ";
}
cout << endl;
}
int main() {
// Sorting strings using bubble sort
vector<string> strArr = {"apple", "orange", "banana", "grape", "cherry"};
cout << "Strings before bubble sort: ";
printVector(strArr);
bubbleSort(strArr);
cout << "Strings after bubble sort: ";
printVector(strArr);
// Sorting even-placed elements in increasing and odd-placed elements in
decreasing order
vector<int> intArr = {10, 11, 20, 21, 30, 31, 40, 41};
cout << "Array before sorting: ";
printVector(intArr);
sortEvenOdd(intArr);
cout << "Array after sorting even-placed elements in increasing and odd-
placed elements in decreasing order: ";
printVector(intArr);

return 0;
}

OUTPUT :

40 | P a g e
 PROBLEM NO. :19

AIM : WAP to Print array of strings in sorted order without copying one string into another. K-Way
Merge Sort

PROGRAM :
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;

// Function to print an array of strings in sorted order without copying one

string into another
void printSortedStrings(vector<string>& arr) {
// Create a vector of pointers to strings
vector<string*> ptrs(arr.size());
for (size_t i = 0; i < arr.size(); ++i) {
ptrs[i] = &arr[i];
}

// Sort the pointers based on the strings they point to

sort(ptrs.begin(), ptrs.end(), [](const string* a, const string* b) {
return *a < *b;
});

// Print the strings using the sorted pointers

for (const string* ptr : ptrs) {
cout << *ptr << " ";
}
cout << endl;
}

// Function to merge K sorted arrays

vector<int> kWayMerge(const vector<vector<int>>& sortedArrays) {
// Define a min-heap to store elements along with the index of the array they
belong to
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,
int>>> minHeap;

// Vector to store the current index of each array

vector<int> indices(sortedArrays.size(), 0);

// Initialize the heap with the first element of each array

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

41 | P a g e
 if (!sortedArrays[i].empty()) {
minHeap.push({sortedArrays[i][0], i});
}
}

vector<int> result;

// Extract the minimum element from the heap and add the next element from
the same array to the heap
while (!minHeap.empty()) {
auto [val, index] = minHeap.top();
minHeap.pop();
result.push_back(val);

if (++indices[index] < sortedArrays[index].size()) {

minHeap.push({sortedArrays[index][indices[index]], index});
}
}

return result;
}

// Utility function to print a vector of strings

void printStringVector(const vector<string>& vec) {
for (const string& str : vec) {
cout << str << " ";
}
cout << endl;
}

// Utility function to print a vector of integers

void printIntVector(const vector<int>& vec) {
for (int val : vec) {
cout << val << " ";
}
cout << endl;
}

int main() {
// Sorting strings using bubble sort without copying strings
vector<string> strArr = {"apple", "orange", "banana", "grape", "cherry"};
cout << "Original array of strings: ";
printStringVector(strArr);

cout << "Sorted array of strings without copying strings: ";

printSortedStrings(strArr);

42 | P a g e
 // K-Way Merge Sort
vector<vector<int>> sortedArrays = {
{1, 5, 9},
{2, 6, 10},
{3, 7, 11},
{4, 8, 12}
};

cout << "Merged sorted arrays: ";

vector<int> mergedSorted = kWayMerge(sortedArrays);
printIntVector(mergedSorted);

return 0;
}

OUTPUT :

43 | P a g e
 PROBLEM NO. :20

AIM : WAP for Nuts and bolts Problems.

PROGRAM :
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Function to print a vector

template <typename T>
void printVector(const vector<T>& vec) {
for (const T& element : vec) {
cout << element << " ";
}
cout << endl;
}

// Partition function for nuts and bolts

int partition(vector<char>& arr, int low, int high, char pivot) {
int i = low;
for (int j = low; j < high; ++j) {
if (arr[j] < pivot) {
swap(arr[i], arr[j]);
i++;
} else if (arr[j] == pivot) {
swap(arr[j], arr[high]);
j--;
}
}
swap(arr[i], arr[high]);
return i;
}

// Function to match nuts and bolts using a modified quicksort

void matchNutsAndBolts(vector<char>& nuts, vector<char>& bolts, int low, int
high) {
if (low < high) {
// Choose the last bolt as pivot for nuts partition
int pivot = partition(nuts, low, high, bolts[high]);

// Partition bolts using the nut at the pivot position

partition(bolts, low, high, nuts[pivot]);

44 | P a g e
 // Recursively match the nuts and bolts
matchNutsAndBolts(nuts, bolts, low, pivot - 1);
matchNutsAndBolts(nuts, bolts, pivot + 1, high);
}
}

int main() {
vector<char> nuts = {'@', '#', '$', '%', '^', '&'};
vector<char> bolts = {'$', '%', '&', '^', '@', '#'};

cout << "Original nuts: ";

printVector(nuts);
cout << "Original bolts: ";
printVector(bolts);

matchNutsAndBolts(nuts, bolts, 0, nuts.size() - 1);

cout << "Matched nuts and bolts: " << endl;

cout << "Nuts: ";
printVector(nuts);
cout << "Bolts: ";
printVector(bolts);

return 0;
}

OUTPUT :

45 | P a g e