abhijeets7663@gmail.com
help@ccatcracker.in

#### Section B Question

32.

Find pair with given sum in array

 Input . Array = [ 8,7, 2, 5, 3, 1] sum = 10 Output. Pair found at index (0,2)(8+2) or Pair found at index 1 and 4 (7+3)
```                  #include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;

// A heap nodestruct Node{	// value stores the element,	// list_num stores list number of the element	// index stores column number of the list from which element was taken	int value, list_num, index;};

// Comparison object to be used to order the heapstruct comp {	bool operator()(const Node lhs, const Node rhs) const	{		return lhs.value > rhs.value;	}};

// Function to compute the minimum range that includes// at-least one element from given M listspair<int, int> findMinimumRange(vector<int> list[], int M){	// high will be maximum element in the heap	int high = INT_MIN;

// stores minimum and maximum element found so	// far in heap	pair<int,int> p = { 0, INT_MAX };

// create an empty min-heap	priority_queue<Node, std::vector<Node>, comp> pq;

// push first element of each list into the min-heap	// along with list number and their index in the list	for (int i = 0; i < M; i++)	{		pq.push({list[i], i, 0});		high = max(high, list[i]);	}

// run till end of any list is not reached	for (;;)	{		// get root node information from the min-heap		int low = pq.top().value;		int i = pq.top().list_num;		int j = pq.top().index;

// remove root node		pq.pop();

// update low, high if new min is found		if (high - low < p.second - p.first) {			p = {low, high};		}

// return on reaching the end of any list		if (j == list[i].size() - 1) {			return p;		}

// take next element from "same" list and		// insert it into the min-heap		pq.push({list[i][j + 1], i, j + 1});

// update high if new element is greater		high = max(high, list[i][j + 1]);	}}

// main functionint main(){	vector<int> list[] =	{		{ 3, 6, 8, 10, 15 },		{ 1, 5, 12 },		{ 4, 8, 15, 16},		{ 2, 6 }	};

const size_t M = sizeof(list) / sizeof(list);

pair<int, int> p = findMinimumRange(list, M);	cout << "Minimum range is " << p.first <<  "-" << p.second << "\n";

return 0;}
```

31.

Given m sorted list with n elements print them in sorted order .

 Input . M list : { 10, 20, 30, 40 }, { 15, 25, 35, 45 }, { 27, 29, 37, 48 }, { 32, 33, 39, 50 }, { 16, 18, 22, 28 } Output. Sorted : 10 15 16 18 20 22 25 27 28 29 30 32 33 35 37 39 40 45 48 50
```                  #include <iostream>#include <vector>#include <queue>using namespace std;

// M arrays of size N each#define N 4#define M 5

// A min-heap nodestruct Node{	// val stores the element,	// i stores list number of the element,	// index stores column number of ith list from which element was taken	int val, i, index;};

// Comparison object to be used to order the min-heapstruct comp{	bool operator()(const Node &lhs, const Node &rhs) const	{		return lhs.val > rhs.val;	}};

// Function to merge M sorted lists each of size N and// print them in ascending ordervoid printSorted(int list[][N]){	// create an empty min-heap	priority_queue<Node, std::vector<Node>, comp> pq;

// push first element of each list into the min-heap	// along with list number and their index in the list	for (int i = 0; i < M; i++)		pq.push({list[i], i, 0});

// run till min-heap is not empty	while (!pq.empty())	{		// extract minimum node from the min-heap		Node min = pq.top();		pq.pop();

// print the minimum element		cout << min.val << " ";

// take next element from "same" list and		// insert it into the min-heap		if (min.index + 1 < N)		{			min.index += 1;			min.val = list[min.i][min.index];			pq.push(min);		}	}}

// main functionint main(){	// M lists of size N each in the form of 2D-matrix	int list[M][N] =	{		{ 10, 20, 30, 40 },		{ 15, 25, 35, 45 },		{ 27, 29, 37, 48 },		{ 32, 33, 39, 50 },		{ 16, 18, 22, 28 }	};

printSorted(list);

return 0;}
```

30.

Find k smallest element in array using C++

 Input . Array : { 7, 4, 6, 3, 9, 1 }; K = 3 Output. K small number : 4
```                  #include <iostream>#include <vector>#include <queue>using namespace std;

// Function to find the K'th smallest element in the// array using max-heapint findKthSmallest(vector<int> const &v, int k){	// create an max-heap using std::priority_queue and	// insert first k elements of the array into the heap	priority_queue<int, vector<int>> pq(v.begin(), v.begin() + k);

// do for remaining array elements	for (int i = k; i < v.size(); i++)	{		// if current element is less than the root of the heap		if (v[i] < pq.top())		{			// replace root with the current element			pq.pop();			pq.push(v[i]);		}	}

// return the root of max-heap	return pq.top();}

// Find K'th smallest element in an arrayint main(){	vector<int> vec  = { 7, 4, 6, 3, 9, 1 };	const size_t k = 3;

cout << "K'th smallest element in the array is " <<			findKthSmallest(vec, k);

return 0;}
```

29.

Write a C++ program to reverse a linked list

 Input . List : 85 15 4 20 Output. Reversed list 20 4 15 85
```                  // Iterative C++ program to reverse // a linked list #include <iostream> using namespace std;

/* Link list node */struct Node { 	int data; 	struct Node* next; 	Node(int data) 	{ 		this->data = data; 		next = NULL; 	} };

/* Function to reverse the linked list */	void reverse() 	{ 		// Initialize current, previous and 		// next pointers 		Node* current = head; 		Node *prev = NULL, *next = NULL;

while (current != NULL) { 			// Store next 			next = current->next;

// Reverse current node's pointer 			current->next = prev;

// Move pointers one position ahead. 			prev = current; 			current = next; 		} 		head = prev; 	}

/* Function to print linked list */	void print() 	{ 		struct Node* temp = head; 		while (temp != NULL) { 			cout << temp->data << " "; 			temp = temp->next; 		} 	}

void push(int data) 	{ 		Node* temp = new Node(data); 		temp->next = head; 		head = temp; 	} };

/* Driver program to test above function*/int main() { 	/* Start with the empty list */	LinkedList ll; 	ll.push(20); 	ll.push(4); 	ll.push(15); 	ll.push(85);

cout << "Given linked list\n"; 	ll.print();

ll.reverse();

cout << "\nReversed Linked list \n"; 	ll.print(); 	return 0; }
```

28.

write a CPP program to reverse a string using stack

 Input . Enter a string : abc Output. Result : cba
```                  // CPP program to reverse a string using stack #include <bits/stdc++.h> using namespace std;

// A structure to represent a stack class Stack { 	public: 	int top; 	unsigned capacity; 	char* array; };

// function to create a stack of given // capacity. It initializes size of stack as 0 Stack* createStack(unsigned capacity) { 	Stack* stack = new Stack(); 	stack->capacity = capacity; 	stack->top = -1; 	stack->array = new char[(stack->capacity * sizeof(char))]; 	return stack; }

// Stack is full when top is equal to the last index int isFull(Stack* stack) { return stack->top == stack->capacity - 1; }

// Stack is empty when top is equal to -1 int isEmpty(Stack* stack) { return stack->top == -1; }

// Function to add an item to stack. // It increases top by 1 void push(Stack* stack, char item) { 	if (isFull(stack)) 		return; 	stack->array[++stack->top] = item; }

// Function to remove an item from stack. // It decreases top by 1 char pop(Stack* stack) { 	if (isEmpty(stack)) 		return -1; 	return stack->array[stack->top--]; }

// A stack based function to reverse a string void reverse(char str[]) { 	// Create a stack of capacity 	//equal to length of string 	int n = strlen(str); 	Stack* stack = createStack(n);

// Push all characters of string to stack 	int i; 	for (i = 0; i < n; i++) 		push(stack, str[i]);

// Pop all characters of string and 	// put them back to str 	for (i = 0; i < n; i++) 		str[i] = pop(stack); }

// Driver code int main() { 	char str[] = "GeeksQuiz";

reverse(str); 	cout << "Reversed string is " << str;

return 0; }
```

27.

C++ Program to convert infix expression to postfix

 Input . Output. abcd^e-fgh*+^*+i-
```                  /* C++ implementation to convert infix expression to postfix*/// Note that here we use std::stack for Stack operations #include<bits/stdc++.h> using namespace std;

//Function to return precedence of operators int prec(char c) { 	if(c == '^') 	return 3; 	else if(c == '*' || c == '/') 	return 2; 	else if(c == '+' || c == '-') 	return 1; 	else	return -1; }

// The main function to convert infix expression //to postfix expression void infixToPostfix(string s) { 	std::stack<char> st; 	st.push('N'); 	int l = s.length(); 	string ns; 	for(int i = 0; i < l; i++) 	{ 		// If the scanned character is an operand, add it to output string. 		if((s[i] >= 'a' && s[i] <= 'z')||(s[i] >= 'A' && s[i] <= 'Z')) 		ns+=s[i];

// If the scanned character is an ‘(‘, push it to the stack. 		else if(s[i] == '(') 				st.push('('); 				// If the scanned character is an ‘)’, pop and to output string from the stack 		// until an ‘(‘ is encountered. 		else if(s[i] == ')') 		{ 			while(st.top() != 'N' && st.top() != '(') 			{ 				char c = st.top(); 				st.pop(); 			ns += c; 			} 			if(st.top() == '(') 			{ 				char c = st.top(); 				st.pop(); 			} 		} 				//If an operator is scanned 		else{ 			while(st.top() != 'N' && prec(s[i]) <= prec(st.top())) 			{ 				char c = st.top(); 				st.pop(); 				ns += c; 			} 			st.push(s[i]); 		}

} 	//Pop all the remaining elements from the stack 	while(st.top() != 'N') 	{ 		char c = st.top(); 		st.pop(); 		ns += c; 	} 		cout << ns << endl;

}

//Driver program to test above functions int main() { 	string exp = "a+b*(c^d-e)^(f+g*h)-i"; 	infixToPostfix(exp); 	return 0; }
```

26.

C++ program to demonstrate all insertion methods on Linked List

 Input . Insert Numbers Output. Created Linked list is: 1 7 8 6 4
```                  // A complete working C++ program to demonstrate // all insertion methods on Linked List #include <bits/stdc++.h> using namespace std;

// A linked list node class Node { 	public: 	int data; 	Node *next; };

/* Given a reference (pointer to pointer) to the head of a list and an int, inserts a new node on the front of the list. */void push(Node** head_ref, int new_data) { 	/* 1. allocate node */	Node* new_node = new Node();

/* 2. put in the data */	new_node->data = new_data;

/* 3. Make next of new node as head */	new_node->next = (*head_ref);

/* 4. move the head to point to the new node */	(*head_ref) = new_node; }

/* Given a node prev_node, insert a new node after the given prev_node */void insertAfter(Node* prev_node, int new_data) { 	/*1. check if the given prev_node is NULL */	if (prev_node == NULL) 	{ 		cout<<"the given previous node cannot be NULL"; 		return; 	}

/* 2. allocate new node */	Node* new_node = new Node();

/* 3. put in the data */	new_node->data = new_data;

/* 4. Make next of new node as next of prev_node */	new_node->next = prev_node->next;

/* 5. move the next of prev_node as new_node */	prev_node->next = new_node; }

/* Given a reference (pointer to pointer) to the head of a list and an int, appends a new node at the end */void append(Node** head_ref, int new_data) { 	/* 1. allocate node */	Node* new_node = new Node();

Node *last = *head_ref; /* used in step 5*/

/* 2. put in the data */	new_node->data = new_data;

/* 3. This new node is going to be 	the last node, so make next of 	it as NULL*/	new_node->next = NULL;

/* 4. If the Linked List is empty, 	then make the new node as head */	if (*head_ref == NULL) 	{ 		*head_ref = new_node; 		return; 	}

/* 5. Else traverse till the last node */	while (last->next != NULL) 		last = last->next;

/* 6. Change the next of last node */	last->next = new_node; 	return; }

// This function prints contents of // linked list starting from head void printList(Node *node) { 	while (node != NULL) 	{ 		cout<<" "<<node->data; 		node = node->next; 	} }

/* Driver code*/int main() { 	/* Start with the empty list */	Node* head = NULL; 		// Insert 6. So linked list becomes 6->NULL 	append(&head, 6); 		// Insert 7 at the beginning. 	// So linked list becomes 7->6->NULL 	push(&head, 7); 		// Insert 1 at the beginning. 	// So linked list becomes 1->7->6->NULL 	push(&head, 1); 		// Insert 4 at the end. So 	// linked list becomes 1->7->6->4->NULL 	append(&head, 4); 		// Insert 8, after 7. So linked 	// list becomes 1->7->8->6->4->NULL 	insertAfter(head->next, 8); 		cout<<"Created Linked list is: "; 	printList(head); 		return 0; }
```

25.

C++ program to demonstrate example of friend function with class

 Input . Output. Value of a (private data member of class Number): 1000
```                  /*C++ program to demonstrate example of friend function with class.*/#include <iostream> using namespace std; class Number{private:    int a;public:    void getNum(int x);    //declaration of friend function    friend void printNum(Number NUM);      }; //class member function definitionsvoid Number::getNum(int x){    a=x;} //friend function definition, no need of class name with SRO (::)void printNum(Number NUM){    cout << "Value of a (private data member of class Number): " << NUM.a; } int main(){    Number nObj; //Object declaration    nObj.getNum(1000);    printNum(nObj);    return 0;}
```

24.

C++ program to create class to get and print details of a student

 Input . Enter name: mike Enter roll number: 112 Enter total marks outof 500: 456 Output. Student details: Name:mike,Roll Number:112,Total:456,Percentage:91.2
```                  /*C++ program to create class for a student.*/#include <iostream>using namespace std;

class student{	private:		char  name;		int   rollNo;		int   total;		float perc;	public:		//member function to get student's details		void getDetails(void);		//member function to print student's details		void putDetails(void);};

//member function definition, outside of the classvoid student::getDetails(void){	cout << "Enter name: " ;	cin >> name;	cout << "Enter roll number: ";	cin >> rollNo;	cout << "Enter total marks outof 500: ";	cin >> total;		perc=(float)total/500*100;}

//member function definition, outside of the classvoid student::putDetails(void){	cout << "Student details:\n";	cout << "Name:"<< name << ",Roll Number:" << rollNo << ",Total:" << total << ",Percentage:" << perc;}

int main(){	student std;		//object creation		std.getDetails();	std.putDetails();		return 0;}
```

23.

```                  /*C++ program to demonstrate example of Constructor Overloading.*/#include <iostream>using namespace std; //Class declaration.class Demo{    //Private block to declare data member( X,Y ) of integer type.    private:        int X;        int Y;     //Public blocks of member function to access data members.    public:        //Declaration of default constructor to initialize data members.            Demo ();          //Declaration of parameterized constructor to initialize data members.            Demo (int a, int b);         //To display output onn screen.        void    Display();     };//End of class //Definition of parameterized constructor.Demo:: Demo(){    X = 10;    Y = 20;} //Definition of parameterized constructor.Demo:: Demo(int a, int b){    X = a;    Y = b;}  //Definition of Display() member function.void Demo:: Display(){    cout << endl << "X: " << X;    cout << endl << "Y: " << Y << endl;} int main(){    Demo d1;    cout << "Default Constructor: " << endl;    cout << "Value after initialization : " ;    d1.Display();        Demo d2(30,40) ; //Ctor automatically call when object is created.    cout << "Parameterized Constructor: " << endl;    cout << "Value after initialization : " ;    d2.Display();        return 0;}