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

int main()
{
    cout<<"Maximum Area Histogram"<<endl;
    cout<<"Enter number of elements: ";
    int n;
    cin>>n;
    cout<<"Enter elements:"<<endl;
    int arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    stack<pair<int,int>> stk1;
    stack<pair<int,int>> stk2;
    pair<int,int> p;
    vector<int> left;
    vector<int> right;
    for(int i=0;i<n;i++)
    {
        if(stk1.empty())
        {
            left.push_back(-1);
        }
        else
        {
            while(stk1.empty()==false && stk1.top().first>=arr[i])
            {
                stk1.pop();
            }
            if(stk1.empty()) left.push_back(-1);
            else left.push_back(stk1.top().second);
        }
        p.first=arr[i];
        p.second=i;
        stk1.push(p);
    }
    for(int i=n-1;i>=0;i--)
    {
        if(stk2.empty())
        {
            right.push_back(n);
        }
        else
        {
            while(stk2.empty()==false && stk2.top().first>=arr[i])
            {
                stk2.pop();
            }
            if(stk2.empty()) right.push_back(n);
            else right.push_back(stk2.top().second);
        }
        p.first=arr[i];
        p.second=i;
        stk2.push(p);
    }
    reverse(right.begin(),right.end());
    vector<int> width;
    for(int i=0;i<n;i++)
    {
        width.push_back(right[i]-left[i]-1);
    }
    int max=INT_MIN;
    for(int i=0;i<n;i++)
    {
        if(arr[i]*width[i]>max) max=arr[i]*width[i];
    }
    cout<<"\nElements in array: ";
    for(int i=0;i<n;i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<"\nNearest Smallest to Left array (Indices): ";
    for(int i=0;i<n;i++)
    {
        cout<<left[i]<<" ";
    }
    cout<<"\nNearest Smallest to Right array (Indices): ";
    for(int i=0;i<n;i++)
    {
        cout<<right[i]<<" ";
    }
    cout<<"\nMax area of histogram: "<<max;
    return 0;
}


text:
#include <stdio.h>
#include <stdlib.h>
#define MAX 4

int arr[MAX];
int top = -1;

int isEmpty()
{
    if (top == -1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int isFull()
{
    if (top == MAX - 1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

void push(int data)
{
    if (isFull())
    {
        printf("stack overflow\n");
        return;
    }
    top += 1;
    arr[top] = data;
}

int pop()
{
    int data;
    if (isEmpty())
    {
        printf("stack underflow");
        exit(1);
    }
    data = arr[top];
    top -= 1;
    return data;
}

int peek()
{
    if (isEmpty)
    {
        printf("stack underflow\n");
        exit(1);
    }
    return arr[top];
}

int print()
{
    if (isEmpty())
    {
        printf("stack underflow\n");
    }
    else
    {
        for (int i = top; i >= 0; i--)
        {
            printf("%d", arr[i]);
            printf("\n");
        }
    }
}

int main()
{
    int choice, data;
    while (1)
    {
        printf("\n");
        printf("1. push\n");
        printf("2. pop\n");
        printf("3. print top\n");
        printf("4. print all\n");
        printf("5. quit\n");
        printf("\n");
        printf("enter your choice: ");
        scanf("%d", &choice);
        printf("\n");

        switch (choice)
        {
        case 1:
            printf("enter element to be pushed: ");
            scanf("%d", &data);
            push(data);
            break;

        case 2:
            data = pop();
            printf("deleted element is %d\n", data);
            break;

        case 3:
            printf("the top element in stack is %d\n", arr[top]);
            break;

        case 4:
            print();
            break;

        case 5:
            exit(1);

        default:
            printf("wrong choice\n");
        }
    }

    return 0;
}

file_name: Merge Sorted Array.cpp

mime_type: text/x-c++


text:
#include<iostream>
using namespace std;

class queue{
private:
    int arry[50], front = -1, rear = -1, temp, returnNum;
    int *F = arry;
    int *R = arry;
public:
    void enQueue(int num){
        if(rear > 48){
            cout << "\nQueue OverFlow\n";
        }
        else{
            if(front == -1 && rear == -1){
                *R = num;
                R++;
                front++;
                rear++;
            }
            else{
                *R = num;
                R++;
                rear++;
            }
        }
    }
    int deQueue(){
        if( (front > rear) || front < 0){
            //cout << "\nQueue UnderFlow\n";
            front = -1;
            rear = -1;
            F = arry;
            R = arry;
            return -1;
        }
        else{
            returnNum = *F;
            F++;
            front++;
            return returnNum;
        }
        return -1;
    }
    void display(){
        if(front > rear){
            cout << "\nThe Queue is Empty.\n";
        }
        else{
            //cout <<"\n" << front << " | " << rear;
            cout << "\nThe Queue is as Follows: ";
            for(int i = rear; i >= front; i--){
                cout << arry[i] << " ";
            }
        }
    }
};

class stack{
public:
    queue q1, q2;
    int selected = 1;

    void push(int num){
        int x = 0;
        if(selected == 1){
            q1.enQueue(num);
            while (x != -1){
                x = q2.deQueue();
                if(x != -1)
                    q1.enQueue(x);
            }
            x = 0;
            selected = 2;
        }
        else{
            q2.enQueue(num);
            while (x != -1){
                x = q1.deQueue();
                if(x != -1)
                    q2.enQueue(x);
            }
            x = 0;
            selected = 1;
        }

    }
    int pop(){
        if(selected == 1){
            cout << "\nThe Deleted element is : " << q2.deQueue();
        }
        else{
            cout << "\nThe Deleted element is : " << q1.deQueue();
        }
    }
    int display(){
        if(selected == 1){
            q2.display();
        }
        else{
            q1.display();
        }
    }

};

int main(){
    int n;
    char c;
    stack s1;

    while(1){
        cout << "\nEnter 1 for push and 2 for pop : ";
        cin >> c;

        switch (c){
        case '1':
            cout << "\nEnter the Num: ";
            cin >> n;
            s1.push(n);
            s1.display();
            break;
        case '2':
            s1.pop();
            s1.display();
            break;
        default:
            cout << "You Entere a wrong Choice, Try Again:";
            break;
        }

    }
}


text:
// { Driver Code Starts
#include<bits/stdc++.h>
using namespace std;

 // } Driver Code Ends

class Solution
{
    public:
    //Function to check if brackets are balanced or not.
    bool ispar(string x)
    {
        int n= x.length();
        stack <char> a;
        int d=0,b=0;
        if(x[0]=='}' || x[0]==')'||x[0]==']') return false;
        for(int i=0;i<n;i++){
            if(x[i]=='{' || x[i]=='('||x[i]=='[') d++;
            if(x[i]=='}' || x[i]==')'||x[i]==']') b++;
        }if(d!=b)return false;
        for(int i=0;i<n;i++){
            if(x[i]=='{' || x[i]=='('||x[i]=='[')
              a.push(x[i]);
            if(x[i]=='}' || x[i]==')'||x[i]==']') {
              if ((x[i]=='}' && a.top()=='{') || (x[i]==')' && a.top()=='(')||(x[i]==']' && a.top()=='[')) {
                a.pop();
                }
            }
        }
        if(a.size()==0) return true;
        else return false;
    }
};

// { Driver Code Starts.

int main()
{
   int t;
   string a;
   cin>>t;
   while(t--)
   {
       cin>>a;
       Solution obj;
       if(obj.ispar(a))
        cout<<"balanced"<<endl;
       else
        cout<<"not balanced"<<endl;
   }
}  // } Driver Code Ends


text:
// C# program to sort an
// array using stack
using System;
using System.Collections.Generic;

class GFG
{
	// This function return
	// the sorted stack
	static Stack<int> sortStack(Stack<int> input)
	{
		Stack<int> tmpStack = new Stack<int>();

		while (input.Count != 0)
		{
			// pop out the
			// first element
			int tmp = input.Peek();
			input.Pop();

			// while temporary stack is
			// not empty and top of stack
			// is smaller than temp
			while (tmpStack.Count != 0 &&
					tmpStack.Peek() < tmp)
			{
				// pop from temporary
				// stack and push it
				// to the input stack
				input.Push(tmpStack.Peek());
				tmpStack.Pop();
			}

			// push temp in
			// temporary of stack
			tmpStack.Push(tmp);
		}

		return tmpStack;
	}

	static void sortArrayUsingStacks(int []arr,
									int n)
	{
		// Push array elements
		// to stack
		Stack<int> input = new Stack<int>();
		for (int i = 0; i<n; i++)
		input.Push(arr[i]);

		// Sort the temporary stack
		Stack<int> tmpStack = sortStack(input);

		// Put stack elements in arrp[]
		for (int i = 0; i < n; i++)
		{
			arr[i] = tmpStack.Peek();
			tmpStack.Pop();
		}
	}

	// Driver Code
	static void Main()
	{
		int []arr = new int[] {10, 5,
							15, 45};
		int n = arr.Length;

		sortArrayUsingStacks(arr, n);

		for (int i = 0; i < n; i++)
		Console.Write(arr[i] + " ");
	}
}


text:
#include<stdio.h>
#include<stdlib.h>

struct node
{
	int data;
	struct node *next;
}*top=NULL;

void push()
{
	struct node *newnode;
	newnode=(struct node*)malloc(sizeof(struct node));
	printf("\nEnter the data : ");
	scanf("%d",&newnode->data);
	if(top==NULL)
		newnode->next=NULL;
	else
		newnode->next=top;
	top=newnode;
}

int pop()
{
	if(top==NULL)
	{
		printf("\nUnderflow!!");
		return -1;
	}
	else
	{
		int x=top->data;
		struct node *temp;
		temp=top;
		top=top->next;
		free(temp);
		return x;
	}
}

void display()
{
	struct node	*temp;
	temp=top;
	while(temp!=NULL)
	{
		printf("%d ",temp->data);
		temp=temp->next;
	}
	printf("\n");
}

int main()
{
	int ch;
	do
	{
		printf("\n1 : Push");
		printf("\n2 : Pop");
		printf("\n3 : Display");
		printf("\n4 : Quit");
		printf("\nEnter your choice: ");
		scanf("%d",&ch);
		switch(ch)
		{
			case 1:
				push();
				break;
			case 2:
				pop();
                display();
				break;
			case 3:
				display();
				break;
			case 4:
				break;
			default :
				printf("\nWrong choice.");
		}
	}
    while(ch!=4);
	return 0;
}


text:
/*******
 *
 * Code : Stack Using LL
Send Feedback
Implement a Stack Data Structure specifically to store integer data using a Singly Linked List.
The data members should be private.
You need to implement the following public functions :
1. Constructor:
It initialises the data members as required.
2. push(data) :
This function should take one argument of type integer. It pushes the element into the stack and returns nothing.
3. pop() :
It pops the element from the top of the stack and in turn, returns the element being popped or deleted. In case the stack is empty, it returns -1.
4. top :
It returns the element being kept at the top of the stack. In case the stack is empty, it returns -1.
5. size() :
It returns the size of the stack at any given instance of time.
6. isEmpty() :
It returns a boolean value indicating whether the stack is empty or not.
Operations Performed on the Stack:
Query-1(Denoted by an integer 1): Pushes an integer data to the stack.

Query-2(Denoted by an integer 2): Pops the data kept at the top of the stack and returns it to the caller.

Query-3(Denoted by an integer 3): Fetches and returns the data being kept at the top of the stack but doesn't remove it, unlike the pop function.

Query-4(Denoted by an integer 4): Returns the current size of the stack.

Query-5(Denoted by an integer 5): Returns a boolean value denoting whether the stack is empty or not.
Input Format:
The first line contains an integer 'q' which denotes the number of queries to be run against each operation in the stack.
Then the test cases follow.

Every 'q' lines represent an operation that needs to be performed.

For the push operation, the input line will contain two integers separated by a single space, representing the type of the operation in integer and the integer data being pushed into the stack.

For the rest of the operations on the stack, the input line will contain only one integer value, representing the query being performed on the stack.
 Output Format:
For Query-1, you do not need to return anything.
For Query-2, prints the data being popped from the stack.
For Query-3, prints the data kept on the top of the stack.
For Query-4, prints the current size of the stack.
For Query-5, prints 'true' or 'false'(without quotes).

Output for every query will be printed in a separate line.
Note:
You are not required to print anything explicitly. It has already been taken care of. Just implement the function.
 Constraints:
1 <= q <= 10^5
1 <= x <= 5
-2^31 <= data <= 2^31 - 1 and data != -1

Where 'q' is the total number of queries being performed on the stack, 'x' is the range for every query and data represents the integer pushed into the stack.

Time Limit: 1 second
Sample Input 1:
6
1 13
1 47
4
5
2
3
Sample Output 1:
2
false
47
13
Sample Input 2:
4
5
2
1 10
5
Sample Output 2:
true
-1
false
 Explanation of Sample Input 2:
There are 4 queries in total.
The first one is Query-5: It tells whether the stack is empty or not. Since the stack is empty at this point, the output is  'true'.

The second one is Query-2: It pops the data from the stack. Since at this point in time, no data exist in the stack hence, it prints -1.

The third one is Query-1: It pushes the specified data 10 into the stack and since the function doesn't return anything, nothing is printed.

The fourth one is Query-5: It tells whether the stack is empty at this point or not. Since the stack has one element and hence it is not empty, false is printed.

********************************/

/*******
 Following Node class and main already created internally. You can directly use that.

#include<iostream>
using namespace std;

template <typename T>
class Node {
    public :
    T data;
    Node<T> *next;

    Node(T data) {
        this -> data = data;
        next = NULL;
    }
};

#include "Stack.h"
    int main() {

        Stack<int> st;

        int choice;
        cin >> choice;
        int input;

        while (choice !=-1) {
            if(choice == 1) {
                cin >> input;
                st.push(input);
            }
            else if(choice == 2) {
                int ans = st.pop();
                if(ans != 0) {
                    cout << ans << endl;
                }
                else {
                    cout << "-1" << endl;
                }
            }
            else if(choice == 3) {
                int ans = st.top();
                if(ans != 0) {
                    cout << ans << endl;
                }
                else {
                    cout << "-1" << endl;
                }
            }
            else if(choice == 4) {
                cout << st.getSize() << endl;
            }
            else if(choice == 5) {
                cout << st.isEmpty() << endl;
            }
            cin >> choice;
        }

    }
***********/

class Stack {
	// Define the data members
    Node *head;
    int size;
   public:
    Stack() {
        // Implement the Constructor
        head=NULL;
        size=0;
    }

	/*----------------- Public Functions of Stack -----------------*/

    int getSize() {
        // Implement the getSize() function
        return size;
    }

    bool isEmpty() {
        // Implement the isEmpty() function
      if(size==0){
          return true;
      }

            return false;
    }

    void push(int element) {
        // Implement the push() function

         Node* newHead=new Node(element);
        newHead->next=head;
        head=newHead;
        size++;
            }

    int pop() {
        // Implement the pop() function
        if(head==NULL){
            return -1;
        }
        else{
            int temp=head->data;

             Node *temp1=head->next;

           head->next=NULL;

            head=temp1;
            size--;
            return temp;
        }
    }

    int top() {
        // Implement the top() function
        if(head==NULL){
            return -1;
        }
        else{
            return head->data;
        }
    }
};

//main func

#include <iostream>
using namespace std;

class Node {
   public:
    int data;
    Node *next;

    Node(int data) {
        this->data = data;
        next = NULL;
    }
};

int main() {
    Stack st;

    int q;
    cin >> q;

    while (q--) {
        int choice, input;
        cin >> choice;
        switch (choice) {
            case 1:
                cin >> input;
                st.push(input);
                break;
            case 2:
                cout << st.pop() << "\n";
                break;
            case 3:
                cout << st.top() << "\n";
                break;
            case 4:
                cout << st.getSize() << "\n";
                break;
            default:
                cout << ((st.isEmpty()) ? "true\n" : "false\n");
                break;
        }
    }
}


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

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

string InfixToPrefix(stack<char> s,string infix){
    string prefix;
    reverse(infix.begin(), infix.end());

    for (int i = 0; i < infix.length(); i++) {
        if (infix[i] == '(') {
            infix[i] = ')';
        }
        else if (infix[i] == ')') {
            infix[i] = '(';
        }
    }
    for (int i = 0; i < infix.length(); i++) {
        if ((infix[i] >= 'a' && infix[i] <= 'z') || (infix[i] >= 'A' && infix[i] <= 'Z')) {
            prefix += infix[i];
        }
        else if (infix[i] == '(') {
            s.push(infix[i]);
        }
        else if (infix[i] == ')') {
            while ((s.top() != '(') && (!s.empty())) {
                prefix += s.top();
                s.pop();
            }

            if (s.top() == '(') {
                s.pop();
            }
        }
        else{
            if (s.empty()) {
                s.push(infix[i]);
            }
            else {
                if (precedence(infix[i]) > precedence(s.top())) {
                    s.push(infix[i]);
                }
                else if ((precedence(infix[i]) == precedence(s.top()))
                    && (infix[i] == '^')) {
                    while ((precedence(infix[i]) == precedence(s.top()))
                        && (infix[i] == '^')) {
                        prefix += s.top();
                        s.pop();
                    }
                    s.push(infix[i]);
                }
                else if (precedence(infix[i]) == precedence(s.top())) {
                    s.push(infix[i]);
                }
                else {
                    while ((!s.empty()) && (precedence(infix[i]) < precedence(s.top()))) {
                        prefix += s.top();
                        s.pop();
                    }
                    s.push(infix[i]);
                }
            }
        }
    }

    while (!s.empty()) {
        prefix += s.top();
        s.pop();
    }

    reverse(prefix.begin(), prefix.end());
    return prefix;

}

int main(){
    string infix;
    cin>>infix;
    stack<char> stack;
    string prefix;
    prefix=InfixToPrefix(stack,infix);
    cout<<"Prefix : "<<prefix;
    return 0;
}


text:
#include <iostream>
#include <stdlib.h>

using namespace std;

class twoStacks
{
    int *arr;
    int size;
    int top1, top2;

public:
    twoStacks(int n)
    {
        size = n;
        arr = new int[n];
        top1 = -1;
        top2 = size;
    }

    void push1(int x)
    {
        if (top1 < top2 - 1)
        {
            top1++;
            arr[top1] = x;
        }
        else
        {
            cout << "Stack Overflow";
            exit(1);
        }
    }

    void push2(int x)
    {

        if (top1 < top2 - 1)
        {
            top2--;
            arr[top2] = x;
        }
        else
        {
            cout << "Stack Overflow";
            exit(1);
        }
    }

    int pop1()
    {
        if (top1 >= 0)
        {
            int x = arr[top1];
            top1--;
            return x;
        }
        else
        {
            cout << "Stack UnderFlow";
            return -1;
        }
    }

    int pop2()
    {
        if (top2 < size)
        {
            int x = arr[top2];
            top2++;
            return x;
        }
        else
        {
            cout <<endl<< "Stack UnderFlow";
            return -1;
        }
    }
    void display()
    {
        cout << "Stack 1 ";
        if (top1 >= 0)
        {
            for (int i = top1; i >= 0; i--)
                cout << arr[i] << " ";
        }
        else
            cout << "Stack is empty";

    cout << endl;
    cout << "Stack 2: " ;
    if (top2 != size)
    {
        for (int i = top2; i < size; i++)
        {
            cout << arr[i] << " ";
        }
    }
    else
    {
        cout << "Stack is empty";
    }
    cout << endl;
    }
};

int main()
{
    int n;
    cout << "Enter the size of the stack ";
    cin >> n;

    twoStacks ts(n);
    int ch, val;

    do
    {
        cout << "1) Push in stack 1" << endl;
        cout << "2) Push in stack 2" << endl;
        cout << "3) Pop from stack 1" << endl;
        cout << "4) Pop from stack 2" << endl;
        cout << "5) Display Stack" << endl;
        cout << "6) Exit" << endl;
        cout << "Enter choice: " << endl;
        cin >> ch;
        switch (ch)
        {
        case 1:
        {
            cout << "Enter value to be pushed in stack 1:" << endl;
            cin >> val;
            ts.push1(val);
            break;
        }
        case 2:
        {
            cout << "Enter value to be pushed in stack 2: " << endl;
            cin >> val;
            ts.push2(val);
            break;
        }
        case 3:
        {

            int x = ts.pop1();
            if (x != -1)
            {
                cout << "Popped Value from stack 1 is " << x << endl;
                break;
            }
            break;
        }
        case 4:
        {

            int x = ts.pop2();
            if (x != -1)
            {
                cout << "Popped Value from stack 2 is " << x << endl;
                break;
            }
            break;
        }

        case 5:
        {
            ts.display();
            break;
        }
        case 6:
        {
            cout << "Exit" << endl;
            break;
        }
        default:
        {
            cout << "Invalid Choice" << endl;
        }
        }

    } while (ch != 6);
}


text:
#include<stdio.h>
#include<stdlib.h>
/* Function to print reverse of the passed string */
char *reverse(char *str)
{
static int i = 0;
    static char rev[100];
    if(*str)
    {
        reverse(str+1);
        rev[i++] = *str;
    }
    return rev;
}

/* Driver program to test above function */
int main()
{
    char a[100];
    printf("Input string \n");
    gets(a);
    char *r=reverse(a);
    puts(r);
    return 0;
}


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

string reverseString(string s)
{
    //base case
    if(s.length()==0)
    {
        return "";
    }

    return reverseString(s.substr(1))+s[0];//recursive function
}

int main()
{
    string s;
    cout<<"Enter the string to be reversed ";
    getline(cin,s);

    cout<<"Original string is "<<s<<endl; //string before reversal

    string r = reverseString(s);
    cout<<"Reversed string is "<<r<<endl; //reversed string

    return 0;
}


text:
#include<iostream>
using namespace std;
int main()
{
	char arr[20];
	int length;
	bool flag = true;
	cout << "Enter a string\n";
	cin >> arr;
	length = strlen(arr);
	for (int i = 0; i < length; i++)
	{
		if (arr[i] != arr[length - i - 1])
		{
			flag = false;
			break;
		}
	}
	if (flag)
	{
		cout << "String is palindrome\n";
	}
	else {
		cout << "String is not a palindrome\n";
	}
	return 0;
}


text:
#include <bits/stdc++.h>
using namespace std;
typedef long long  int ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define PRIME 1000000007
#define REP(i, a, b) for (int i = a; i < b; ++i)
#define REPR(i, a, b) for (int i = a; i >= b; i--)
const int SIZE = 1e5 + 5;

int instance_val(string s) {
    if (s == "IV")
        return 4;
    else if (s == "IX")
        return 9;
    else if (s == "XL")
        return 40;
    else if (s == "XC")
        return 90;
    else if (s == "CD")
        return 400;
    else if (s == "CM")
        return 900;
    return 0;
}

int romanToInt(string s) {
    map<char, int> mp;
    mp['I'] = 1;
    mp['V'] = 5;
    mp['X'] = 10;
    mp['L'] = 50;
    mp['C'] = 100;
    mp['D'] = 500;
    mp['M'] = 1000;
    int res = 0;
    for (int i = 0; i < s.length(); ++i) {
        if (i + 1 < s.length() && instance_val(s.substr(i, 2))) {
            res += instance_val(s.substr(i, 2));
                i += 1;
        } else {
            int cnt = 1;
            while (i + 1 < s.length() && s[i] == s[i+1]) {
                cnt++;
                i++;
            }
            res += mp[s[i]]*cnt;
        }
    }
    return res;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s("LVIII");
    cout<<romanToInt(s);

	return 0;
}


text:
#include <bits/stdc++.h>
using namespace std;
typedef long long  int ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define PRIME 1000000007
#define REP(i, a, b) for (int i = a; i < b; ++i)
#define REPR(i, a, b) for (int i = a; i >= b; i--)
const int SIZE = 1e5 + 5;

// calculates longest proper prefix which is also a proper suffix.
// see https://cp-algorithms.com/string/prefix-function.html for more details

vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s("abab");
    cout<<prefix_function(s).back();

	return 0;
}


text:
#include <iostream>
using namespace std;

void replaceCharacter(char input[], char c1, char c2) {

    if(input[0]=='\0')
        return;
    if(input[0]!=c1)
        replaceCharacter(input+1,c1,c2);
    else{
        input[0]=c2;
        replaceCharacter(input+1,c1,c2);

}
}

int main() {
    char input[1000000];
    char c1, c2;
    cin >> input;
    cin >> c1 >> c2;
    replaceCharacter(input, c1, c2);
    cout << input << endl;
}


text:
//Given two strings we need to find out the length of the largest common subsequence and return the value .

  #include <stdio.h>

  void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
  }

  void heapify(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;

    if (largest != i) {
      swap(&arr[i], &arr[largest]);
      heapify(arr, n, largest);
    }
  }

  void heapSort(int arr[], int n) {
    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(int arr[], int n) {
    for (int i = 0; i < n; ++i)
      printf("%d ", arr[i]);
    printf("\n");
  }

  int main() {
    int arr[] = {1, 12, 9, 5, 6, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    printf("Sorted array is \n");
    printArray(arr, n);
  }

// Input :
// abcd
// bcad

//Output:
//LCS of abcd and bcad is 3


text:
// 450dsa q20 : Given a sentence in the form of a string, convert it into its equivalent mobile numeric keypad sequence.

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

string printSequence(string str[], string input)
{
    string output = "";
    int n = input.length();
    for (int i = 0; i < n; i++)
    {
        if (input[i] == ' ')
        {
            output += "0";
        }
        else
        {
            int pos = input[i] - 'A';
            output += str[pos];
        }
    }
    return output;
}

int main()
{
    string str[] = {"2", "22", "222",
                    "3", "33", "333",
                    "4", "44", "444",
                    "5", "55", "555",
                    "6", "66", "666",
                    "7", "77", "777", "7777",
                    "8", "88", "888",
                    "9", "99", "999", "9999"};

    string input = "CHAMAN";
    cout << printSequence(str, input);
    return 0;
}


text:
import java.util.Scanner;

public class Pallindrome {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //for integer input
        System.out.println("Enter a number to check palindrome: ");
        int ip = sc.nextInt();
        int x=ip;
        int y=0;
        while(x>0){
            int z=x%10;
            y=y*10+z;
            x=x/10;
        }
        if (ip==y){
            System.out.println("Palindrome Found");
        } else {
            System.out.println("Not a Palindrome");
        }

        //for string input
        System.out.println("Enter a String to check palindrome: ");
        String input= sc.next();
        StringBuilder reverse= new StringBuilder();
        for(int i=(input.length())-1; i>=0; i--){
            reverse.append(input.charAt(i));
        }
        System.out.println(input);
        System.out.println(reverse);
        if(reverse.toString().equals(input)){
            System.out.println("Palindrome Found");
        } else {
            System.out.println("Not a Palindrome");
        }
    }
}


text:
#include <iostream>
#include <unordered_map>
#include <cstring>
#include <vector>
using namespace std;
class node
{
public:
    char ch;
    bool isterminal;
    unordered_map<char, node *> h;
    node(char c)
    {
        ch = c;
        isterminal = false;
    }
};
class Trie
{
public:
    node *root;
    Trie()
    {
        root = new node('\0');
    }
    void addWord(char *word)
    {
        node *temp = root;
        for (int i = 0; word[i]; i++)
        {
            char ch = word[i];
            if (temp->h.count(ch))
            {
                temp = temp->h[ch];
            }
            else
            {
                node *n = new node(ch);
                temp->h[ch] = n;
                temp = n;
            }
        }
        temp->isterminal = true;
    }
    bool searchWord(char *word)
    {
        node *temp = root;
        for (int i = 0; word[i]; i++)
        {
            char ch = word[i];
            if (temp->h.count(ch) == 1)
            {
                temp = temp->h[ch];
            }
            else
            {
                return false;
            }
        }
        return temp->isterminal;
    }
    void findallwords(node *temp, string &x, vector<string> &ans)
    {
        // base case
        if (temp->isterminal == true)
        {
            ans.push_back(x);
        }
        // recursive case
        for (auto p : temp->h)
        {
            x.push_back(p.first);
            findallwords(p.second, x, ans);
            x.pop_back();
        }
    }
    void autofill(char *initial)
    {
        node *temp = root;
        for (int i = 0; initial[i]; i++)
        {
            char ch = initial[i];
            if (temp->h.count(ch) == 1)
            {
                temp = temp->h[ch];
            }
            else
            {
                return;
            }
        }
        string x(initial);
        vector<string> ans;
        findallwords(temp, x, ans);
        for (auto W : ans)
        {
            cout << W << endl;
        }
    }
};
int main()
{
    Trie t;
    t.addWord("Hello");
    t.addWord("Heman");
    t.addWord("Hell");
    t.addWord("Hero");
    t.addWord("Heart");

    t.addWord("Code");
    t.addWord("Coder");
    t.addWord("Coders");
    // char word[100] = "Code";
    // if (t.searchWord(word))
    // {
    //     cout << "Present hai\n";
    // }
    // else
    // {
    //     cout << "Present nahi hai\n";
    // }
    char initial[] = "He";
    t.autofill(initial);
    return 0;
}


text:
#  courtesy = freeCodeCamp.org  (youtube)
#  Library = Tkinter

from tkinter import *
from tkinter.font import Font
from typing import Match
root= Tk()
root.title('DMAS Calculator')

#creating input field
e=Entry(root,  width=35, borderwidth=5, bg='white', fg='purple')
e.grid(row=0, column=0, columnspan=3,padx=10, pady=10)

#Defining the Functions
def button_click(number):
    c=e.get()
    e.delete(0,END)
    e.insert(0, str(c)+str(number))

def button_clear():
    e.delete(0,END)

def button_add():
    first_number=e.get()
    global f_num
    global m
    m= 'add'
    f_num = int(first_number)
    e.delete(0,END)

def button_subtract():
    first_number=e.get()
    global f_num
    global m
    m= 'subs'
    f_num = int(first_number)
    e.delete(0,END)

def button_multiply():
    first_number=e.get()
    global f_num
    global m
    m= 'multiply'
    f_num = int(first_number)
    e.delete(0,END)

def button_divide():
    first_number=e.get()
    global f_num
    global m
    m='divide'
    f_num = int(first_number)
    e.delete(0,END)

def button_equal():
    second_number=e.get()
    e.delete(0, END)

    if m=='add' :        #f_num of add is in action. It means we have to add
        e.insert(0, f_num + int(second_number))
    if m=='subs' :        #f_num of subs is in action. It means we have to subtract
        e.insert(0, f_num - int(second_number))
    if m=='multiply' :        #f_num of multiply is in action. It means we have to multiply
        e.insert(0, f_num * int(second_number))
    if m=='divide' :        #f_num of divide is in action. It means we have to divide
        e.insert(0, f_num / int(second_number))

#defining the global variable
m='hello'

#Defining the buttons
button_1=Button(root, text='1',padx=40, pady=20, command= lambda:button_click(1), bg='cyan', fg='red')
button_2=Button(root, text='2',padx=40, pady=20, command= lambda:button_click(2),bg='cyan', fg='red')
button_3=Button(root, text='3',padx=40, pady=20, command= lambda:button_click(3),bg='cyan', fg='red')
button_4=Button(root, text='4',padx=40, pady=20, command= lambda:button_click(4),bg='cyan', fg='red')
button_5=Button(root, text='5',padx=40, pady=20, command= lambda:button_click(5),bg='cyan', fg='red')
button_6=Button(root, text='6',padx=40, pady=20, command= lambda:button_click(6),bg='cyan', fg='red')
button_7=Button(root, text='7',padx=40, pady=20, command= lambda:button_click(7),bg='cyan', fg='red')
button_8=Button(root, text='8',padx=40, pady=20, command= lambda:button_click(8),bg='cyan', fg='red')
button_9=Button(root, text='9',padx=40, pady=20, command= lambda:button_click(9),bg='cyan', fg='red')
button_0=Button(root, text='0',padx=40, pady=20, command= lambda:button_click(0),bg='cyan', fg='red')
button_clear=Button(root, text='CLEAR',padx=73, pady=20, command=button_clear,bg='pink', fg='red')
button_add=Button(root, text='+',padx=39, pady=20, command=button_add, bg='pink', fg='red')
button_equal=Button(root, text='=',padx=86.49, pady=20, command=button_equal, bg='pink', fg='red')

button_subs=Button(root, text='-',padx=40, pady=20, command=button_subtract,bg='pink', fg='red')
button_mul=Button(root, text='X',padx=40, pady=20, command=button_multiply,bg='pink', fg='red')
button_div=Button(root, text='/',padx=40, pady=20, command=button_divide,bg='pink', fg='red')

#Shoving the buttons on screen
button_1.grid(row=3,column=0)
button_2.grid(row=3,column=1)
button_3.grid(row=3,column=2)

button_4.grid(row=2,column=0)
button_5.grid(row=2,column=1)
button_6.grid(row=2,column=2)

button_7.grid(row=1,column=0)   #row=1  as row=1 is for input field
button_8.grid(row=1,column=1)
button_9.grid(row=1,column=2)

button_0.grid(row=4,column=0)
button_clear.grid(row=4,column=1, columnspan=2)
button_add.grid(row=5,column=0)
button_equal.grid(row=5,column=1, columnspan=2)

button_subs.grid(row=6,column=0)
button_mul.grid(row=6,column=1)
button_div.grid(row=6,column=2)

root.mainloop()


text:
#include<iostream>
#include <list>
#include <stack>
#define NIL -1
using namespace std;

// A class that represents an directed graph
class Graph
{
	int V; // No. of vertices
	list<int> *adj; // A dynamic array of adjacency lists

	// A Recursive DFS based function used by SCC()
	void SCCUtil(int u, int disc[], int low[],
				stack<int> *st, bool stackMember[]);
public:
	Graph(int V); // Constructor
	void addEdge(int v, int w); // function to add an edge to graph
	void SCC(); // prints strongly connected components
};

Graph::Graph(int V)
{
	this->V = V;
	adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
	adj[v].push_back(w);
}

// A recursive function that finds and prints strongly connected
// components using DFS traversal
// u --> The vertex to be visited next
// disc[] --> Stores discovery times of visited vertices
// low[] -- >> earliest visited vertex (the vertex with minimum
//			 discovery time) that can be reached from subtree
//			 rooted with current vertex
// *st -- >> To store all the connected ancestors (could be part
//		 of SCC)
// stackMember[] --> bit/index array for faster check whether
//				 a node is in stack
void Graph::SCCUtil(int u, int disc[], int low[], stack<int> *st,
					bool stackMember[])
{
	// A static variable is used for simplicity, we can avoid use
	// of static variable by passing a pointer.
	static int time = 0;

	// Initialize discovery time and low value
	disc[u] = low[u] = ++time;
	st->push(u);
	stackMember[u] = true;

	// Go through all vertices adjacent to this
	list<int>::iterator i;
	for (i = adj[u].begin(); i != adj[u].end(); ++i)
	{
		int v = *i; // v is current adjacent of 'u'

		// If v is not visited yet, then recur for it
		if (disc[v] == -1)
		{
			SCCUtil(v, disc, low, st, stackMember);

			// Check if the subtree rooted with 'v' has a
			// connection to one of the ancestors of 'u'
			// Case 1 (per above discussion on Disc and Low value)
			low[u] = min(low[u], low[v]);
		}

		// Update low value of 'u' only of 'v' is still in stack
		// (i.e. it's a back edge, not cross edge).
		// Case 2 (per above discussion on Disc and Low value)
		else if (stackMember[v] == true)
			low[u] = min(low[u], disc[v]);
	}

	// head node found, pop the stack and print an SCC
	int w = 0; // To store stack extracted vertices
	if (low[u] == disc[u])
	{
		while (st->top() != u)
		{
			w = (int) st->top();
			cout << w << " ";
			stackMember[w] = false;
			st->pop();
		}
		w = (int) st->top();
		cout << w << "\n";
		stackMember[w] = false;
		st->pop();
	}
}

// The function to do DFS traversal. It uses SCCUtil()
void Graph::SCC()
{
	int *disc = new int[V];
	int *low = new int[V];
	bool *stackMember = new bool[V];
	stack<int> *st = new stack<int>();

	// Initialize disc and low, and stackMember arrays
	for (int i = 0; i < V; i++)
	{
		disc[i] = NIL;
		low[i] = NIL;
		stackMember[i] = false;
	}

	// Call the recursive helper function to find strongly
	// connected components in DFS tree with vertex 'i'
	for (int i = 0; i < V; i++)
		if (disc[i] == NIL)
			SCCUtil(i, disc, low, st, stackMember);
}

// Driver program to test above function
int main()
{
	cout << "\nSCCs in first graph \n";
	Graph g1(5);
	g1.addEdge(1, 0);
	g1.addEdge(0, 2);
	g1.addEdge(2, 1);
	g1.addEdge(0, 3);
	g1.addEdge(3, 4);
	g1.SCC();

	cout << "\nSCCs in second graph \n";
	Graph g2(4);
	g2.addEdge(0, 1);
	g2.addEdge(1, 2);
	g2.addEdge(2, 3);
	g2.SCC();

	cout << "\nSCCs in third graph \n";
	Graph g3(7);
	g3.addEdge(0, 1);
	g3.addEdge(1, 2);
	g3.addEdge(2, 0);
	g3.addEdge(1, 3);
	g3.addEdge(1, 4);
	g3.addEdge(1, 6);
	g3.addEdge(3, 5);
	g3.addEdge(4, 5);
	g3.SCC();

	cout << "\nSCCs in fourth graph \n";
	Graph g4(11);
	g4.addEdge(0,1);g4.addEdge(0,3);
	g4.addEdge(1,2);g4.addEdge(1,4);
	g4.addEdge(2,0);g4.addEdge(2,6);
	g4.addEdge(3,2);
	g4.addEdge(4,5);g4.addEdge(4,6);
	g4.addEdge(5,6);g4.addEdge(5,7);g4.addEdge(5,8);g4.addEdge(5,9);
	g4.addEdge(6,4);
	g4.addEdge(7,9);
	g4.addEdge(8,9);
	g4.addEdge(9,8);
	g4.SCC();

	cout << "\nSCCs in fifth graph \n";
	Graph g5(5);
	g5.addEdge(0,1);
	g5.addEdge(1,2);
	g5.addEdge(2,3);
	g5.addEdge(2,4);
	g5.addEdge(3,0);
	g5.addEdge(4,2);
	g5.SCC();

	return 0;
}


text:
import random # For generating random numbers
import sys # We will use sys.exit to exit the program
import pygame
from pygame.locals import * # Basic pygame imports

# Global Variables for the game
FPS = 32
SCREENWIDTH = 289
SCREENHEIGHT = 511
SCREEN = pygame.display.set_mode((SCREENWIDTH, SCREENHEIGHT))
GROUNDY = SCREENHEIGHT * 0.8
GAME_SPRITES = {}
GAME_SOUNDS = {}
PLAYER = 'gallery/sprites/bird.png'
BACKGROUND = 'gallery/sprites/background.png'
PIPE = 'gallery/sprites/pipe.png'

def welcomeScreen():
    """
    Shows welcome images on the screen
    """

    playerx = int(SCREENWIDTH/5)
    playery = int((SCREENHEIGHT - GAME_SPRITES['player'].get_height())/2)
    messagex = int((SCREENWIDTH - GAME_SPRITES['message'].get_width())/2)
    messagey = int(SCREENHEIGHT*0.13)
    basex = 0
    while True:
        for event in pygame.event.get():
            # if user clicks on cross button, close the game
            if event.type == QUIT or (event.type==KEYDOWN and event.key == K_ESCAPE):
                pygame.quit()
                sys.exit()

            # If the user presses space or up key, start the game for them
            elif event.type==KEYDOWN and (event.key==K_SPACE or event.key == K_UP):
                return
            else:
                SCREEN.blit(GAME_SPRITES['background'], (0, 0))
                SCREEN.blit(GAME_SPRITES['player'], (playerx, playery))
                SCREEN.blit(GAME_SPRITES['message'], (messagex,messagey ))
                SCREEN.blit(GAME_SPRITES['base'], (basex, GROUNDY))
                pygame.display.update()
                FPSCLOCK.tick(FPS)

def mainGame():
    score = 0
    playerx = int(SCREENWIDTH/5)
    playery = int(SCREENWIDTH/2)
    basex = 0

    # Create 2 pipes for blitting on the screen
    newPipe1 = getRandomPipe()
    newPipe2 = getRandomPipe()

    # my List of upper pipes
    upperPipes = [
        {'x': SCREENWIDTH+200, 'y':newPipe1[0]['y']},
        {'x': SCREENWIDTH+200+(SCREENWIDTH/2), 'y':newPipe2[0]['y']},
    ]
    # my List of lower pipes
    lowerPipes = [
        {'x': SCREENWIDTH+200, 'y':newPipe1[1]['y']},
        {'x': SCREENWIDTH+200+(SCREENWIDTH/2), 'y':newPipe2[1]['y']},
    ]

    pipeVelX = -4

    playerVelY = -9
    playerMaxVelY = 10
    playerMinVelY = -8
    playerAccY = 1

    playerFlapAccv = -8 # velocity while flapping
    playerFlapped = False # It is true only when the bird is flapping

    while True:
        for event in pygame.event.get():
            if event.type == QUIT or (event.type == KEYDOWN and event.key == K_ESCAPE):
                pygame.quit()
                sys.exit()
            if event.type == KEYDOWN and (event.key == K_SPACE or event.key == K_UP):
                if playery > 0:
                    playerVelY = playerFlapAccv
                    playerFlapped = True
                    GAME_SOUNDS['wing'].play()

        crashTest = isCollide(playerx, playery, upperPipes, lowerPipes) # This function will return true if the player is crashed
        if crashTest:
            return

        #check for score
        playerMidPos = playerx + GAME_SPRITES['player'].get_width()/2
        for pipe in upperPipes:
            pipeMidPos = pipe['x'] + GAME_SPRITES['pipe'][0].get_width()/2
            if pipeMidPos<= playerMidPos < pipeMidPos +4:
                score +=1
                print(f"Your score is {score}")
                GAME_SOUNDS['point'].play()

        if playerVelY <playerMaxVelY and not playerFlapped:
            playerVelY += playerAccY

        if playerFlapped:
            playerFlapped = False
        playerHeight = GAME_SPRITES['player'].get_height()
        playery = playery + min(playerVelY, GROUNDY - playery - playerHeight)

        # move pipes to the left
        for upperPipe , lowerPipe in zip(upperPipes, lowerPipes):
            upperPipe['x'] += pipeVelX
            lowerPipe['x'] += pipeVelX

        # Add a new pipe when the first is about to cross the leftmost part of the screen
        if 0<upperPipes[0]['x']<5:
            newpipe = getRandomPipe()
            upperPipes.append(newpipe[0])
            lowerPipes.append(newpipe[1])

        # if the pipe is out of the screen, remove it
        if upperPipes[0]['x'] < -GAME_SPRITES['pipe'][0].get_width():
            upperPipes.pop(0)
            lowerPipes.pop(0)

        # Lets blit our sprites now
        SCREEN.blit(GAME_SPRITES['background'], (0, 0))
        for upperPipe, lowerPipe in zip(upperPipes, lowerPipes):
            SCREEN.blit(GAME_SPRITES['pipe'][0], (upperPipe['x'], upperPipe['y']))
            SCREEN.blit(GAME_SPRITES['pipe'][1], (lowerPipe['x'], lowerPipe['y']))

        SCREEN.blit(GAME_SPRITES['base'], (basex, GROUNDY))
        SCREEN.blit(GAME_SPRITES['player'], (playerx, playery))
        myDigits = [int(x) for x in list(str(score))]
        width = 0
        for digit in myDigits:
            width += GAME_SPRITES['numbers'][digit].get_width()
        Xoffset = (SCREENWIDTH - width)/2

        for digit in myDigits:
            SCREEN.blit(GAME_SPRITES['numbers'][digit], (Xoffset, SCREENHEIGHT*0.12))
            Xoffset += GAME_SPRITES['numbers'][digit].get_width()
        pygame.display.update()
        FPSCLOCK.tick(FPS)

def isCollide(playerx, playery, upperPipes, lowerPipes):
    if playery> GROUNDY - 25  or playery<0:
        GAME_SOUNDS['hit'].play()
        return True

    for pipe in upperPipes:
        pipeHeight = GAME_SPRITES['pipe'][0].get_height()
        if(playery < pipeHeight + pipe['y'] and abs(playerx - pipe['x']) < GAME_SPRITES['pipe'][0].get_width()):
            GAME_SOUNDS['hit'].play()
            return True

    for pipe in lowerPipes:
        if (playery + GAME_SPRITES['player'].get_height() > pipe['y']) and abs(playerx - pipe['x']) < GAME_SPRITES['pipe'][0].get_width():
            GAME_SOUNDS['hit'].play()
            return True

    return False

def getRandomPipe():
    """
    Generate positions of two pipes(one bottom straight and one top rotated ) for blitting on the screen
    """
    pipeHeight = GAME_SPRITES['pipe'][0].get_height()
    offset = SCREENHEIGHT/3
    y2 = offset + random.randrange(0, int(SCREENHEIGHT - GAME_SPRITES['base'].get_height()  - 1.2 *offset))
    pipeX = SCREENWIDTH + 10
    y1 = pipeHeight - y2 + offset
    pipe = [
        {'x': pipeX, 'y': -y1}, #upper Pipe
        {'x': pipeX, 'y': y2} #lower Pipe
    ]
    return pipe

if __name__ == "__main__":
    # This will be the main point from where our game will start
    pygame.init() # Initialize all pygame's modules
    FPSCLOCK = pygame.time.Clock()
    pygame.display.set_caption('Flappy Bird by CodeWithHarry')
    GAME_SPRITES['numbers'] = (
        pygame.image.load('gallery/sprites/0.png').convert_alpha(),
        pygame.image.load('gallery/sprites/1.png').convert_alpha(),
        pygame.image.load('gallery/sprites/2.png').convert_alpha(),
        pygame.image.load('gallery/sprites/3.png').convert_alpha(),
        pygame.image.load('gallery/sprites/4.png').convert_alpha(),
        pygame.image.load('gallery/sprites/5.png').convert_alpha(),
        pygame.image.load('gallery/sprites/6.png').convert_alpha(),
        pygame.image.load('gallery/sprites/7.png').convert_alpha(),
        pygame.image.load('gallery/sprites/8.png').convert_alpha(),
        pygame.image.load('gallery/sprites/9.png').convert_alpha(),
    )

    GAME_SPRITES['message'] =pygame.image.load('gallery/sprites/message.png').convert_alpha()
    GAME_SPRITES['base'] =pygame.image.load('gallery/sprites/base.png').convert_alpha()
    GAME_SPRITES['pipe'] =(pygame.transform.rotate(pygame.image.load( PIPE).convert_alpha(), 180),
    pygame.image.load(PIPE).convert_alpha()
    )

    # Game sounds
    GAME_SOUNDS['die'] = pygame.mixer.Sound('gallery/audio/die.wav')
    GAME_SOUNDS['hit'] = pygame.mixer.Sound('gallery/audio/hit.wav')
    GAME_SOUNDS['point'] = pygame.mixer.Sound('gallery/audio/point.wav')
    GAME_SOUNDS['swoosh'] = pygame.mixer.Sound('gallery/audio/swoosh.wav')
    GAME_SOUNDS['wing'] = pygame.mixer.Sound('gallery/audio/wing.wav')

    GAME_SPRITES['background'] = pygame.image.load(BACKGROUND).convert()
    GAME_SPRITES['player'] = pygame.image.load(PLAYER).convert_alpha()

    while True:
        welcomeScreen() # Shows welcome screen to the user until he presses a button
        mainGame() # This is the main game function


text:
#include<iostream>
using namespace std;
int main()
{
	int rows;
	cout << "Enter number of rows\n";
	cin >> rows;
	for (int i = 1; i < rows; i++)
	{
		for (int j = 1; j <= rows - i; j++)
		{
			cout << " ";
		}
		for (int k = 0; k <= i * 2 - 1; k++)
		{
			if (k == 1 || k == i * 3 - 1)
			{
				cout << "*";
			}
			else {
				cout << " ";
			}
		}
		cout << endl;
	}
	for (int i = rows - 1; i > 0; i--)
	{
		for (int j = 1; j <= rows - i; j++)
		{
			cout << " ";
		}
		for (int k = 1; k <= i * 2 - 1; k++)
		{
			if (k == 1 || k == i * 2 - 1)
			{
				cout << "*";
			}
			else {
				cout << " ";
			}
		}
		cout << endl;
	}
	return 0;
}


text:
package mymath;
import java.util.Scanner;
class Trig
{
    double degree,rad;
    Trig(double degree)
    {
        this.degree=degree;
        this.rad=Math.toRadians(this.degree);
    }
    double sin_of_angle()
    {
        return Math.sin(rad);
    }
    double cos_of_angle()
    {
        return Math.cos(rad);
    }
    double tan_of_angle()
    {
        return Math.tan(rad);
    }
    double cosec_of_angle()
    {
        return (1/Math.sin(rad));
    }
    double sec_of_angle()
    {
        return (1/Math.cos(rad));
    }
    double cot_of_angle()
    {
        return (1/Math.tan(rad));
    }
}
class Algebra
{
    float a,b;
    Algebra(float a,float b)
    {
        this.a=a;
        this.b=b;
    }
    float add()
    {
        return (a+b);
    }
    float sub()
    {
        return (a-b);
    }
    float multiply()
    {
        return (a*b);
    }
    float divide()
    {
        return (a/b);
    }
}
class Stat
{
    int size;
    int []arr;
    Stat(int size,int[] arr)
    {
        this.size=size;
        this.arr=arr;
    }
    int mini()
    {
        int min = arr[0];
        for (int i = 0; i < arr.length; i++)
        {
            if(arr[i] <min)
            {
               min = arr[i];
            }
        }
        return min;
    }
    int maxi()
    {
        int max = arr[0];
        for (int i = 0; i < arr.length; i++)
        {
            if(arr[i] > max)
            {
               max = arr[i];
            }
        }
        return max;
    }
    double sum()
    {
        double sum=0;
        for(int i=0;i<size;i++)
        {
            sum+=arr[i];
        }
        return sum;
    }

    double avg()
    {
        return this.sum()/this.size;
    }
}
class PackDemo
{
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        while(true)
        {
            System.out.println("1.Trignometry\n2.Algebra\n3.Statistic\n4.Exit");
            int ch = sc.nextInt();
            switch(ch)
            {
                case 1: System.out.print("Enter the angle in degree :");
                        double degree=sc.nextDouble();
                        Trig t=new Trig(degree);
                        System.out.println("Sine of angle "+degree+" dregree = "+t.sin_of_angle());
                        System.out.println("Cosineof angle "+degree+" dregree = "+t.cos_of_angle());
                        System.out.println("Tangent of angle "+degree+" dregree = "+t.tan_of_angle());
                        System.out.println("Cosecant of angle "+degree+" dregree = "+t.cosec_of_angle());
                        System.out.println("Secant of angle "+degree+" dregree = "+t.sec_of_angle());
                        System.out.println("Cotangent of angle "+degree+" dregree = "+t.cot_of_angle());
                        break;
                case 2: System.out.print("Enter Any two floating point number : ");
                        float a=sc.nextFloat();
                        float b=sc.nextFloat();
                        Algebra alg=new Algebra(a,b);
                        System.out.println(a+" + "+b +" = "+alg.add());
                        System.out.println(a+" - "+b +" = "+alg.sub());
                        System.out.println(a+" * "+b +" = "+alg.multiply());
                        System.out.println(a+" / "+b +" = "+alg.divide());
                        break;
                case 3:
                        System.out.print("Enter the no.of entries:");
                        int size=sc.nextInt();
                        System.out.print("Enter the data :");
                        int[] arr=new int[size];
                        for(int i=0;i<size;i++)
                        {
                            arr[i]=sc.nextInt();
                        }
                        Stat st=new Stat(size, arr);
                        System.out.println("Minimum= "+st.mini());
                        System.out.println("Maximum= "+st.maxi());
                        System.out.println("Sum= "+st.sum());
                        System.out.println("Average= "+st.avg());
                        break;
                case 4:
                        System.exit(0);
            }
        }
    }
}


text:
import java.util.*;
public class Main
{
    public static int complimentOfBase10Integer(int x){
        int y=0;
        int x1=x;
        while(x!=0){
            x=x>>1;
            y=y<<1;
            y=y|1;
        }
        int x2=~x1;
        int z=x2&y;
        return z;
    }
	public static void main(String[] args) {
	 int x=5;
	 Main obj=new Main();
	 int num=obj.complimentOfBase10Integer(x);
	 System.out.print(num);
	}
}


text:
#include <iostream>
using namespace std;

class Factorial
{
private:
    int num;
    int factorial = 1;

public:
    void calculateFactorial();
    void show();
};

void
Factorial::calculateFactorial()
{
    cout << "Enter a number : " << endl;
    cin >> num;

    if (num == 0 || num == 1)
    {
        factorial = 1;
    }
    else
    {
        while (num > 1)
        {
            factorial = factorial * num;
            num--;
        }
    }
}

void Factorial::show()
{
    cout << "Factorial : " << factorial << endl;
}

int main()
{
    Factorial factorial;
    factorial.calculateFactorial();
    factorial.show();
}


text:
document.addEventListener("DOMContentLoaded", () => {
  const grid = document.querySelector(".grid");
  let width = 10;
  let squares = [];
  let bombCount = 20;
  let isGameOver = false;
  let flags = 0;
  const restart = document.getElementById("restart");
  let shuffledArray;
  // create board
  function createBoard() {
    isGameOver = false;
    document.getElementById('result').innerHTML = '';
    grid.innerHTML = "";
    squares = [];
    // get shuffled game array with random bombs
    const bombsArray = Array(bombCount).fill("bomb");
    const emptyArray = Array(width * width - bombCount).fill("valid");

    const gameArray = emptyArray.concat(bombsArray);

    shuffledArray = gameArray.sort(() => Math.random() - 0.5);

    for (let i = 0; i < width * width; i++) {
      const square = document.createElement("div");
      square.setAttribute("id", i);
      // console.log(square);
      // square.classList.add(shuffledArray[i]);
      grid.appendChild(square);
      squares.push(square);

      // normal click
      square.addEventListener("click", function (e) {
        click(square);
      });

      // cntrl and left click
      square.oncontextmenu = function (e) {
        e.preventDefault();
        addFlag(square);
      };
    }

    // add Numbers
    for (let i = 0; i < squares.length; i++) {
      let total = 0;
      const isLeftEdge = i % width === 0;
      const isRightEdge = i % width === width - 1;

      if (shuffledArray[i] == "valid") {
        if (i > 0 && !isLeftEdge && shuffledArray[i-1] == "bomb")
          total++;
        if (i > 9 && !isRightEdge && shuffledArray[i + 1 - width] == "bomb")
          total++;
        if (i > 10 && shuffledArray[i - width] == "bomb")
           total++;
        if (
          i > 11 &&
          !isLeftEdge &&
          shuffledArray[i - 1 - width] == "bomb"
        )
          total++;
        if (i < 98 && !isRightEdge && shuffledArray[i + 1] == "bomb")
          total++;
        if (
          i < 90 &&
          !isLeftEdge &&
          shuffledArray[i - 1 + width] == "bomb"
        )
          total++;
        if (
          i < 88 &&
          !isRightEdge &&
          shuffledArray[i + 1 + width] == "bomb"
        )
          total++;
        if (i < 89 && shuffledArray[i + width] == "bomb") total++;
        squares[i].setAttribute("data", total);
      }else{
        squares[i].setAttribute("data", 0);
      }
    }
  }

  // add Flag With Right Click
  function addFlag(square) {
    if (isGameOver) return;
    if (!square.classList.contains("checked") && flags < bombCount) {
      if (!square.classList.contains("flag")) {
        square.classList.add("flag");
        square.innerHTML = `<i class="fa fa-flag" aria-hidden="true"></i>`;
        flags++;
        checkForWin();
      } else {
        square.classList.remove("flag");
        square.innerHTML = "";
        flags--;
      }
    }
  }

  createBoard();

  function click(square) {
    let currentId = square.id;
    if (isGameOver){
      return;
    }
    if (
      square.classList.contains("checked") ||
      square.classList.contains("flag")
    )
      return;
    if (shuffledArray[currentId] == "bomb") {
      gameOver(square);
      return;
    } else {
      let total = square.getAttribute("data");
      if (total != 0) {
        square.classList.add("checked");
        square.innerHTML = total;
        return;
      }
      checkSquare(square, currentId);
    }
    square.classList.add("checked");
    checkForWin();
  }

  // checking neighnouring squares
  function checkSquare(square, currentId) {
    const isLeftEdge = currentId % width === 0;
    const isRightEdge = currentId % width === width - 1;

    setTimeout(() => {
      if (currentId > 0 && !isLeftEdge) {
        const newId = squares[parseInt(currentId) - 1].id;
        const newSquare = document.getElementById(newId);
        click(newSquare);
      }
      if (currentId > 9 && !isRightEdge) {
        const newId = squares[parseInt(currentId) + 1 - width].id;
        const newSquare = document.getElementById(newId);
        click(newSquare);
      }
      if (currentId > 10) {
        const newId = squares[parseInt(currentId) - width].id;
        const newSquare = document.getElementById(newId);
        click(newSquare);
      }
      if (currentId > 11 && !isLeftEdge) {
        const newId = squares[parseInt(currentId) - 1 - width].id;
        const newSquare = document.getElementById(newId);
        click(newSquare);
      }
      if (currentId < 98 && !isRightEdge) {
        const newId = squares[parseInt(currentId) + 1].id;
        const newSquare = document.getElementById(newId);
        click(newSquare);
      }

      if (currentId < 90 && !isLeftEdge) {
        const newId = squares[parseInt(currentId) - 1 + width].id;
        const newSquare = document.getElementById(newId);
        click(newSquare);
      }
      if (currentId < 88 && !isRightEdge) {
        const newId = squares[parseInt(currentId) + 1 + width].id;
        const newSquare = document.getElementById(newId);
        click(newSquare);
      }
      if (currentId < 89) {
        const newId = squares[parseInt(currentId) + width].id;
        const newSquare = document.getElementById(newId);
        click(newSquare);
      }
    }, 10);
  }

  function gameOver(square) {
    isGameOver = true;

    // show all bombs
    squares.forEach((sq) => {
      if (shuffledArray[sq.id] == "bomb") {
        sq.innerHTML = '<i class="fa fa-bomb" aria-hidden="true"></i>';
        sq.classList.add("exploded");
      }
    });
    document.getElementById('result').innerHTML = 'You lose!!!!!!!';
  }

  function checkForWin() {
    let matches = 0, emptySquares = 0;
    for (let i = 0; i < squares.length; i++) {
      if (
        shuffledArray[i] == "bomb" &&
        squares[i].classList.contains("flag")
      ) {
        matches++;
      }
      if(shuffledArray[i] == "valid" && squares[i].classList.contains("checked"))
        emptySquares++;
      if (matches == bombCount || emptySquares == 100 - bombCount) {
        document.getElementById('result').innerHTML = "You Win!!!!!!!!!!!!!!";
        isGameOver = true;
      }
    }
  }

  restart.addEventListener("click", function (e) {
    e.preventDefault();
    createBoard();
  });
});


text:
<!DOCTYPE html>

    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/font-awesome/4.7.0/css/font-awesome.min.css">
    <link rel="stylesheet" href="style.css">

    <title>Minesweeper</title>

MineSweeper

Instructions

Right Click To Flag a block

Left Click to Open a Block

                <button class="m-auto" type="button" id="restart">Restart</button>


text:
body {
  background-color: navajowhite;
}

header{
    background-color: paleturquoise;
    box-shadow: 10px 10px palegreen;
    height: 150px;
    margin: 20px 30px 30px 30px;
    font-size: 60px;
    width: auto;
}

@media only screen and (max-width: 770px) {
  header {
    font-size: 50px;
  }
}

@media only screen and (max-width: 670px) {
  header {
    font-size: 35px;
  }
}

header h1{
    color: royalblue;
    height: 100px;
    margin: 0;
}

.content-box{
  display: flex;
  align-items: center;
  justify-content: space-around;
  flex-wrap: wrap;
}

.grid {
    margin: auto;
    height: 400px;
    width: 400px;
    display: flex;
    flex-wrap: wrap;
    background-color: gray;
}

.grid div{
    height: 36px;
    width: 36px;
    border: 2px solid black;
    box-shadow: inset 3px 3px white;
}

.details{
  margin-top: 10px;
  padding: 20px;
  background-color: rgb(226, 225, 225);
}

.details ul {
  margin: 30px 0;
}

.checked{
    background-color: palegreen;
}

.exploded {
    background-color: orange;
}

.button{
    width: 100px;
    margin: auto;
}

button{
    background-color: rgb(208, 211, 23);
    font-size: 20px;
    font-family: 'Lucida Sans', 'Lucida Sans Regular', 'Lucida Grande', 'Lucida Sans Unicode', Geneva, Verdana, sans-serif;
    padding: 16px;
    border-radius: 20%;
    border: solid 3px rgb(21, 31, 7);
    box-shadow: inset 3px 3px 10px 5px rgb(116, 226, 43);
}


text:
#include<bits/stdc++.h>
using namespace std;
struct TrieNode{
    bool isEnd;
    TrieNode *child[26];
    TrieNode(){
        for(int i=0;i<26;i++){
            child[i]=NULL;
        }
        isEnd=false;
    }
};

class Trie {
public:
    TrieNode *root;
    /** Initialize your data structure here. */
    Trie() {
        root=NULL;
    }

    /** Inserts a word into the trie. */
    void insert(string word) {
        int ind;
        if(!this->root){
            this->root=new TrieNode();
        }
        TrieNode *t=this->root;
        for(int i=0;i<word.size();i++){
            ind=word[i]-'a';
            if(!t->child[ind]){
                t->child[ind] = new TrieNode();
            }
            t=t->child[ind];
        }
        t->isEnd=true;
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        int ind;
        if(!this->root){
            return false;
        }
        TrieNode *t=this->root;
        for(int i=0;i<word.size();i++){
            ind=word[i]-'a';
            if(!t->child[ind]){
                return false;
            }
            t=t->child[ind];
        }
        return t->isEnd;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        int ind;
        if(!this->root){
            return false;
        }
        TrieNode *t=this->root;
        for(int i=0;i<prefix.size();i++){
            ind=prefix[i]-'a';
            if(!t->child[ind]){
                return false;
            }
            t=t->child[ind];
        }
        return true;
    }
};

int main(){
  /**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */
}


text:
# Scaling (Resizing) Images - Cubic, Area, Linear Interpolations
# Interpolation is a method of estimating values between known data points

# Import Computer Vision package - cv2
import cv2

# Import Numerical Python package - numpy as np
import numpy as np

# Read the image using imread built-in function
image = cv2.imread('image_2.jpg')

# Display original image using imshow built-in function
cv2.imshow("Original", image)

# Wait until any key is pressed
cv2.waitKey()

# cv2.resize(image, output image size, x scale, y scale, interpolation)

# Scaling using cubic interpolation
scaling_cubic = cv2.resize(image, None, fx=.75, fy=.75, interpolation = cv2.INTER_CUBIC)

# Display cubic interpolated image
cv2.imshow('Cubic Interpolated', scaling_cubic)

# Wait until any key is pressed
cv2.waitKey()

# Scaling using area interpolation
scaling_skewed = cv2.resize(image, (600, 300), interpolation = cv2.INTER_AREA)

# Display area interpolated image
cv2.imshow('Area Interpolated', scaling_skewed)

# Wait until any key is pressed
cv2.waitKey()

# Scaling using linear interpolation
scaling_linear  = cv2.resize(image, None, fx=0.5, fy=0.5, interpolation = cv2.INTER_LINEAR)

# Display linear interpolated image
cv2.imshow('Linear Interpolated', scaling_linear)

# Wait until any key is pressed
cv2.waitKey()

# Close all windows
cv2.destroyAllWindows()


text:
# Flipping Images - Horizontally, Vertically, Horizontally & Vertically

# Import Computer Vision package - cv2
import cv2

# Read the image using imread built in function
image = cv2.imread('image_1.jpg')

# Display original image using imshow built in function
cv2.imshow("Original-Press any Key to contd", image)

# Wait until any key is pressed
cv2.waitKey(0)

# cv2.flip is used to flip images
# Horizontal flipping of images using value '1'
flipping = cv2.flip(image, 1)

# Display horizontally flipped image
cv2.imshow("Horizontal Flipping", flipping)

# Wait until any key is pressed
cv2.waitKey(0)

# Vertical flipping of images using value '0'
flipping = cv2.flip(image, 0)

# Display vertically flipped image
cv2.imshow("Vertical Flipping", flipping)

# Wait until any key is pressed
cv2.waitKey(0)

# Horizontal & Vertical flipping of images using value '-1'
flipping = cv2.flip(image, -1)

# Display horizontally & vertically flipped image
cv2.imshow("Horizontal & Vertical Flipping", flipping)

# Wait until any key is pressed
cv2.waitKey(0)

# Close all windows
cv2.destroyAllWindows()


text:
# Varying Brightness of Images using Add and Subtract Operations

# Import Computer Vision package - cv2
import cv2

# Import Numerical Python package - numpy as np
import numpy as np

# Read the image using imread built-in function
image = cv2.imread('image_2.jpg')

# Display original image using imshow built-in function
cv2.imshow("Original", image)

# Wait until any key is pressed
cv2.waitKey(0)

# np.ones returns an array of given shape and type, filled with ones
# np.ones(shape, dtype)

matrix = np.ones(image.shape, dtype = "uint8") * 120
# image.shape: gives takes the shape of original image
# uint8: unsigned integer (0 to 255)
# matrix: contains ones, having same dimension as original image but mutlipied by 120

# Adding matrix to orginal image, increases brightness
add = cv2.add(image, matrix)

# Display added image
cv2.imshow("Added", add)

# Wait until any key is pressed
cv2.waitKey(0)

# Subtracting matrix and original image, decreases brightness
subtract = cv2.subtract(image, matrix)

# Display subtracted image
cv2.imshow("Subtracted", subtract)

# Wait untill any key is pressed
cv2.waitKey(0)

# Close all windows
cv2.destroyAllWindows()


text:
// A divide and conquer program in C++
// to find the smallest distance from a
// given set of points.

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

// A structure to represent a Point in 2D plane
class Point
{
	public:
	int x, y;
};

/* Following two functions are needed for library function qsort().
Refer: http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ */

// Needed to sort array of points
// according to X coordinate
int compareX(const void* a, const void* b)
{
	Point *p1 = (Point *)a, *p2 = (Point *)b;
	return (p1->x - p2->x);
}

// Needed to sort array of points according to Y coordinate
int compareY(const void* a, const void* b)
{
	Point *p1 = (Point *)a, *p2 = (Point *)b;
	return (p1->y - p2->y);
}

// A utility function to find the
// distance between two points
float dist(Point p1, Point p2)
{
	return sqrt( (p1.x - p2.x)*(p1.x - p2.x) +
				(p1.y - p2.y)*(p1.y - p2.y)
			);
}

// A Brute Force method to return the
// smallest distance between two points
// in P[] of size n
float bruteForce(Point P[], int n)
{
	float min = FLT_MAX;
	for (int i = 0; i < n; ++i)
		for (int j = i+1; j < n; ++j)
			if (dist(P[i], P[j]) < min)
				min = dist(P[i], P[j]);
	return min;
}

// A utility function to find
// minimum of two float values
float min(float x, float y)
{
	return (x < y)? x : y;
}

// A utility function to find the
// distance beween the closest points of
// strip of given size. All points in
// strip[] are sorted accordint to
// y coordinate. They all have an upper
// bound on minimum distance as d.
// Note that this method seems to be
// a O(n^2) method, but it's a O(n)
// method as the inner loop runs at most 6 times
float stripClosest(Point strip[], int size, float d)
{
	float min = d; // Initialize the minimum distance as d

	qsort(strip, size, sizeof(Point), compareY);

	// Pick all points one by one and try the next points till the difference
	// between y coordinates is smaller than d.
	// This is a proven fact that this loop runs at most 6 times
	for (int i = 0; i < size; ++i)
		for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j)
			if (dist(strip[i],strip[j]) < min)
				min = dist(strip[i], strip[j]);

	return min;
}

// A recursive function to find the
// smallest distance. The array P contains
// all points sorted according to x coordinate
float closestUtil(Point P[], int n)
{
	// If there are 2 or 3 points, then use brute force
	if (n <= 3)
		return bruteForce(P, n);

	// Find the middle point
	int mid = n/2;
	Point midPoint = P[mid];

	// Consider the vertical line passing
	// through the middle point calculate
	// the smallest distance dl on left
	// of middle point and dr on right side
	float dl = closestUtil(P, mid);
	float dr = closestUtil(P + mid, n - mid);

	// Find the smaller of two distances
	float d = min(dl, dr);

	// Build an array strip[] that contains
	// points close (closer than d)
	// to the line passing through the middle point
	Point strip[n];
	int j = 0;
	for (int i = 0; i < n; i++)
		if (abs(P[i].x - midPoint.x) < d)
			strip[j] = P[i], j++;

	// Find the closest points in strip.
	// Return the minimum of d and closest
	// distance is strip[]
	return min(d, stripClosest(strip, j, d) );
}

// The main function that finds the smallest distance
// This method mainly uses closestUtil()
float closest(Point P[], int n)
{
	qsort(P, n, sizeof(Point), compareX);

	// Use recursive function closestUtil()
	// to find the smallest distance
	return closestUtil(P, n);
}

// Driver code
int main()
{
	Point P[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
	int n = sizeof(P) / sizeof(P[0]);
	cout << "The smallest distance is " << closest(P, n);
	return 0;
}


text:
// Inversions in an array
// using Merge Sort (Divide and Conquer Algo)

//Problem LINK : https://practice.geeksforgeeks.org/problems/inversion-of-array-1587115620/1

/* APPROACH :
    If we recall merge sort, we partion array and then subsequently sort and merge left and right array,
    now during the merge process we can easily count inversions as, when we encounter any number in right half smaller than in the left half
    hence all number greater index than current index in the left half of array are greater than the number in right one (the one encountered above),
    and hence we add in the inversion number.
*/
#include <bits/stdc++.h>
using namespace std;

int _mergeSort(int arr[], int temp[], int left, int right);
int merge(int arr[], int temp[], int left, int mid, int right);

/* This function sorts the
   input array and returns the
number of inversions in the array */
int mergeSort(int arr[], int array_size)
{
    int temp[array_size];
    return _mergeSort(arr, temp, 0, array_size - 1);
}

/* An auxiliary recursive function
  that sorts the input array and
returns the number of inversions in the array. */
int _mergeSort(int arr[], int temp[], int left, int right)
{
    int mid, inv_count = 0;
    if (right > left) {
        /* Divide the array into two parts and
        call _mergeSortAndCountInv()
        for each of the parts */
        mid = (right + left) / 2;

        /* Inversion count will be sum of
        inversions in left-part, right-part
        and number of inversions in merging */
        inv_count += _mergeSort(arr, temp, left, mid);
        inv_count += _mergeSort(arr, temp, mid + 1, right);

        /*Merge the two parts*/
        inv_count += merge(arr, temp, left, mid + 1, right);
    }
    return inv_count;
}

/* This funt merges two sorted arrays
and returns inversion count in the arrays.*/
int merge(int arr[], int temp[], int left, int mid,
          int right)
{
    int i, j, k;
    int inv_count = 0;

    i = left; /* i is index for left subarray*/
    j = mid; /* j is index for right subarray*/
    k = left; /* k is index for resultant merged subarray*/
    while ((i <= mid - 1) && (j <= right)) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        }
        else {
            temp[k++] = arr[j++];
            inv_count = inv_count + (mid - i);
        }
    }

/* Copy the remaining elements of left subarray
(if there are any) to temp*/
    while (i <= mid - 1)
        temp[k++] = arr[i++];

    /* Copy the remaining elements of right subarray
       (if there are any) to temp*/
    while (j <= right)
        temp[k++] = arr[j++];

    /*Copy back the merged elements to original array*/
    for (i = left; i <= right; i++)
        arr[i] = temp[i];

    return inv_count;
}

int main()
{
    int arr[] = { 1, 20, 6, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int ans = mergeSort(arr, n);
    cout << " Number of inversions are " << ans;
    return 0;
}
// Inversions in an array
// using Merge Sort (Divide and Conquer Algo)

//Problem LINK : https://practice.geeksforgeeks.org/problems/inversion-of-array-1587115620/1

/* APPROACH :
    If we recall merge sort, we partion array and then subsequently sort and merge left and right array,
    now during the merge process we can easily count inversions as, when we encounter any number in right half smaller than in the left half
    hence all number greater index than current index in the left half of array are greater than the number in right one (the one encountered above),
    and hence we add in the inversion number.
*/
#include <bits/stdc++.h>
using namespace std;

int _mergeSort(int arr[], int temp[], int left, int right);
int merge(int arr[], int temp[], int left, int mid, int right);

/* This function sorts the
   input array and returns the
number of inversions in the array */
int mergeSort(int arr[], int array_size)
{
    int temp[array_size];
    return _mergeSort(arr, temp, 0, array_size - 1);
}

/* An auxiliary recursive function
  that sorts the input array and
returns the number of inversions in the array. */
int _mergeSort(int arr[], int temp[], int left, int right)
{
    int mid, inv_count = 0;
    if (right > left) {
        /* Divide the array into two parts and
        call _mergeSortAndCountInv()
        for each of the parts */
        mid = (right + left) / 2;

        /* Inversion count will be sum of
        inversions in left-part, right-part
        and number of inversions in merging */
        inv_count += _mergeSort(arr, temp, left, mid);
        inv_count += _mergeSort(arr, temp, mid + 1, right);

        /*Merge the two parts*/
        inv_count += merge(arr, temp, left, mid + 1, right);
    }
    return inv_count;
}

/* This funt merges two sorted arrays
and returns inversion count in the arrays.*/
int merge(int arr[], int temp[], int left, int mid,
          int right)
{
    int i, j, k;
    int inv_count = 0;

    i = left; /* i is index for left subarray*/
    j = mid; /* j is index for right subarray*/
    k = left; /* k is index for resultant merged subarray*/
    while ((i <= mid - 1) && (j <= right)) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        }
        else {
            temp[k++] = arr[j++];
            inv_count = inv_count + (mid - i);
        }
    }

/* Copy the remaining elements of left subarray
(if there are any) to temp*/
    while (i <= mid - 1)
        temp[k++] = arr[i++];

    /* Copy the remaining elements of right subarray
       (if there are any) to temp*/
    while (j <= right)
        temp[k++] = arr[j++];

    /*Copy back the merged elements to original array*/
    for (i = left; i <= right; i++)
        arr[i] = temp[i];

    return inv_count;
}

int main()
{
    int arr[] = { 1, 20, 6, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int ans = mergeSort(arr, n);
    cout << " Number of inversions are " << ans;
    return 0;
}


text:
```cpp
class Solution {
public:
    int jump(vector<int>& nums) {
        int cur = 0, prev = 0, count = 0;
        for(int i = 0; i < nums.size()-1; ++i)
        {

            cur = max(cur, i+nums[i]);

            if(cur >= nums.size()-1)
                return count+1;

            if(i == prev)
            {
                prev = cur;
                ++count;
            }
        }
        return count;
    }
};
```


text:
#include<bits/stdc++.h>
using namespace std;
struct edge{
    int u, v, w;
    edge(int a, int b, int c){
        u=a;v=b;w=c;
    }
};
bool sortbywt(struct edge a, struct edge b){
    return a.w < b.w;
}
int find(int u, vector<int> &parent){
    if(parent[u]==u)return u;
    return parent[u]=find(parent[u], parent);
}
void Union(int u, int v, vector<int> &rank, vector<int> &parent){
    int a = find(u, parent);
    int b = find(v, parent);

    if(rank[a]<rank[b]){
        parent[a]=b;
    }
    else if(rank[b]<rank[a]){
        parent[b]=a;
    }
    else {
        parent[b]=a;
        rank[a]++;
    }
}

int main(){
    int E,V;
    cin >> E >> V;

    vector<edge> edges;
    for(int i=0;i<E;i++){
        int u,v,w;
        cin >> u >> v >> w;
        edges.push_back(edge(u,v,w));
    }
    vector<int> parent(V);
    vector<int> rank(V);
    for(int i=0;i<V;i++){
        parent[i]=i;
        rank[i]=0;
    }
    sort(edges.begin(), edges.end(), sortbywt);
    vector<edge> mst;
    int cost=0;
    for(edge x: edges){
        if(find(x.u, parent)!=find(x.v, parent)){
            mst.push_back(x);
            cost+=x.w;
            Union(x.u, x.v, rank, parent);
        }
    }
    cout <<"Minimum Spanning Tree:"<<endl;
    cout <<"Minimum cost: "<<cost<<endl;
    cout <<"V1 V2 WT:"<<endl;

    for(int i=0;i<mst.size();i++){
        cout <<mst[i].u<<" "<<mst[i].v<<" "<<mst[i].w<<endl;
    }
    return 0;
}


text:
// Floyd-Warshall Algorithm in C++

#include <iostream>
using namespace std;

// defining the number of vertices
#define nV 4

#define INF 999

void printMatrix(int matrix[][nV]);

// Implementing floyd warshall algorithm
void floydWarshall(int graph[][nV]) {
  int matrix[nV][nV], i, j, k;

  for (i = 0; i < nV; i++)
    for (j = 0; j < nV; j++)
      matrix[i][j] = graph[i][j];

  // Adding vertices individually
  for (k = 0; k < nV; k++) {
    for (i = 0; i < nV; i++) {
      for (j = 0; j < nV; j++) {
        if (matrix[i][k] + matrix[k][j] < matrix[i][j])
          matrix[i][j] = matrix[i][k] + matrix[k][j];
      }
    }
  }
  printMatrix(matrix);
}

void printMatrix(int matrix[][nV]) {
  for (int i = 0; i < nV; i++) {
    for (int j = 0; j < nV; j++) {
      if (matrix[i][j] == INF)
        printf("%4s", "INF");
      else
        printf("%4d", matrix[i][j]);
    }
    printf("\n");
  }
}

int main() {
  int graph[nV][nV] = {{0, 3, INF, 5},
             {2, 0, INF, 4},
             {INF, 1, 0, INF},
             {INF, INF, 2, 0}};
  floydWarshall(graph);
}


text:
// Bipartite Graph
// ---------------
// You can divide all the vertices of graph in 2 sets
// such that all edges of the graph are from set1 to set2

// Two Coloring

/// How  to flip colors between 1 and 2 ?
// Use 3-color
//   3-2 = 1    and   3-1 = 2

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

bool dfs_helper(vector<int> graph[], int node, int visited[], int parent, int color){
	// come to node and assign the color
	visited[node] = color;    // 1 or 2 -- both means visited
	for(auto nbr: graph[node]){
		// Many possibilities
		if(visited[nbr] == 0){
			int subprob = dfs_helper(graph, nbr, visited, node, 3-color);
			if(subprob == false){
				return false;
			}
		}
		else if(nbr != parent and color == visited[nbr]){
			return false;
		}
	}
	return true;
}

// Yes or No, whether graph is Bipartite or Not
bool dfs(vector<int> graph[], int N){
	// Visited array states :
	// 0 -> Not visited
	// 1 -> Color 1
	// 2 -> Color 2
	int visited[N];
	for(int i=0; i<=N; i++){
		visited[i] = 0;
	}

	int color = 1;
	int ans = dfs_helper(graph,0,visited,-1, color);

	for(int i=0; i<N; i++){
		cout << i << "->" << visited[i] << "\n";
	}

	return ans;
}

int main(){

	int N, M;
	cin >> N >> M;

	vector<int> graph[N];

	while(M--){
		int x, y;
		cin >> x >> y;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}

	// By DFS, coloring the nodes at each step
	// Current node -> color 1
	// Neighbouring nodes -> color 2
	if(dfs(graph, N)){
		cout << "Yes, its bipartite..\n";
	}
	else{
		cout << "No, its not bipartite..\n";
	}
}


text:
//Shortest path in undirected graph using BFS.

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

vector<ll> adj[10005];
ll dis[10005],vis[10005];

void bfs(ll src){

    queue<ll> q;
    vis[src]=1;
    dis[src]=0;
    q.push(src);

    while(!q.empty()){

        int node = q.front();
        q.pop();

        for(auto it : adj[node]){       //traversing in the adjacency list.
            if(vis[it]==0){
                dis[it]=dis[node]+1;
                q.push(it);
                vis[it]=1;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    ll t;
    cin>>t;

    while(t--){

    ll n,m;   //no. of nodes & vertices.
    cin>>n>>m;

    for(ll i=0;i<=n;i++) adj[i].clear() , vis[i]=0;

    while(m--){
      ll a,b;
        cin>>a>>b;  adj[a].push_back(b);  adj[b].push_back(a);
    }

    bfs(1);       //calling the above BFS function.

    for(ll i = 1; i <= n; i++)    //printing path from source to ith node.
    cout<<dis[i]<<" ";

    cout<<endl;
    }
}


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

void addEdge(vector<int>adj[] , int u , int v){
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void bfs( vector<int>adj[] , int V , int s){
    vector<bool>visited(V , 0);
    queue<int>q;
    visited[s]=1;
    q.push(s);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        cout<<x<<" ";
        for(auto u : adj[x]){
            if(visited[u]==0){
                q.push(u);
                visited[u]=1;
            }
        }
    }
    cout<<endl;

}

//bfs for graph having various connected components
void bfs3(vector<int>adj[] , int s , vector<bool>&visited){
    queue<int>q;
    q.push(s);
    visited[s]=1;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        cout<<x<<" ";
        for(auto u : adj[x]){
            if(visited[u]==0){
                q.push(u);
                visited[u]=1;
            }
        }
    }

}

void bfs2(vector<int>adj[] , int V){
    int i  = 0;
    vector<bool>visited(V , 0);
    for(i = 0 ; i<V ; i++){
        if(visited[i]==0){
            bfs3(adj , i , visited);
        }
    }

}

int main(){
    int V = 4;
    vector<int>adj[V];
    addEdge(adj , 0 , 1);
    addEdge(adj , 0 , 2);
    addEdge(adj , 1 , 2);
    addEdge(adj , 1 , 3);
    bfs(adj , V , 0);
    bfs2(adj , V);

    return 0;
}


text:
import java.util.*;
class Graph<T>
{
//creating an object of the Map class that stores the edges of the graph
private Map<T, List<T> > map = new HashMap<>();
//the method adds a new vertex to the graph
public void addNewVertex(T s)
{
map.put(s, new LinkedList<T>());
}
//the method adds an edge between source and destination
public void addNewEdge(T source, T destination, boolean bidirectional)
{
//
if (!map.containsKey(source))
addNewVertex(source);
if (!map.containsKey(destination))
addNewVertex(destination);
map.get(source).add(destination);
if (bidirectional == true)
{
map.get(destination).add(source);
}
}
//the method counts the number of vertices
public void countVertices()
{
System.out.println("Total number of vertices: "+ map.keySet().size());
}
//the method counts the number of edges
public void countEdges(boolean bidirection)
{
//variable to store number of edges
int count = 0;
for (T v : map.keySet())
{
count = count + map.get(v).size();
}
if (bidirection == true)
{
count = count / 2;
}
System.out.println("Total number of edges: "+ count);
}
//checks a graph has vertex or not
public void containsVertex(T s)
{
if (map.containsKey(s))
{
System.out.println("The graph contains "+ s + " as a vertex.");
}
else
{
System.out.println("The graph does not contain "+ s + " as a vertex.");
}
}
//checks a graph has edge or not
//where s and d are the two parameters that represent source(vertex) and destination (vertex)
public void containsEdge(T s, T d)
{
if (map.get(s).contains(d))
{
System.out.println("The graph has an edge between "+ s + " and " + d + ".");
}
else
{
System.out.println("There is no edge between "+ s + " and " + d + ".");
}
}
//prints the adjacencyS list of each vertex
//here we have overridden the toString() method of the StringBuilder class
@Override
public String toString()
{
StringBuilder builder = new StringBuilder();
//foreach loop that iterates over the keys
for (T v : map.keySet())
{
builder.append(v.toString() + ": ");
//foreach loop for getting the vertices
for (T w : map.get(v))
{
builder.append(w.toString() + " ");
}
builder.append("\n");
}
return (builder.toString());
}
}
//creating a class in which we have implemented the driver code
public class GraphImplementation
{
public static void main(String args[])
{
//creating an object of the Graph class
Graph graph=new Graph();
//adding edges to the graph
graph.addNewEdge(0, 1, true);
graph.addNewEdge(0, 4, true);
graph.addNewEdge(1, 2, true);
graph.addNewEdge(1, 3, false);
graph.addNewEdge(1, 4, true);
graph.addNewEdge(2, 3, true);
graph.addNewEdge(2, 4, true);
graph.addNewEdge(3, 0, true);
graph.addNewEdge(2, 0, true);
//prints the adjacency matrix that represents the graph
System.out.println("Adjacency List for the graph:\n"+ graph.toString());
//counts the number of vertices in the graph
graph.countVertices();
//counts the number of edges in the graph
graph.countEdges(true);
//checks whether an edge is present or not between the two specified vertices
graph.containsEdge(3, 4);
graph.containsEdge(2, 4);
//checks whether vertex is present or not
graph.containsVertex(3);
graph.containsVertex(5);
}
}


text:
// C# Code For Check if a graphs has a cycle
// of odd length
using System;
using System.Collections.Generic;

class GFG
{

	public static int V = 4;

	// This function returns true if graph G[V,V]
	// contains odd cycle, else false
	public static bool containsOdd(int [,]G, int src)
	{
		// Create a color array to store colors assigned
		// to all vertices. Vertex number is used as
		// index in this array. The value '-1' of
		// colorArr[i] is used to indicate that no color
		// is assigned to vertex 'i'. The value 1 is
		// used to indicate first color is assigned and
		// value 0 indicates second color is assigned.
		int []colorArr = new int[V];
		for (int i = 0; i < V; ++i)
			colorArr[i] = -1;

		// Assign first color to source
		colorArr[src] = 1;

		// Create a queue (FIFO) of vertex numbers and
		// enqueue source vertex for BFS traversal
		Queue<int> q = new Queue<int>();
		q.Enqueue(src);

		// Run while there are vertices in queue
		// (Similar to BFS)
		while (q.Count != 0)
		{
			// Dequeue a vertex from queue
			int u = q.Peek();
			q.Dequeue();

			// Return true if there is a self-loop
			if (G[u, u] == 1)
			return true;

			// Find all non-colored adjacent vertices
			for (int v = 0; v < V; ++v)
			{
				// An edge from u to v exists and
				// destination v is not colored
				if (G[u, v] == 1 && colorArr[v] == -1)
				{
					// Assign alternate color to this
					// adjacent v of u
					colorArr[v] = 1 - colorArr[u];
					q.Enqueue(v);
				}

				// An edge from u to v exists and
				// destination v is colored with same
				// color as u
				else if (G[u,v] == 1 && colorArr[v] ==
										colorArr[u])
					return true;
			}
		}

		// If we reach here, then all adjacent
		// vertices can be colored with alternate
		// color
		return false;
	}

	/* Driver code */
	public static void Main()
	{

		int [,]G = {{0, 1, 0, 1},
					{1, 0, 1, 0},
					{0, 1, 0, 1},
					{1, 0, 1, 0}};

		if (containsOdd(G, 0))
			Console.WriteLine("Yes") ;
			else
				Console.WriteLine("No");
	}
}


text:
//https://www.codechef.com/submit/B01T
#include <bits/stdc++.h>
using namespace std;

#define mod (ll)(998244353)
#define pii pair<ll,ll>
#define vi vector<ll>
// #define v vector
#define vc vector<char>
#define vvi vector<vector<int>>
#define vpii vector< pii >
#define vvpii vector<vector< pair<ll,ll> >>
#define f first
#define s second
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define mp(x, y) make_pair(x, y)
#define all(x) x.begin(), x.end()
#define print(vec, l, r)                                                       \
    for (int i = l; i <= r; i++)                                               \
        cout << vec[i] << " ";                                                 \
    cout << endl;
#define forf(i, a, b) for (ll i = (a); i < (b); i++)
#define forr(i, a, b) for (ll i = (a); i > (b); i -= 1)
#define input(vec, N) for (int i = 0; i < (N); i++) cin >> vec[i];
typedef long long ll;
#define ld long double
const int N = (2e5+20);
const int M = (1e6+20);
const int MAXN = 2e6+12;
const ll INF = 2e18+90;
#define BLOCK 555

typedef unsigned long long ull;
typedef long double lld;

// #include <ext/pb_ds/assoc_container.hpp> //required
// #include <ext/pb_ds/tree_policy.hpp> //required
// using namespace __gnu_pbds; //required
// template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// s.find_by_order(k); returns the (k+1)th smallest element
// s.order_of_key(k); returns the number of elements in s strictly less than k

long long binpow(long long a, long long b, long long m = mod) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

#define no cout<<"NO"<<endl;return;
#define yes cout<<"YES"<<endl;return;

// file open close
void solve(int tte){

    int n;
    cin>>n;

    int a[n+2];
    forf(i,1,n+1) cin>>a[i];

    vvi adj(n+2);

    queue < int > q;
    vi deg(n+2,0);

    forf(i,1,n){
      int u,v;
      cin>>u>>v;

      adj[u].pb(v);
      adj[v].pb(u);
      deg[u]++;
      deg[v]++;
    }

    int rem = 0;

    forf(i,1,n+1){
      if(a[i]) rem++;
      else rem--;

      if(adj[i].size() == 1 && i>1){
        q.push(i);
      }
    }

    vi mark(n+2,0);
    set < int > s;

    while(q.size()){

      if(!rem) break;

      int v = q.front();
      //cout<<v<<endl;
      q.pop();
      s.insert(v);

      if(a[v]){
        rem-=2;
      }else{
        rem+=2;
      }

      for(auto x : adj[v]){
        s.erase(x);
        deg[x]--;
        if(x>1 && deg[x]==1){
          q.push(x);
        }
      }

    }

    cout<<s.size()<<endl;

    for(auto x : s){
      cout<<x<<" ";
    }
    cout<<endl;

}
// file open close

signed main() {
  #ifndef ONLINE_JUDGE
    freopen("Error.txt", "w", stderr);
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
  #endif

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int T = 1;

  cin >> T;
  int t=1;
  // bfs();
  // calc();
  // sieve(N-5);
  // calc();
  while (t<=T) {
      //cout<<"Case #"<<t<<": ";
      solve(t);
      t++;
  }
}


text:
// Given a Directed Acyclic Graph (DAG) with V vertices and E edges, Find any Topological Sorting of that Graph.
#include <bits/stdc++.h>
using namespace std;

 // } Driver Code Ends
class Solution
{
	public:
	//Function to return list containing vertices in Topological order.
	vector<int> topoSort(int V, vector<int> adj[])
	{
	    vector<int> indegree(V,0);
	    for(int i=0; i<V; i++){
	        for(int j=0; j<adj[i].size(); j++){
	            int node=adj[i][j];
	            indegree[node]++;
	        }
	    }

	    queue<int> qu;
	    for(int i=0; i<V; i++){
	        if(indegree[i]==0)
	            qu.push(i);
	    }
	    vector<int> topo;
	    while(!qu.empty()){
	        int node=qu.front();
	        qu.pop();
	        topo.push_back(node);
	        for(int j=0; j<adj[node].size(); j++){
	            int nbr=adj[node][j];
	            if(--indegree[nbr]==0)
	                qu.push(nbr);
	        }
	    }
	    return topo;
	}
};

// { Driver Code Starts.

/*  Function to check if elements returned by user
*   contains the elements in topological sorted form
*   V: number of vertices
*   *res: array containing elements in topological sorted form
*   adj[]: graph input
*/
int check(int V, vector <int> &res, vector<int> adj[]) {

    if(V!=res.size())
    return 0;

    vector<int> map(V, -1);
    for (int i = 0; i < V; i++) {
        map[res[i]] = i;
    }
    for (int i = 0; i < V; i++) {
        for (int v : adj[i]) {
            if (map[i] > map[v]) return 0;
        }
    }
    return 1;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N, E;
        cin >> E >> N;
        int u, v;

        vector<int> adj[N];

        for (int i = 0; i < E; i++) {
            cin >> u >> v;
            adj[u].push_back(v);
        }

        Solution obj;
        vector <int> res = obj.topoSort(N, adj);

        cout << check(N, res, adj) << endl;
    }

    return 0;
}  // } Driver Code Ends


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

vector<int> dijkstra(vector<vector<int> >& adj,map<pair<int,int>,int>& C,int& source,int& n,int& m){
         const int inf = INT_MAX;
         //using min heap to obtain next lesser edge
         priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;

         //Initializing distance to infinity
         vector<int>dist(n+1,inf);
         q.push({0,source});
         vector<bool>visited(n+1,false);
         dist[source]=0;

         while(!q.empty()){
            auto z=q.top();
            q.pop();
            int y=z.first;
            int x=z.second;
            if(visited[x])continue;
            visited[x]=true;
            for(int i : adj[x]){
              if(!visited[i]){
              if(dist[i]>y+C[{x,i}]){
                dist[i]=y+C[{x,i}];
                q.push({dist[i],i});
              }
            }
            }
         }
         return dist;
}

int main(){
         int n,m;
         cin>>n>>m;
         //Adjacency List to store the graph
         vector<vector<int> >adj(n+1);

         //Map to store the edge lengths
         map<pair<int,int>,int>C;
         for(int i=0;i<m;i++){
          int x,y,cost;
          cin>>x>>y>>cost;
          if(x==y)continue;
          if(C.find({x,y})==C.end()){
            adj[x].push_back(y);
            C[{x,y}]=cost;
          }
          else{
            C[{x,y}]=min(C[{x,y}],cost);
          }
         }

         int source;
         cin>>source;

         vector<int>dist = dijkstra(adj,C,source,n,m);

         //Printing distance of all points from source
         for(int i=1;i<=n;i++)cout<<dist[i]<<" ";
          cout<<endl;
}


text:
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;

// Function to check valid coordinate
int validCoord(int x, int y, int n, int m)
{

	if (x < 0 || y < 0) {
		return 0;
	}
	if (x >= n || y >= m) {
		return 0;
	}
	return 1;
}

// Function to run bfs
void bfs(int n, int m, int data[][8],
					int x, int y, int color)
{

// Visiting array
int vis[101][101];

// Initializing all as zero
memset(vis, 0, sizeof(vis));

// Creating queue for bfs
queue<pair<int, int> > obj;

// Pushing pair of {x, y}
obj.push({ x, y });

// Marking {x, y} as visited
vis[x][y] = 1;

// Until queue is empty
while (obj.empty() != 1)
{

	// Extracting front pair
	pair<int, int> coord = obj.front();
	int x = coord.first;
	int y = coord.second;
	int preColor = data[x][y];

	data[x][y] = color;

	// Popping front pair of queue
	obj.pop();

	// For Upside Pixel or Cell
	if (validCoord(x + 1, y, n, m)
		&& vis[x + 1][y] == 0
		&& data[x + 1][y] == preColor)
	{
	obj.push({ x + 1, y });
	vis[x + 1][y] = 1;
	}

	// For Downside Pixel or Cell
	if (validCoord(x - 1, y, n, m)
		&& vis[x - 1][y] == 0
		&& data[x - 1][y] == preColor)
	{
	obj.push({ x - 1, y });
	vis[x - 1][y] = 1;
	}

	// For Right side Pixel or Cell
	if (validCoord(x, y + 1, n, m)
		&& vis[x][y + 1] == 0
		&& data[x][y + 1] == preColor)
	{
	obj.push({ x, y + 1 });
	vis[x][y + 1] = 1;
	}

	// For Left side Pixel or Cell
	if (validCoord(x, y - 1, n, m)
		&& vis[x][y - 1] == 0
		&& data[x][y - 1] == preColor)
	{
	obj.push({ x, y - 1 });
	vis[x][y - 1] = 1;
	}
}

// Printing The Changed Matrix Of Pixels
for (int i = 0; i < n; i++)
{
	for (int j = 0; j < m; j++)
	{
	cout << data[i][j] << " ";
	}
	cout << endl;
}
cout << endl;
}

// Driver Code
int main()
{
int n, m, x, y, color;
n = 8;
m = 8;

int data[8][8] = {
	{ 1, 1, 1, 1, 1, 1, 1, 1 },
	{ 1, 1, 1, 1, 1, 1, 0, 0 },
	{ 1, 0, 0, 1, 1, 0, 1, 1 },
	{ 1, 2, 2, 2, 2, 0, 1, 0 },
	{ 1, 1, 1, 2, 2, 0, 1, 0 },
	{ 1, 1, 1, 2, 2, 2, 2, 0 },
	{ 1, 1, 1, 1, 1, 2, 1, 1 },
	{ 1, 1, 1, 1, 1, 2, 2, 1 },
};

x = 4, y = 4, color = 3;

// Function Call
bfs(n, m, data, x, y, color);
return 0;
}