text:
/*
N meetings in one room

Easy Accuracy: 43.1% Submissions: 45123 Points: 2
There is one meeting room in a firm. There are N meetings in the form of (start[i], end[i]) where start[i] is start time of meeting i and end[i] is
finish time of meeting i.
What is the maximum number of meetings that can be accommodated in the meeting room when only one meeting can be held in the meeting room at a
 particular time?

Note: Start time of one chosen meeting can't be equal to the end time of the other chosen meeting.

Example 1:

Input:
N = 6
start[] = {1,3,0,5,8,5}
end[] =  {2,4,6,7,9,9}
Output:
4
Explanation:
Maximum four meetings can be held with
given start and end timings.
The meetings are - (1, 2),(3, 4), (5,7) and (8,9)
Example 2:

Input:
N = 3
start[] = {10, 12, 20}
end[] = {20, 25, 30}
Output:
1
Explanation:
Only one meetings can be held
with given start and end timings.

Your Task :
You don't need to read inputs or print anything. Complete the function maxMeetings() that takes two arrays start[] and end[] along with their size N
as input parameters and returns the maximum number of meetings that can be held in the meeting room.

Expected Time Complexity : O(N*LogN)
Expected Auxilliary Space : O(N)

Constraints:
1 = N = 105
0 = start[i] < end[i] = 105
*/

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

 // } Driver Code Ends

class Solution
{
    public:
    //Function to find the maximum number of meetings that can
    //be performed in a meeting room.
    bool static comp(const pair<int,int>&a,const pair<int,int>&b){
        return a.second<b.second;
    }
    int maxMeetings(int start[], int end[], int n)
    {
        // Your code here
        vector<pair<int,int>>v;int c=1,j=0;
        for(int i=0;i<n;i++)
         v.push_back(make_pair(start[i],end[i]));
        sort(v.begin(),v.end(),comp);

        for(int i=1;i<n;i++){
            if(v[i].first>v[j].second)
             {c++;j=i;}
        }
        return c;
    }
};

// { Driver Code Starts.
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int start[n], end[n];
        for (int i = 0; i < n; i++) cin >> start[i];

        for (int i = 0; i < n; i++) cin >> end[i];

        Solution ob;
        int ans = ob.maxMeetings(start, end, n);
        cout << ans << endl;
    }
    return 0;
}  // } Driver Code Ends


text:
/*
Job Sequencing Problem

Medium Accuracy: 48.94% Submissions: 41033 Points: 4
Given a set of N jobs where each jobi has a deadline and profit associated with it. Each job takes 1 unit of time to complete and only one job can be scheduled at a time. We earn the profit if and only if the job is completed by its deadline. The task is to find the number of jobs done and the maximum profit.

Note: Jobs will be given in the form (Jobid, Deadline, Profit) associated with that Job.

Example 1:

Input:
N = 4
Jobs = {(1,4,20),(2,1,10),(3,1,40),(4,1,30)}
Output:
2 60
Explanation:
Job1 and Job3 can be done with
maximum profit of 60 (20+40).
Example 2:

Input:
N = 5
Jobs = {(1,2,100),(2,1,19),(3,2,27),
        (4,1,25),(5,1,15)}
Output:
2 127
Explanation:
2 jobs can be done with
maximum profit of 127 (100+27).

Your Task :
You don't need to read input or print anything. Your task is to complete the function JobScheduling() which takes an integer N and an array of Jobs(Job id, Deadline, Profit) as input and returns the count of jobs and maximum profit.

Expected Time Complexity: O(NlogN)
Expected Auxilliary Space: O(N)

Constraints:
1 <= N <= 105
1 <= Deadline <= 100
1 <= Profit <= 500
*/

#include<bits/stdc++.h>
using namespace std;
struct job
{
    int id;
    int dead;
    int prof;
    job(int id,int dead,int prof)
    {
        this->id=id;
        this->dead=dead;
        this->prof=prof;
    }
};
bool comparator(job &j1,job &j2)
{
    return j1.dead<j2.dead;
}

int main()
{
    int tes,n,temp1,temp2,temp3,sum;
    cin>>tes;
    for(int t=0;t<tes;t++)
    {
        cin>>n;
        vector<job>v;
        for(int i=0;i<n;i++)
        {
            cin>>temp1>>temp2>>temp3;
            job j(temp1,temp2,temp3);
            v.push_back(j);
        }
        sort(v.begin(),v.end(),comparator);
        priority_queue<int,vector<int>,greater<int>> pq;
        pq.push(v[0].prof);
        int pqsize=1;
        for(int j=1;j<n;j++)
        {
            if(pqsize<v[j].dead)
            {
                pq.push(v[j].prof);
                pqsize++;
            }
            else if(v[j].prof>pq.top())
            {
                pq.pop();
                pq.push(v[j].prof);
            }
        }
        cout<<pqsize<<" ";
        sum=0;
        while(pqsize!=0)
        {
            sum=sum+pq.top();
            pq.pop();
            pqsize--;
        }
        cout<<sum<<endl;

    }
    return 0;
}

file_name: Merge Sorted Array.cpp

mime_type: text/x-c++


text:
# Python implementation of stable matching problem

def gale_shapley(hospital, student, pref_hospital, pref_student):
    # inverse student prereference list
    # for each student keep the rank for each man, rank_hospital is a dictionary of dicionary,
    # when w needs to choose, we can compare the rank of each man with constant time
    # the bigger the number, the higher the rank
    rank_hospital = {}
    for s in student:
        rank_hospital[s] = {}
        i = len(student)
        for h in pref_student[s]:
            # the higher the number (which is i) is,the higher the ranking
            rank_hospital[s][h] = i
            i -= 1
    # count how many proposals each hospital has made, to track next student he can propose
    count = {}
    for h in hospital:
        count[h] = hospital[h]

    # initially all hospital and student are free
    freehospital = list()
    for h in hospital:
        while count[h] > 0:
            freehospital.append(h)
            count[h] -= 1
    numpartners = len(student)
    S = {}           # engaged pairs stored in dictionary with student name as key, hospital name as value

    # run the algorithm
    while freehospital:
        h = freehospital.pop()
        if count[h] > numpartners:
            continue
        # get the first student that h has not yet been proposed to
        s = pref_hospital[h][count[h]]
        count[h] += 1

        if s not in S:  # student s is free
            S[s] = h
        else:
            # s prefers h to the current partner h', accepts h, dumps h'
            hprime = S[s]
            if rank_hospital[s][h] > rank_hospital[s][hprime]:
                S[s] = h
                freehospital.append(hprime)
            # s prefers the current partner, reject h
            else:
                freehospital.append(h)
    return S

if __name__ == "__main__":

    # change to a data structure (e.g a dictionay) to keep track the number of positions for each hospital
    hospital = {'Atlanta':1, 'Boston':2, 'Chicago':2, 'Detroit':1}

    student = ['Val', 'Wayne', 'Xavier', 'Yolanda', 'Zeus', 'Alfred']

    pref_hospital = {'Atlanta': ['Wayne', 'Val', 'Alfred', 'Yolanda', 'Zeus', 'Xavier'],
                     'Boston': ['Yolanda', 'Wayne', 'Alfred', 'Val', 'Xavier', 'Zeus'],
                     'Chicago': ['Alfred', 'Wayne', 'Zeus', 'Xavier', 'Yolanda', 'Val'],
                     'Detroit': ['Val', 'Yolanda', 'Xavier', 'Wayne', 'Zeus', 'Alfred']
                     }
    pref_student = {
        'Val': ['Atlanta', 'Boston', 'Detroit', 'Chicago'],
        'Wayne': ['Chicago', 'Boston', 'Detroit', 'Atlanta', 'El Paso'],
        'Xavier': ['Boston',  'Chicago', 'Detroit', 'Atlanta'],
        'Yolanda': ['Atlanta', 'Detroit', 'Chicago', 'Boston'],
        'Zeus': ['Detroit', 'Boston', 'Chicago', 'Atlanta'],
        'Alfred': ['Boston', 'Detroit', 'Atlanta', 'Chicago']
    }

    stable_matching = gale_shapley(
        hospital, student, pref_hospital, pref_student)
    print(stable_matching)


text:
/*
Fractional Knapsack

Medium Accuracy: 45.14% Submissions: 41340 Points: 4
Given weights and values of N items, we need to put these items in a knapsack of capacity W to get the maximum total value in the knapsack.
Note: Unlike 0/1 knapsack, you are allowed to break the item.

Example 1:

Input:
N = 3, W = 50
values[] = {60,100,120}
weight[] = {10,20,30}
Output:
240.00
Explanation:Total maximum value of item
we can have is 240.00 from the given
capacity of sack.
Example 2:

Input:
N = 2, W = 50
values[] = {60,100}
weight[] = {10,20}
Output:
160.00
Explanation:
Total maximum value of item
we can have is 160.00 from the given
capacity of sack.

Your Task :
Complete the function fractionalKnapsack() that receives maximum capacity , array of structure/class and size n and returns a double value
representing the maximum value in knapsack.
Note: The details of structure/class is defined in the comments above the given function.

Expected Time Complexity : O(NlogN)
Expected Auxilliary Space: O(1)

Constraints:
1 <= N <= 105
1 <= W <= 105
*/

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

int main()
{
int t;
cin>>t;
while(t--)
{
int n,cap,ele,val;
float value=0;
cin>>n>>cap;
vector<pair<float,pair<int,int>>>v;
for(int i=0;i<n;i++) {cin>>val>>ele;
float ing = float(val)/ele;
v.push_back(make_pair(ing,(make_pair(val,ele))));
}
sort(v.begin(),v.end());
for(auto i=v.end()-1;i>=v.begin();i--)
{
if((*i).second.second<=cap)
{
value = value + (((*i).first) * ((*i).second.second));
cap = cap - (*i).second.second;
}
else
{
if((*i).second.second>cap)
(*i).second.second=cap;
value = value + (((*i).first) * ((*i).second.second));
cap = cap - (*i).second.second;
}
}
cout << fixed << setprecision(2) <<value<<"\n"; }
return 0;}


text:
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

bool cmp(pii p1, pii p2) {
    return p1.ss < p2.ss;
}
void c_p_c()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    w(x) {
        int n;
        cin >> n;
        vector<pair<int, int> > v(n);
        //v.clear();
        for (int i = 0; i < n; i++) {
            int x, y;
            cin >> x >> y;
            v[i] = {x, y};
        }

        sort(v.begin(), v.end(), cmp);
        /*  for(int i=0;i<n;i++){
                cout<<v[i].ff<<","<<v[i].ss<<endl;

            }*/
        int ans = 0;
        int last = INT_MIN;
        for (int i = 0; i < n; i++) {
            if (v[i].ff >= last) {
                ans++;
                last = v[i].ss;
            }
        }
        cout << ans << "\n";
    }

}

int32_t main()
{
    clock_t begin = clock();
    c_p_c();
#ifndef ONLINE_JUDGE
    clock_t end = clock();
    cout << "\nExecuted In: " << double(end - begin) / CLOCKS_PER_SEC * 1000 << " ms";
#endif
    return 0;
}


text:
#include <bits/stdc++.h>

using namespace std;

// Structure for an item which stores weight and
// corresponding value of Item
struct Item {
    int value, weight;

    // Constructor
    Item(int value, int weight)
    {
       this->value=value;
       this->weight=weight;
    }
};

// Comparison function to sort Item according to val/weight
// ratio
bool cmp(struct Item a, struct Item b)
{
    double r1 = (double)a.value / (double)a.weight;
    double r2 = (double)b.value / (double)b.weight;
    return r1 > r2;
}

// Main greedy function to solve problem
double fractionalKnapsack(int W, struct Item arr[], int n)
{
    //    sorting Item on basis of ratio
    sort(arr, arr + n, cmp);

    //    Uncomment to see new order of Items with their
    //    ratio
    /*
    for (int i = 0; i < n; i++)
    {
        cout << arr[i].value << "  " << arr[i].weight << " :
    "
             << ((double)arr[i].value / arr[i].weight) <<
    endl;
    }
    */

    int curWeight = 0; // Current weight in knapsack
    double finalvalue = 0.0; // Result (value in Knapsack)

    // Looping through all Items
    for (int i = 0; i < n; i++) {
        // If adding Item won't overflow, add it completely
        if (curWeight + arr[i].weight <= W) {
            curWeight += arr[i].weight;
            finalvalue += arr[i].value;
        }

        // If we can't add current Item, add fractional part
        // of it
        else {
            int remain = W - curWeight;
            finalvalue += arr[i].value
                          * ((double)remain
                             / (double)arr[i].weight);
            break;
        }
    }

    // Returning final value
    return finalvalue;
}

// Driver code
int main()
{
    int W = 50; //    Weight of knapsack
    Item arr[] = { { 60, 10 }, { 100, 20 }, { 120, 30 } };

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

    // Function call
    cout << "Maximum value we can obtain = "
         << fractionalKnapsack(W, arr, n);
    return 0;
}


text:
#include <iostream>
#include<vector>
using namespace std;
#define MAX 9999
int print(int graph[50][50], int z) {
	for (int i = 0; i <= z; i++) {
		for (int j = 0; j <= z; j++) {
			cout << graph[i][j] << " ";
		}
		cout << "\n";
	}
	return 0;
}
int minVertex(vector<int>& dist, vector<bool>& mst, int n) {
	int mini = MAX;
	int v;
	for (int i = 0; i < n; i++) {
		if (mst[i] == false && dist[i] < mini) {
			v = i;
			mini = dist[i];
		}
	}
	return v;
}
int Dijktras(int graph[50][50], int n,int src) {
	vector<int>dist(n + 1, MAX);
	vector<bool>setmst(n + 1, false);
	vector<int>parent(n + 1);
	parent[src] = -1;
	dist[src] = 0;
	for (int i = 0; i <= n - 1; i++) {
		int m = minVertex(dist, setmst, n);
		setmst[m] = true;
		for (int j = 0; j <= n; j++) {
			if (setmst[j] == false && graph[m][j] != 0 && (dist[m]+graph[m][j]) < dist[j] && dist[m]!=MAX) {
				dist[j] = graph[m][j]+dist[m];
				parent[j] = m;
			}

		}
	}
	cout << "\nShortest pair from node: "<<src<<"\n\n";
	for (int i = 0; i <= n; i++) {
		if(parent[i]!=-1)
		cout << parent[i] << " -> " << i << " = " << graph[parent[i]][i] << "\n";
	}
	return 0;
}
int main()
{
	int graph[50][50], n, x, y, z = 0, u = 0, w, v = 0,src;
	memset(graph, 0, sizeof(graph));
	cout << "Enter number of paths: ";
	cin >> n;
	for (int i = 0; i < n; i++) {
		cout << "Path , destination and weigth: ";
		cin >> x >> y >> w;
		graph[x][y] = w;
		graph[y][x] = w;
		z = max(z, x);
		u = max(u, y);
		v++;
	}
	cout << "Enter Source node: ";
	cin >> src;
	z = max(z, u);
	cout << "Adjacency matrix:\n\n";
	print(graph, z);
	Dijktras(graph, z,src);
	return 0;
}


text:
#include <iostream>
#define N 9
using namespace std;

int grid[N][N] = {
    {3,0,0,8,7,5,0,9,0},
    {0,1,0,2,5,0,0,0,8},
    {9,8,0,1,0,0,3,5,7},
    {1,0,5,0,0,0,0,0,0},
    {4,0,0,0,0,0,0,0,2},
    {0,0,0,0,0,0,5,0,3},
    {5,7,8,3,0,1,0,2,6},
    {0,0,0,0,4,8,9,0,0},
    {0,9,0,6,2,0,0,8,1}
};
bool isPresentInCol(int col, int num) {    //check whether num is present in col or not

   for (int row = 0; row < N; row++)
      if (grid[row][col] == num)
         return true;

   return false;
}
bool isPresentInRow(int row, int num) {    //check whether num is present in row or not

   for (int col = 0; col < N; col++)
      if (grid[row][col] == num)
         return true;
   return false;
}
bool isPresentInBox(int boxStartRow, int boxStartCol, int num) {    //check whether num is present in 3x3 box or not

   for (int row = 0; row < 3; row++)
      for (int col = 0; col < 3; col++)
         if (grid[row+boxStartRow][col+boxStartCol] == num)
            return true;
   return false;
}
void sudokuGrid() {    //print the sudoku grid after solve
   for (int row = 0; row < N; row++) {
      cout<<"[ ";
      for (int col = 0; col < N; col++) {

         cout << grid[row][col] <<" ";
      }
      cout<<"]"<<endl;

      }
      cout << endl;

}
bool findEmptyPlace(int &row, int &col) {    //get empty location and update row and column
   for (row = 0; row < N; row++)
      for (col = 0; col < N; col++)
         if (grid[row][col] == 0) //marked with 0 is empty
            return true;
   return false;
}
bool isValidPlace(int row, int col, int num) {
   //when item not found in col, row and current 3x3 box
   return !isPresentInRow(row, num) && !isPresentInCol(col, num) && !isPresentInBox(row - row%3 , col - col%3, num);
}
bool solveSudoku() {
   int row, col;
   if (!findEmptyPlace(row, col))
      return true;     //when all places are filled
   for (int num = 1; num <= 9; num++) {
//the valid numbers are from 1 - 9
      if (isValidPlace(row, col, num)) {
//check validation, if yes, put the number in the grid
         grid[row][col] = num;
         if (solveSudoku())
//recursively go for other rooms in the grid
            return true;
//core part of the backtracking
         grid[row][col] = 0;
//turn to unassigned space when conditions are not satisfied
      }
   }
   return false;
}
int main() {
   if (solveSudoku() == true)
      sudokuGrid();
   else
      cout << "No solution exists";
}


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

#define V 4

void printSolution(int color[]);

bool isSafe(bool graph[V][V], int color[])
{

	for (int i = 0; i < V; i++)
		for (int j = i + 1; j < V; j++)
			if (graph[i][j] && color[j] == color[i])
				return false;
	return true;
}

bool graphColoring(bool graph[V][V], int m, int i,
				int color[V])
{
	if (i == V) {

		if (isSafe(graph, color)) {

			// Print the solution
			printSolution(color);
			return true;
		}
		return false;
	}

	// Assign each color from 1 to m
	for (int j = 1; j <= m; j++) {
		color[i] = j;

		if (graphColoring(graph, m, i + 1, color))
			return true;

		color[i] = 0;
	}

	return false;
}

void printSolution(int color[])
{
	cout << "Solution Exists:" " Following are the assigned colors \n";
	for (int i = 0; i < V; i++)
		cout << " " << color[i];
	cout << "\n";
}

// Driver code
int main()
{

	bool graph[V][V] = {
		{ 0, 1, 1, 1 },
		{ 1, 0, 1, 0 },
		{ 1, 1, 0, 1 },
		{ 1, 0, 1, 0 },
	};
	int m = 3;

	int color[V];
	for (int i = 0; i < V; i++)
		color[i] = 0;

	if (!graphColoring(graph, m, 0, color))
		cout << "Solution does not exist";

	return 0;
}


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

void placeQueens(int i, int n, vector<vector<string>> &ans, vector<string> &v, vector<bool> &row, vector<bool> &col, vector<bool> &ld, vector<bool> &rd)
{
    if (i == n)
    {
        ans.push_back(v);
        return;
    }
    for (int j = 0; j < n; j++)
    {
        if (row[i] + col[j] + ld[i + j] + rd[j - i + n - 1] == 0)
        {
            v[i][j] = 'Q'; //place Queen
            row[i] = col[j] = ld[i + j] = rd[j - i + n - 1] = true;
            placeQueens(i + 1, n, ans, v, row, col, ld, rd);
            row[i] = col[j] = ld[i + j] = rd[j - i + n - 1] = false;
            v[i][j] = '.';
        }
    }
}

vector<vector<string>> solveNQueens(int n)
{
    string s;
    vector<string> v;
    vector<vector<string>> ans;
    vector<bool> row(n, false), col(n, false), ld(2 * n, false), rd(2 * n, false);
    for (int i = 0; i < n; i++)
    {
        s = s + '.';
    }
    for (int i = 0; i < n; i++)
    {
        v.push_back(s);
    }
    placeQueens(0, n, ans, v, row, col, ld, rd);
    return ans;
}

int main()
{
    int n;
    cin>>n;
    vector<vector<string> > ans;
    ans = solveNQueens(n);
    //Display
    for(int i=0;i<ans.size();i++)
    {
        for(int j=0;j<ans[i].size();i++)
        {
            cout<<ans[i][j]<<endl;
        }
    }
}


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

//Name: Bibaswan Roy
//The 1s represent the path, and 0s are blocks

const int n = 4;

bool isSafe(int (*maze)[n], int r, int c)
{
    if(maze[r][c] == 1 && r < n && c < n)
        return true;
    return false;
}

void solPrint(int sol[n][n])
{
    for(int i =0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            cout << sol[i][j] << "  ";
        cout << endl;
    }
}

bool mazeSolver(int maze[n][n], int sol[n][n], int r, int c)
{
    if(r == n-1 && c == n-1 && maze[r][c] == 1)
    {
        sol[r][c] = 1;
        return true;
    }
    sol[r][c] = 1;
    if(isSafe(maze, r, c))
    {
        if(mazeSolver(maze, sol, r+1, c))
            return true;
        if(mazeSolver(maze, sol, r, c+1))
            return true;
    }
    sol[r][c] = 0;
    return false;
}

int main()
{
    int maze[n][n] = {{1, 1, 0, 0},
                      {0, 1, 1, 1},
                      {0, 1, 0, 1},
                      {1, 1, 0, 1}};
    int sol[n][n] = {{0, 0, 0, 0},
                     {0, 0, 0, 0},
                     {0, 0, 0, 0},
                     {0, 0, 0, 0}};

    if(mazeSolver(maze, sol, 0, 0))
    solPrint(sol);
    else
    {
        cout << "\nThe rat cannot escape";
    }

    return 0;
}


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

enum Color {RED, BLACK};

struct Node
{
	int data;
	bool color;
	Node *left, *right, *parent;

	// Constructor
	Node(int data)
	{
	this->data = data;
	left = right = parent = NULL;
	this->color = RED;
	}
};

// Class to represent Red-Black Tree
class RBTree
{
private:
	Node *root;
protected:
	void rotateLeft(Node *&, Node *&);
	void rotateRight(Node *&, Node *&);
	void fixViolation(Node *&, Node *&);
public:
	// Constructor
	RBTree() { root = NULL; }
	void insert(const int &n);
	void inorder();
	void levelOrder();
};

// A recursive function to do inorder traversal
void inorderHelper(Node *root)
{
	if (root == NULL)
		return;

	inorderHelper(root->left);
	cout << root->data << " ";
	inorderHelper(root->right);
}

/* A utility function to insert
	a new node with given key
in BST */
Node* BSTInsert(Node* root, Node *pt)
{
	/* If the tree is empty, return a new node */
	if (root == NULL)
	return pt;

	/* Otherwise, recur down the tree */
	if (pt->data < root->data)
	{
		root->left = BSTInsert(root->left, pt);
		root->left->parent = root;
	}
	else if (pt->data > root->data)
	{
		root->right = BSTInsert(root->right, pt);
		root->right->parent = root;
	}

	/* return the (unchanged) node pointer */
	return root;
}

// Utility function to do level order traversal
void levelOrderHelper(Node *root)
{
	if (root != NULL)
	{
		std::queue<Node *> q;
		q.push(root);

		while (!q.empty())
		{
			Node *temp = q.front();
			cout << temp->data << " ";
			q.pop();

			if (temp->left != NULL)
				q.push(temp->left);

			if (temp->right != NULL)
				q.push(temp->right);
		}
	}
}

void RBTree::rotateLeft(Node *&root, Node *&pt)
{
	Node *pt_right = pt->right;

	pt->right = pt_right->left;

	if (pt->right != NULL)
		pt->right->parent = pt;

	pt_right->parent = pt->parent;

	if (pt->parent == NULL)
		root = pt_right;

	else if (pt == pt->parent->left)
		pt->parent->left = pt_right;

	else
		pt->parent->right = pt_right;

	pt_right->left = pt;
	pt->parent = pt_right;
}

void RBTree::rotateRight(Node *&root, Node *&pt)
{
	Node *pt_left = pt->left;

	pt->left = pt_left->right;

	if (pt->left != NULL)
		pt->left->parent = pt;

	pt_left->parent = pt->parent;

	if (pt->parent == NULL)
		root = pt_left;

	else if (pt == pt->parent->left)
		pt->parent->left = pt_left;

	else
		pt->parent->right = pt_left;

	pt_left->right = pt;
	pt->parent = pt_left;
}

// This function fixes violations
// caused by BST insertion
void RBTree::fixViolation(Node *&root, Node *&pt)
{
	Node *parent_pt = NULL;
	Node *grand_parent_pt = NULL;

	while ((pt != root) && (pt->color != BLACK) &&
		(pt->parent->color == RED))
	{

		parent_pt = pt->parent;
		grand_parent_pt = pt->parent->parent;

		/* Case : A
			Parent of pt is left child
			of Grand-parent of pt */
		if (parent_pt == grand_parent_pt->left)
		{

			Node *uncle_pt = grand_parent_pt->right;

			/* Case : 1
			The uncle of pt is also red
			Only Recoloring required */
			if (uncle_pt != NULL && uncle_pt->color ==
												RED)
			{
				grand_parent_pt->color = RED;
				parent_pt->color = BLACK;
				uncle_pt->color = BLACK;
				pt = grand_parent_pt;
			}

			else
			{
				/* Case : 2
				pt is right child of its parent
				Left-rotation required */
				if (pt == parent_pt->right)
				{
					rotateLeft(root, parent_pt);
					pt = parent_pt;
					parent_pt = pt->parent;
				}

				/* Case : 3
				pt is left child of its parent
				Right-rotation required */
				rotateRight(root, grand_parent_pt);
				swap(parent_pt->color,
						grand_parent_pt->color);
				pt = parent_pt;
			}
		}

		/* Case : B
		Parent of pt is right child
		of Grand-parent of pt */
		else
		{
			Node *uncle_pt = grand_parent_pt->left;

			/* Case : 1
				The uncle of pt is also red
				Only Recoloring required */
			if ((uncle_pt != NULL) && (uncle_pt->color ==
													RED))
			{
				grand_parent_pt->color = RED;
				parent_pt->color = BLACK;
				uncle_pt->color = BLACK;
				pt = grand_parent_pt;
			}
			else
			{
				/* Case : 2
				pt is left child of its parent
				Right-rotation required */
				if (pt == parent_pt->left)
				{
					rotateRight(root, parent_pt);
					pt = parent_pt;
					parent_pt = pt->parent;
				}

				/* Case : 3
				pt is right child of its parent
				Left-rotation required */
				rotateLeft(root, grand_parent_pt);
				swap(parent_pt->color,
						grand_parent_pt->color);
				pt = parent_pt;
			}
		}
	}

	root->color = BLACK;
}

// Function to insert a new node with given data
void RBTree::insert(const int &data)
{
	Node *pt = new Node(data);

	// Do a normal BST insert
	root = BSTInsert(root, pt);

	// fix Red Black Tree violations
	fixViolation(root, pt);
}

// Function to do inorder and level order traversals
void RBTree::inorder()	 { inorderHelper(root);}
void RBTree::levelOrder() { levelOrderHelper(root); }

// Driver Code
int main()
{
	RBTree tree;

	tree.insert(7);
	tree.insert(6);
	tree.insert(5);
	tree.insert(4);
	tree.insert(3);
	tree.insert(2);
	tree.insert(1);

	cout << "Inorder Traversal of Created Tree\n";
	tree.inorder();

	cout << "\n\nLevel Order Traversal of Created Tree\n";
	tree.levelOrder();

	return 0;
}


text:
/*
Topic: Data Structures / Trees
Sub-Topic: ZigZag Traversal of Binary Tree
Time Complexity: O(n)
Space Complexity: O(n)
*/

#include <bits/stdc++.h>
using namespace std;
struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
};

struct Node* newNode(int data)
{
    struct Node* node = new struct Node;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Printing the Traversal
void zizag_traversal(struct Node* root)
{
    if (!root)
        return;

    stack<Node*> curr;
    stack<Node*> nextlevel;

    curr.push(root);

    // Check for Stack IsEmpty() Condition
    bool pre = true;
    while (!curr.empty()) {

        // Pop
        struct Node* temp = curr.top();
        curr.pop();

          if (temp) {
            cout << temp->data << " ";

            // Storing Data according to Current Order

            if (pre) {
                if (temp->left)
                    nextlevel.push(temp->left);
                if (temp->right)
                    nextlevel.push(temp->right);
            }
            else {
                if (temp->right)
                    nextlevel.push(temp->right);
                if (temp->left)
                    nextlevel.push(temp->left);
            }
        }

        if (curr.empty()) {
            pre = !pre;
            swap(curr, nextlevel);
        }
    }
}

int main()
{
    // Creation of Tree
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(7);
    root->left->right = newNode(6);
    root->right->left = newNode(5);
    root->right->right = newNode(4);
    cout << "ZigZag Order traversal of binary tree is \n";

    zizag_traversal(root);

    return 0;
}


text:
#include<iostream>
using namespace std;

struct node{
    int data;
    struct node *left,*right;
    node(int d){
        data=d;
        left=right=NULL;
    }
};

int main(){
    struct node *root=new node(6);
    root->right=new node(8);
    root->left=new node(4);
    root->left->left=new node(2);
    root->left->right=new node(5);
    root->right->left=new node(7);
    root->right->right=new node(9);
}


text:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int diameter = 0;
        heightOfTree(root, diameter);
        return diameter;
    }

    int heightOfTree(TreeNode* node, int& d){
        if(node == NULL) return 0;

        int lh = heightOfTree(node -> left, d);
        int rh = heightOfTree(node -> right, d);

        d = max(d, rh+lh);

        return (max(lh,rh) +1);
    }
};


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

class Solution
{
public:
    vector<int> ans;

    void rightSide(TreeNode *root, int level)
    {
        if (root == NULL)
        {
            return;
        }

        if (level == ans.size())
            ans.push_back(root->val);

        rightSide(root->right, level + 1);
        rightSide(root->left, level + 1);
    }

    vector<int> rightSideView(TreeNode *root)
    {
        rightSide(root, 0);
        return ans;
    }
};


text:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while(root!=NULL && root->val != val){
            if(val<root->val){
                root = root->left;
            }
            else{
                root = root->right;
            }
        }

        return root;
    }
};


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

// A Binary Tree node
struct Node{
	int key;
	struct Node *left, *right;
};

Node * newNode(int k){
// function to create new node using the key
	Node *temp = new Node;
	temp->key = k;
	temp->left = temp->right = NULL;
	return temp;
}

// storing paths in a vector of bool
bool findPath(Node *root, vector<int> &path, int k){
	// base case
	if (root == NULL) return false;

	path.push_back(root->key);

	// See if the k is same as root's key
	if (root->key == k)
		return true;

	// Check if k is found in left or right sub-tree
	if ( (root->left && findPath(root->left, path, k)) ||
		(root->right && findPath(root->right, path, k)) )
		return true;

	// If not present in subtree rooted with root, remove root from
	// path[] and return false
	path.pop_back();
	return false;
}

// Returns LCA if node n1, n2 are present in the given binary tree, otherwise return -1
int findLCA(Node *root, int n1, int n2){
	vector<int> path1, path2;

	if ( !findPath(root, path1, n1) || !findPath(root, path2, n2))
		return -1;

	// Compare the paths to get the first different value
	int i;
	for (i = 0; i < path1.size() && i < path2.size() ; i++)
		if (path1[i] != path2[i])
			break;
	return path1[i-1];
}

// Driver program to test above functions
int main(){
    /*****************
     *  Driver program just to verify and run the LCA function
     * It can be implimented on personal use case
    ***************/

    Node * root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    cout << "lca(5, 4) = " << findLCA(root, 5, 4)<<endl;
    cout << "lca(4, 3) = " << findLCA(root, 4, 3)<<endl;
    cout << "lca(2, 6) = " << findLCA(root, 2, 6)<<endl;
    cout << "lca(3, 4) = " << findLCA(root, 3, 4)<<endl;
    return 0;
}

// A O(n) solution to find LCA of two given values n1 and n2


text:
#include<bits/stdc++.h>
using namespace std;
class TreeNode
{
    public:
    int data;
    TreeNode *left,*right;
    TreeNode(int data)
    {
        this->data=data;
        left=right=NULL;
    }
};

TreeNode* inputTree()
{
    cout<<"Enter the root data : ";
    int rootData;
    cin>>rootData;
    if(rootData==-1)
    return NULL;
    TreeNode *root=new TreeNode(rootData);

    queue<TreeNode*> pendingNodes;
    pendingNodes.push(root);

    while(pendingNodes.empty()!=true)
    {
        TreeNode* front=pendingNodes.front();
        pendingNodes.pop();

        cout<<"Enter the left child of "<<front->data<<" : ";
        int leftChildData;
        cin>>leftChildData;
        if(leftChildData!=-1)
        {
            TreeNode *leftChild=new TreeNode(leftChildData);
            front->left=leftChild;
            pendingNodes.push(leftChild);
        }

        cout<<"Enter the right child of "<<front->data<<" : ";
        int rightChildData;
        cin>>rightChildData;
        if(rightChildData!=-1)
        {
            TreeNode* rightChild=new TreeNode(rightChildData);
            front->right=rightChild;
            pendingNodes.push(rightChild);
        }
    }
    return root;
}

vector<vector<int>> verticalTraversal(TreeNode* root)
{
    map<int,map<int,multiset<int>>> nodes;
    queue<pair<TreeNode*,pair<int,int>>> todo;
    todo.push({root,{0,0}});
    while(todo.empty()!=true)
    {
        auto p=todo.front();
        todo.pop();
        TreeNode* node=p.first;
        int x=p.second.first;
        int y=p.second.second;
        nodes[x][y].insert(node->data);
        if(node->left!=NULL)
        todo.push({node->left,{x-1,y+1}});
        if(node->right!=NULL)
        todo.push({node->right,{x+1,y+1}});
    }

    vector<vector<int>> ans;
    for(auto p:nodes)
    {
        vector<int> col;
        for(auto q:p.second)
        {
            col.insert(col.end(),q.second.begin(),q.second.end());
        }
        ans.push_back(col);
    }
    return ans;
}

int main()
{
    TreeNode* root=inputTree();
    vector<vector<int>> ans=verticalTraversal(root);
    for(int i=0;i<ans.size();i++)
    {
        for(int j=0;j<ans[i].size();j++)
        {
            cout<<ans[i][j]<<" ";
        }
        cout<<"\n";
    }
}


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

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

Node* newNode(int data)
{
	Node* temp = new Node;
	temp->data = data;
	temp->left = temp->right = NULL;
	return temp;
}

void printInorder(struct Node* node)
{
	if (node == NULL)
		return;
	printInorder(node->left);
	cout << node->data << " ";
	printInorder(node->right);
}

int main()
{
	struct Node* root = newNode(1);
	root->left = newNode(2);
	root->right = newNode(3);
	root->left->left = newNode(4);
	root->left->right = newNode(5);

	cout << "\nInorder traversal of binary tree is \n";
	printInorder(root);

	return 0;
}


text:
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };

class Solution {
    void rootToLeaf(TreeNode* root,int sum,vector<int> &temp,vector<vector<int>> &v){
        sum-=root->val;
        temp.push_back(root->val);
        if(root->left==NULL && root->right==NULL){
            if(!sum) v.push_back(temp);
            sum+=root->val;
            temp.pop_back();
            return;
        }
        if(root->left) rootToLeaf(root->left,sum,temp,v);
        if(root->right) rootToLeaf(root->right,sum,temp,v);
        sum+=root->val;
        temp.pop_back();
    }
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> v;
        vector<int> temp;
        if(root==NULL) return v;
        rootToLeaf(root,targetSum,temp,v);
        return v;
    }
};


text:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> Centroid(vector<ll> g[], ll n)
{
    vector<ll> centroid;
    vector<ll> sz(n);
    function<void(ll, ll)> dfs = [&](ll u, ll prev)
    {
        sz[u] = 1;
        bool is_centroid = true;
        for (auto v : g[u])
            if (v != prev)
            {
                dfs(v, u);
                sz[u] += sz[v];
                if (sz[v] > n / 2)
                    is_centroid = false;
            }
        if (n - sz[u] > n / 2)
            is_centroid = false;
        if (is_centroid)
            centroid.push_back(u);
    };
    dfs(0, -1);
    return centroid;
}
int main()
{
    ll n;
    cout << "Enter nodes: ";
    cin >> n;
    vector<ll> v[n];
    cout << "Enter edges: ";
    for (ll i = 0; i < n - 1; i++)
    {
        ll a, b;
        cin >> a >> b;
        a--;
        b--;
        v[a].push_back(b);
    }
    cout << " Centroids: \n";
    vector<ll> centroid = Centroid(v, n);
    for (ll i = 0; i < centroid.size(); i++)
        cout << centroid[i] + 1 << "\n";
    return 0;
}


text:
class Solution {
public:
    int maxSubArray(vector<int>& nums) {

        int sum=0;
        int maxi = INT_MIN;
        for(int i=0;i<nums.size();i++)
        {
            sum += nums[i];
            maxi = max(sum,maxi);
            if(sum<0)
            {
                sum=0;
            }
        }
        return maxi;

    }
};


text:
#include <stdio.h>

int search(int arr[], int N, int x)
{
    int i;
    for (i = 0; i < N; i++)
        if (arr[i] == x)
            return i;
    return -1;
}

// Driver's code
int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int N = sizeof(arr) / sizeof(arr[0]);

    // Function call
    int result = search(arr, N, x);
    (result == -1)
        ? printf("Element is not present in array")
        : printf("Element is present at index %d", result);
    return 0;
}


text:
/*
Given an array arr[] of N non-negative integers representing the height of blocks. If width of each block is 1, compute how much water can be trapped between the blocks during the rainy season.

Example 1:

Input:
N = 6
arr[] = {3,0,0,2,0,4}
Output:
10
Explanation:

Example 2:

Input:
N = 4
arr[] = {7,4,0,9}
Output:
10
Explanation:
Water trapped by above
block of height 4 is 3 units and above
block of height 0 is 7 units. So, the
total unit of water trapped is 10 units.
Example 3:

Input:
N = 3
arr[] = {6,9,9}
Output:
0
Explanation:
No water will be trapped.

Your Task:
You don'y need to read input or print anything. The task is to complete the function trappingWater() which takes arr and N as input parameters and returns the total amount of water that can be trapped.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Constraints:
3 <= N <= 107
0 <= Ai <= 108
*/

// { Driver Code Starts
#include<bits/stdc++.h>

using namespace std;

 // } Driver Code Ends

class Solution{

    // Function to find the trapped water between the blocks.
    public:
    int trappingWater(int arr[], int n){
        // Code here
        int left[n];
        int right[n];
        int sum=0,max1=0,max2=0;
        for(int i=0;i<n;i++){
            left[i]=max1;
            if(max1<arr[i]) max1=arr[i];
        }
        for(int i=n-1;i>=0;i--){
            right[i]=max2;
            if(max2<arr[i]) max2=arr[i];
        }
        for(int i=0;i<n;i++){
            int d= min(left[i],right[i]);
            if(d>arr[i]) sum=sum +(d-arr[i]);
        }
        return sum;
    }
};

// { Driver Code Starts.

int main(){

    int t;
    //testcases
    cin >> t;

    while(t--){
        int n;

        //size of array
        cin >> n;

        int a[n];

        //adding elements to the array
        for(int i =0;i<n;i++){
            cin >> a[i];
        }
        Solution obj;
        //calling trappingWater() function
        cout << obj.trappingWater(a, n) << endl;

    }

    return 0;
}  // } Driver Code Ends


text:
#include<iostream>
using namespace std;

//fibonacci search of elemet on sorted array arr of size n
//iterative approach
//time : O(log(n))
//space : O(1)
//f(n)~c*1.62^n
//O(log₁.₆₂(n)) not better than Binary search O(log₂(n))
int FibonacciSearch(int arr[], int n, int element){
    int f2=0;
    int f1=1;
    int f0=f2+f1;

    while(f0<n){
        f2=f1;
        f1=f0;
        f0=f1+f2;
    }
    int offset=-1;
    while(f0>1){
        int i = min(offset+f2,n-1);
        if(arr[i]<element){
            f0=f1;
            f2=f0-f2;
            f1=f0-f2;
            offset=i;
        }
        else if(arr[i]>element){
            f0=f2;
            f1=f1-f2;
            f2=f0-f1;
        }
        else return i;
    }
    if (arr[n-1] == element)
            return n-1;
    return -1;
}
int main(){
    int arr[]={0,1,2,3,4,5,6,7,8,9,10,11,12};
    int n=sizeof(arr)/sizeof(int);
    for (int i=0;i<=n;i++)
    {
        if(i!=FibonacciSearch(arr,n,i))
            cout<<"failled at "<<i<<" with output "<<FibonacciSearch(arr,i,n)<<endl;
    }
    cout<<endl;
}


text:
#include <iostream>
using namespace std;

// function to check for
// perfect square number
int checkPerfectSquare(
    long int N,
    long int start,
    long int last)
{
    // Find the mid value
    // from start and last
    long int mid = (start + last) / 2;

    if (start > last) {
        return -1;
    }

    // check if we got the number which
    // is square root of the perfect
    // square number N
    if (mid * mid == N) {
        return mid;
    }

    // if the square(mid) is greater than N
    // it means only lower values then mid
    // will be possibly the square root of N
    else if (mid * mid > N) {
        return checkPerfectSquare(
            N, start, mid - 1);
    }

    // if the square(mid) is less than N
    // it means only higher values then mid
    // will be possibly the square root of N
    else {
        return checkPerfectSquare(
            N, mid + 1, last);
    }
}

// Driver code
int main()
{
    long int N = 65;

    cout << checkPerfectSquare(N, 1, N);
    return 0;
}


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

int BinarySearch(vector<int> v, int key) {
    sort(v.begin(), v.end());

    int low = 0, high = v.size()-1;

    while(low <= high) {
        int mid = low + (high - low) / 2;
        if(v[mid] == key) return mid;
        else if(key < v[mid]) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

int main() {
    vector<int> v = {5, 4, 1, 2, 3};
    cout<<BinarySearch(v, 2);
    return 0;
}


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

// A Linked List node
struct Node
{
	int data;
	Node* next;
};

// Returns true if first list is present in second
// list
bool findList(Node* first, Node* second)
{
	Node* ptr1 = first, *ptr2 = second;

	// If both linked lists are empty, return true
	if (first == NULL && second == NULL)
		return true;

	// Else If one is empty and other is not return
	// false
	if ( first == NULL ||
		(first != NULL && second == NULL))
		return false;

	// Traverse the second list by picking nodes
	// one by one
	while (second != NULL)
	{
		// Initialize ptr2 with current node of second
		ptr2 = second;

		// Start matching first list with second list
		while (ptr1 != NULL)
		{
			// If second list becomes empty and first
			// not then return false
			if (ptr2 == NULL)
				return false;

			// If data part is same, go to next
			// of both lists
			else if (ptr1->data == ptr2->data)
			{
				ptr1 = ptr1->next;
				ptr2 = ptr2->next;
			}

			// If not equal then break the loop
			else break;
		}

		// Return true if first list gets traversed
		// completely that means it is matched.
		if (ptr1 == NULL)
			return true;

		// Initialize ptr1 with first again
		ptr1 = first;

		// And go to next node of second list
		second = second->next;
	}

	return false;
}

/* Function to print nodes in a given linked list */
void printList(Node* node)
{
	while (node != NULL)
	{
		printf("%d ", node->data);
		node = node->next;
	}
}

// Function to add new node to linked lists
Node *newNode(int key)
{
	Node *temp = new Node;
	temp-> data= key;
	temp->next = NULL;
	return temp;
}

/* Driver program to test above functions*/
int main()
{
	/* Let us create two linked lists to test
	the above functions. Created lists shall be
		a: 1->2->3->4
		b: 1->2->1->2->3->4*/
	Node *a = newNode(1);
	a->next = newNode(2);
	a->next->next = newNode(3);
	a->next->next->next = newNode(4);

	Node *b = newNode(1);
	b->next = newNode(2);
	b->next->next = newNode(1);
	b->next->next->next = newNode(2);
	b->next->next->next->next = newNode(3);
	b->next->next->next->next->next = newNode(4);

	findList(a,b) ? cout << "LIST FOUND" :
					cout << "LIST NOT FOUND";

	return 0;
}

//Revised by Debasish Behera


text:
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main(){
     ll n,k;
     cin>>n>>k;
     //p--> put->how many times candies kept
     //e--> eat->how many times candies ate
     ll l=0,h=n,m=l+(h-l)/2,e,p;
     while(l<=h){
         m=l+(h-l)/2;
         e=m;
         p=n-m;
         ll x=(p*(p+1))/2;
         //x--> total how many candies there in the box if we put p times
         if(x-e>k){
            l=m+1;
         }
         else if(x-e<k){
            h=m-1;
         }
         else{
            break;
         }
     }
     cout<<e;
}


text:
class Solution {
public:
    int leftResult(vector<int>nums, int target){
        int start=0;
        int end=nums.size()-1;
        int left_result = -1;
        while(start<=end){
            int mid=start+((end-start)/2);
            if(target==nums[mid]){
                left_result=mid;
                end=mid-1;
            }
            else if(target<nums[mid])
                end=mid-1;
            else
                start=mid+1;
        }
        return left_result;
    }
    int rightResult(vector<int>nums, int target){
        int start=0;
        int end=nums.size()-1;
        int right_result=-1;
        while(start<=end){
            int mid=start+((end-start)/2);
            if(target==nums[mid]){
                right_result=mid;
                start=mid+1;
            }
            else if(target<nums[mid])
                end=mid-1;
            else
                start=mid+1;
        }
        return right_result;
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        int left_result=leftResult(nums, target);
        int right_result=rightResult(nums, target);
        vector<int>v;
        v.push_back(left_result);
        v.push_back(right_result);
        return v;
    }
};


text:
/*
You are given an array of integers. Find a peak element in it.
An element of a Array is said to be peak if it is NOT smaller than any of its its neighbours.
For corner elements, we need to consider only one neighbour.

Example:
Input: arr[]= {5, 10, 20, 15}
       Output: 20
       Element 20 has neighbours 10 and 15,
       both of them are less than 20.

Input: arr[] = {10, 20, 15, 2, 23, 90, 67}
       Output: 20 or 90
       The element 20 has neighbours 10 and 15,
       both of them are less than 20, similarly 90 has neighbours 23 and 67.

Approach:
  If in the array, the first element is greater than the second or the last element is greater than the second last, print the respective element and terminate the program.
Else traverse the array from the second index to the second last index
If for an element array[i], it is greater than both its neighbours, i.e., array[i] > array[i-1] and array[i] > array[i+1], then print that element and terminate.

Time complexity: O(n)
Space Complexity: O(1)
*/

#include <bits/stdc++.h>
using namespace std;
int findPeak(int arr[], int n)
{
    if (n == 1)      // when either first or last element is the peak element
      return 0;
    if (arr[0] >= arr[1])
        return 0;
    if (arr[n - 1] >= arr[n - 2])
        return n - 1;

    		// check if other elements can be the peak element
    for (int i = 1; i < n - 1; i++) {

	        // check for the presence of smaller neighbors
        if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1])
            return i;
    }
}

// Driver Code
int main()
{
    int arr[] = { 1, 3, 20, 4, 1, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Index of a peak point is "
         << findPeak(arr, n);
    return 0;
}


text:
/*
Search an element in a Rotated Sorted Array.
Given the array nums after the possible rotation and an integer target, return the index of target if
it is in nums, or -1 if it is not in nums.

Example:
Input: arr[]= {4,5,6,7,0,1,2}, target = 0
       Output: 4

Input: arr[] = {10, 20, 25, 28, 2, 8, 9}
       Output: 4

Time complexity: O(log N)
Space Complexity: O(1)
*/
#include <bits/stdc++.h>
using namespace std;

    int findIndex(vector<int>& nums){

        int n = nums.size();
        int start = 0, end = n-1;

        while(start <= end){
            int mid = start + (end-start)/2;
            int prev = (mid-1+n)%n;
            int next = (mid+1)%n;

            if(nums[mid] < nums[prev] && nums[mid] <= nums[next])
                return mid;
            else if(nums[mid] > nums[end])
                start = mid+1;
            else
                end = mid-1;
        }
        return 0;
    }
    int binarySearch(vector<int>& nums, int T, int start, int end){

        while(start <= end){
            int mid = start + (end-start)/2;

            if(nums[mid] == T)
                return mid;
            else if(T < nums[mid])
                end = mid-1;
            else
                start = mid+1;
        }
        return -1;
    }
    int search(vector<int>& nums, int T) {

        int n = nums.size();
        if(n == 1 && nums[0] != T)
            return -1;

        int index = findIndex(nums);
        int a = binarySearch(nums, T, 0, index-1);
        int b = binarySearch(nums, T, index, n-1);

        return a == -1? b : a;
    }
    int main(){
        int vector<int> arr{ 4, 5, 6, 7, 0, 1, 2 };
        int tar = 0;
        cout << "Index of element is :"<< search(arr, tar);
        return 0;
    }


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

int InterpolationSearch(int arr[], int lo, int hi, int x)
{
	int pos;

	if (lo <= hi && x >= arr[lo] && x <= arr[hi]) {

		pos = lo
			+ (((double)(hi - lo) / (arr[hi] - arr[lo]))
				* (x - arr[lo]));

		if (arr[pos] == x)
			return pos;

		if (arr[pos] < x)
			return InterpolationSearch(arr, pos + 1, hi, x);

		if (arr[pos] > x)
			return InterpolationSearch(arr, lo, pos - 1, x);
	}
	return -1;
}

int main()
{

	int arr[] = { 13, 15, 76, 34, 28, 9, 67, 91, 2 };

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

	int x = 18;
	int index = InterpolationSearch(arr, 0, n - 1, x);

	if (index != -1)
		cout << "Element found at index " << index;
	else
		cout << "Element not found.";

	return 0;
}


text:
// to decrpyt what we just encrypted , we subtract 1 from the ascii value of the encrypted message.
#include<stdio.h>
#include<string.h>
void decrypt (char *str){
    char *ptr=str;
    while(*ptr!='\0'){
        *ptr=*ptr-1;
        ptr++;
    }
}
int main(){
    char str[]="nxpovtff";
    decrypt(str);
    printf("Decrypted string:%s",str);
    return 0;
}


text:
//encrypt a string by adding 1 to the ascii value of its characters
#include<stdio.h>
#include<string.h>
void encrypt (char *str){
    char *ptr=str;
    while(*ptr!='\0'){
        *ptr=*ptr+1;
        ptr++;
    }
}
int main(){
    char str[]="mwonusee";
    encrypt(str);
    printf("Encrypted string:%s",str);
    return 0;
}


text:
#include <iostream>
#include <queue>
#include <vector>
#include <cstdlib>
using namespace std;
 class Stack
{
    queue<int> q1, q2;
 public:
    void push(int data)
    {
        while (!q1.empty())
        {
            q2.push(q1.front());
            q1.pop();
        }
        q1.push(data);
         while (!q2.empty())
        {
            q1.push(q2.front());
            q2.pop();
        }
    }
     int pop()
    {
        if (q1.empty())
        {
            cout << "Underflow!!";
            exit(0);
        }
        int front = q1.front();
        q1.pop();

        return front;
    }
};

int main()
{
    vector<int> keys = { 1, 2, 3, 4, 5 };
     Stack s;
    for (int key: keys) {
        s.push(key);
    }

    for (int i = 0; i <= keys.size(); i++) {
        cout << s.pop() << endl;
    }

    return 0;
}


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

void solve(){
    int n,k;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<int> count;
    for(int i=0;i<27;i++){
        count.push_back(0);
    }
    map<char,int> mp;
    int j=1;
    for(char c='a';c<='z';c++){
        mp[c]=j;
        j++;
    }
    for(int i=0;i<n;i++){
        int val1=mp[s[i]];
        count[val1]++;
    }

    string copy=s;
    sort(all(copy));

    vector<int> count1;
    for(int i=0;i<27;i++){
        count1.push_back(0);
    }
    for(int i=0;i<k;i++){
        int val1=mp[copy[i]];
        count1[val1]++;
    }
    string anwser="";
    for(int i=0;i<n;i++){
        int val1=mp[s[i]];
        if(count1[val1]){
            count1[val1]--;
        }
        else{
            anwser.push_back(s[i]);
        }
    }
    cout << anwser << endl;
}

int main(){
  init();
  IOS;
  ll t=1;
  // cin >> t;
  while(t--){
      solve();
  }
}


text:
/*
Given two arrays a[] and b[] respectively of size n and m, the task is to print the count of elements in the intersection (or common elements) of the two arrays.
For this question, the intersection of two arrays can be defined as the set containing distinct common elements between the two arrays.

Example 1:

Input:
n = 5, m = 3
a[] = {89, 24, 75, 11, 23}
b[] = {89, 2, 4}

Output: 1

Explanation:
89 is the only element in the intersection of two arrays.
Example 2:

Input:
n = 6, m = 5
a[] = {1, 2, 3, 4, 5, 6}
b[] = {3, 4, 5, 6, 7}

Output: 4

Explanation:
3 4 5 and 6 are the elements in the intersection of two arrays.

Expected Time Complexity: O(n + m).
Expected Auxiliary Space: O(min(n,m)).

Constraints:
1 ≤ n, m ≤ 10^5
1 ≤ a[i], b[i] ≤ 10^5
*/

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

class Solution {
  public:
    // Function to return the count of the number of elements in
    // the intersection of two arrays.
    int NumberofElementsInIntersection(int a[], int b[], int n, int m) {
        unordered_map<int,int> hash1, hash2;
        // Storing the Elements of both Arrays in Hashmaps
        for(int i=0; i<n; ++i) hash1[a[i]]++;
        for(int j=0; j<m; ++j) hash2[b[j]]++;
        int ans=0;
        // Checking for the intersection
        for(auto i: hash1) {
            if(i.second>0 and hash2[i.first]>0) ans++;
        }
        return ans;
    }
};

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        int a[n], b[m];
        for (int i = 0; i < n; i++) cin >> a[i];

        for (int i = 0; i < m; i++) cin >> b[i];
        Solution ob;
        cout << ob.NumberofElementsInIntersection(a, b, n, m) << endl;
    }
    return 0;
}


text:
/*
Given an array Arr of N positive integers and another number X. Determine whether or not there exist two elements in Arr whose sum is exactly X.

Example 1:

Input:
N = 6, X = 16
Arr[] = {1, 4, 45, 6, 10, 8}
Output: Yes
Explanation: Arr[3] + Arr[4] = 6 + 10 = 16
Example 2:

Input:
N = 5, X = 10
Arr[] = {1, 2, 4, 3, 6}
Output: Yes
Explanation: Arr[2] + Arr[4] = 4 + 6 = 10

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Constraints:
1 ≤ N ≤ 10^5
1 ≤ Arr[i] ≤ 10^5

*/

#include <bits/stdc++.h>

using namespace std;

//User function template for C++
class Solution{
public:
	// Function to check if array has 2 elements
	// whose sum is equal to the given value
	bool hasArrayTwoCandidates(int arr[], int n, int x) {
	    int hash[100005]={0};
	    for(int i=0; i<n; ++i) {
            // Checking if the element (target-arr[i]) was incurred before
	        if((x-arr[i])>=0 and hash[x-arr[i]]>0) return true;
	        hash[arr[i]]++;
	    }
	    return false;
	}
};

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, x;
        cin >> n >> x;
        int arr[n];
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        Solution ob;
        auto ans = ob.hasArrayTwoCandidates(arr, n, x);
        cout << (ans ? "Yes\n" : "No\n");
    }
    return 0;
}


text:
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        unordered_map<int, int> remainders;// key: remainder, value: index
        vector<int> res(2);
        for(unsigned int i = 0; i < nums.size(); i++){
            int rem = target - nums[i];
            if(remainders.find(nums[i]) == remainders.end()){
                remainders[rem] = i;
            }else{
                res[1] = i;
                res[0] = remainders[nums[i]];
                return res;
            }
        }
        return res;
    }
};


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

#define vi vector<int>
#define pii pair<int,int>
#define vii vector<pii>
#define ff first
#define ss second
#define ll long long

void helper(int r, int c, vector<vector<char> > &a, map<pair<int,int>,map<int,int>> &mp, vector<map<int,int>> row, vector<map<int,int>> col)
{
   if(r==9)
   {
      for(auto it : a)
      {
         for(auto i : it)
         {
            cout<<i<<" ";
         }
         cout<<"\n";
      }
      cout<<"\n";
      return;
   }

   if(c == 9)
   {
      helper(r+1, 0, a, mp, row, col);
      return;
   }

   if(a[r][c] != '.') //अगर जगह खाली नहीं है
   {
      helper(r, c+1, a, mp, row, col);
      return;
   }

   for(int i=1;i<=9;i++)
   {
      int rw = r/3, cl = c/3;
      if(!mp[{rw, cl}][i] and !row[r][i] and !col[c][i])
      {
         mp[{rw, cl}][i] = 1;
         row[r][i] = 1;
         col[c][i] = 1;
         a[r][c] = i + '0';

         helper(r, c+1, a, mp, row, col);

         mp[{rw, cl}][i] = 0;
         row[r][i] = 0;
         col[c][i] = 0;
         a[r][c] = '.';
      }
   }
}

void SolveSudoku(vector<vector<char> > &a)
{
   map<pair<int,int>,map<int,int>> mp;

   vector<map<int,int>> row(9);
   vector<map<int,int>> col(9);

   for(int i=0;i<9;i++)
   {
      for(int j=0;j<9;j++)
      {
         if(a[i][j] != '.')
         {
            mp[{i/3, j/3}][a[i][j]-'0'] = 1;
            row[i][a[i][j]-'0'] = 1;
            col[i][a[i][j]-'0'] = 1;
         }
      }
   }
   helper(0,0,a,mp,row,col);
}

int main()
{
   vector<vector<char> > Soduku = {
                       { '6', '2', '.', '.', '.', '.', '.', '.', '.' },
                       { '3', '.', '6', '5', '.', '8', '4', '.', '.' },
                       { '.', '8', '7', '.', '.', '.', '.', '3', '1' },
                       { '.', '.', '3', '.', '1', '.', '.', '8', '.' },
                       { '9', '.', '.', '8', '6', '3', '.', '.', '5' },
                       { '.', '5', '.', '.', '9', '.', '6', '.', '.' },
                       { '1', '3', '.', '.', '.', '.', '2', '5', '.' },
                       { '.', '.', '.', '.', '.', '.', '.', '7', '4' },
                       { '.', '.', '5', '2', '.', '6', '3', '.', '.' } };

   SolveSudoku(Soduku);
   return 0;
}


text:
/*
Given an array arr of size n and an integer X. Find if there's a triplet in the array which sums up to the given integer X.

Example 1:
Input:
n = 6, X = 13
arr[] = [1 4 45 6 10 8]
Output:
1
Explanation:
The triplet {1, 4, 8} in
the array sums up to 13.

Example 2:

Input:
n = 5, X = 10
arr[] = [1 2 4 3 6]
Output:
1
Explanation:
The triplet {1, 3, 6} in
the array sums up to 10.

Expected Time Complexity: O(n2)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ n ≤ 10^3
1 ≤ A[i] ≤ 10^5
*/

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

class Solution {
    public:
    //Function to find if there exists a triplet in the
    //array A[] which sums up to X.
    bool find3Numbers(int A[], int n, int X)
    {
        sort(A,A+n);    // Sorting Array
        int ans=0;
        for(int i=1; i<=(n-2); ++i) {
            int l=0, r=n-1;
            // Fixing A[i] and find A[l] and A[r] which sums upto target X.
            while(l<=r and l<i and r>i) {
                int sum=A[l]+A[i]+A[r];
                if(sum<=X) {
                    if(sum==X) ans++;
                    l++;
                }
                else r--;
            }
        }
        return (ans>0?1:0);
    }
};
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,X;
		cin>>n>>X;
		int i,A[n];
		for(i=0;i<n;i++)
			cin>>A[i];
		Solution ob;
        cout <<  ob.find3Numbers(A, n, X) << endl;
    }
}


text:
/*
Given a non-empty array of integers, find the top k elements which have the highest frequency in the array. If two numbers have the same frequency then the larger number should be given preference.

Example 1:

Input:
nums = {1,1,1,2,2,3},
k = 2
Output: {1, 2}
Example 2:

Input:
nums = {1,1,2,2,3,3,3,4},
k = 2
Output: {3, 2}
Explanation: Elements 1 and 2 have the
same frequency ie. 2. Therefore, in this
case, the answer includes the element 2
as 2 > 1.

Expected Time Complexity : O(NlogN)
Expected Auxilliary Space : O(N)

Constraints:
1 <= N <= 10^5
1<=A[i]<=10^5
*/

#include <bits/stdc++.h>
using namespace std;
class Solution {
  public:
    vector<int> topK(vector<int>& nums, int k) {
        map<int,int> freq;   //Storing the Frequency of each element in Hash Map
        for(int i=0; i<nums.size(); ++i) {
            freq[nums[i]]++;
        }
        vector<pair<int,int>> vec;
        for(auto i: freq) {
            vec.push_back({i.second,i.first});
        }
        // Storing {Freqency, Element} pair in vector and sorting descending order to take top k elements
        sort(vec.rbegin(),vec.rend());
        vector<int> ans;
        int len=vec.size();
        for(int i=0; i<min(k,len); ++i) ans.push_back(vec[i].second);
        return ans;
    }
};

int main() {
    int tc;
    cin >> tc;
    while (tc--) {
        int n;
        cin >> n;
        vector<int> nums(n);
        for (auto &i : nums) cin >> i;
        int k;
        cin >> k;
        Solution obj;
        vector<int> ans = obj.topK(nums, k);
        for (auto i : ans) cout << i << " ";
        cout << "\n";
    }
    return 0;
}


text:
class Solution {
public:
    int firstUniqChar(string s) {

        unordered_map<int , int> m;
        for(auto i : s){
            m[i]++;
        }
        int ans = -1;
        bool flag = false;
        for(int i = 0; i< s.size(); i++){
            for(auto itr : m){
                if(char(itr.first )== s[i] && itr.second == 1){
                    ans = i;
                    return i;
                }
            }

        }
        return ans;

    }
};


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

class Node{

    public:
        int data;
        Node* next;

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

    //destructor
    ~Node(){
        int value = this->data;
        if(this->next != NULL){
            delete next;
            this->next = NULL;
        }
        cout<<"Deleted value is : "<< value << endl;
    }
};

void insertNode(Node* &tail , int ele , int data){

    //empty list
    if(tail == NULL){
        Node* temp = new Node(data);
        temp->next = temp;
        tail = temp;
    }

    else{
        //non-empty list
        //assuming that the element is present in the list

        Node* curr = tail;

        while(curr->data != ele) {
            curr = curr -> next;
        }

        //element found -> curr is representing element wala node
        Node* temp = new Node(data);
        temp -> next = curr -> next;
        curr -> next = temp;

    }
}

void print(Node* tail) {

    Node* temp = tail;

    //empty list
    if(tail == NULL) {
        cout << "List is Empty "<< endl;
        return ;
    }

    do {
        cout << tail -> data << " ";
        tail = tail -> next;
    } while(tail != temp);

    cout << endl;
}

void deleteNode(Node* &tail, int value) {

    //empty list
    if(tail == NULL) {
        cout << " List is empty, please check again" << endl;
        return;
    }
    else{
        //non-empty

        //assuming that "value" is present in the Linked List
        Node* prev = tail;
        Node* curr = prev -> next;

        while(curr -> data != value) {
            prev = curr;
            curr = curr -> next;
        }

        prev -> next = curr -> next;

        //1 Node Linked List
        if(curr == prev) {
            tail = NULL;
        }

        //>=2 Node linked list
        else if(tail == curr ) {
            tail = prev;
        }

        curr -> next = NULL;
        delete curr;

    }
}

int main(){

    Node* tail = NULL;
    insertNode(tail, 5, 3);
    print(tail);

    insertNode(tail, 3, 5);
    print(tail);

    insertNode(tail, 5, 7);
    print(tail);
    insertNode(tail, 7, 9);
    print(tail);
    insertNode(tail, 5, 6);
    print(tail);

    insertNode(tail, 9, 10);
    print(tail);
    insertNode(tail, 3, 4);
    print(tail);

    deleteNode(tail, 5);
    print(tail);
    return 0;
}


text:
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    int data;
    struct node *prev;
    struct node *next;
} no;
int main()
{
    int n;
    no *head, *last;
    head = NULL;
    last = NULL;
    printf("Enter the total number of nodes in list: ");
    scanf("%d", &n);
    int i, data;
    no *newNode;
    if (n >= 1)
    {
        head = (no *)malloc(sizeof(no));
        printf("Enter data of 1 node: ");
        scanf("%d", &data);
        head->data = data;
        head->prev = NULL;
        head->next = NULL;
        last = head;
        for (i = 2; i <= n; i++)
        {
            newNode = (no *)malloc(sizeof(no));
            printf("Enter data of %d node: ", i);
            scanf("%d", &data);
            newNode->data = data;
            newNode->prev = last;
            newNode->next = NULL;
            last->next = newNode;
            last = newNode;
        }
    }
    no *temp;
    temp = head;
    while (temp->next != 0)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("%d ", temp->data);
    printf("\n");
    int p;
    printf("Enter the position to be updated:");
    scanf("%d", &p);
    int data1;
    printf("Enter a data:");
    scanf("%d", &data1);
    no *temp1;
    temp1 = head;
    for (int i = 0; i < (p-1); i++)
    {
        temp1 = temp1->next;
    }
    temp1->data = data1;
    no *temp2;
    temp2 = head;
    printf("Resultant linked list :\n");
    while (temp2->next != 0)
    {
        printf("%d ", temp2->data);
        temp2 = temp2->next;
    }
    printf("%d ", temp2->data);
    no *temp3;
    temp3=head;
    int length=0;
    while(temp3->next!=0){
        length++;
        temp3=temp3->next;
    }
    return 0;
}


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

class Node{

    public:
        int data;
        Node* next;

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

    //destructor
    ~Node(){
        int value = this->data;
        if(this->next != NULL){
            delete next;
            this->next = NULL;
        }
        cout<<"Deleted value is : "<< value << endl;
    }
};

void insertAtHead(Node* &head , int data){   //head is taken as reference

    //new Node created
    Node* temp = new Node(data);
    temp->next = head;
    head = temp;
}

//insert a new node at last
//we make use of tail pointer that always shows the last node in given LL
void insertAtTail(Node* &tail , int data){

    //new Node created
    Node* temp = new Node(data);
    tail->next = temp;
    tail = temp;
}

void insertAtPosition(Node* &head , Node* &tail , int data , int pos){

    if(pos == 1)
    {
        insertAtHead(head , data);
        return;
    }

    //new Node created
    Node* temp = new Node(data);

    Node* p = head;
    int count = 1;
    while(count < pos-1){
        p = p->next;
        count++;
    }

    if(p->next == NULL){
        insertAtTail(tail , data);
        return ;
    }

    temp->next = p->next;
    p->next = temp;
}

//delete start node
void deleteHead(Node* &head){
    Node* temp = head;
    head = head -> next;
    temp->next = NULL;
    delete temp;
}

void deleteAtPosition(Node* &head , Node* &tail , int pos){

    if(pos == 1){
        deleteHead(head);
        return ;
    }

    else{
        Node* curr = head;
        Node* prev = NULL;
        int count = 1;

        while(count < pos){
            prev = curr;
            curr = curr->next;
            count++;
        }

        prev->next = curr->next;
        if(curr->next == NULL){
            tail = prev;
        }
        curr->next = NULL;
        delete curr;
    }
}

void display(Node* &head){
    Node* p = head;
    while(p != NULL){
        cout<< p->data << " ";
        p = p->next;
    }
    cout<<endl;
}

int main(){

    Node* head = new Node(10);  //new Node created and passed data
    Node* tail = head;

    insertAtHead(head , 5);
    display(head);

    insertAtTail(tail,15);
    display(head);

    insertAtPosition(head , tail , 12 , 3);
    display(head);

    deleteAtPosition(head , tail , 4);
    display(head);
    cout<<"tail data : "<<tail->data;
    return 0;
}


text:
#include <iostream>
using namespace std;
class Node
{
public:
    int data;
    Node *next;
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};
Node *takeinput()
{
    int data;
    cin >> data;
    Node *head = NULL;
    Node *tail = NULL;
    while (data != -1)
    {
        Node *newdata = new Node(data);
        if (head == NULL)
        {
            head = newdata;
            tail = newdata;
        }
        else
        {
            tail->next = newdata;
            tail = newdata;
        }
        cin >> data;
    }
    return head;
}
Node *deleteNode(Node *head, int i)
{

    int count = 0;
    Node *temp = head;
    if (head == NULL)
    {
        return NULL;
    }
    if (i == 0)
    {
        head = head->next;
        delete temp;
        return head;
    }
    else
    {

        while (count <= i - 2 && temp != NULL)
        {
            temp = temp->next;
            count++;
        }
        if (temp != NULL && temp->next != NULL)
        {
            Node *a = temp;
            temp = a->next;
            Node *newnode = temp->next;
            a->next = newnode;
            delete temp;
        }
        return head;
    }
}
void print(Node *head)
{
    Node *temp = head;
    while (temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}
int main()
{
    Node *head = takeinput();
    int i;
    cin >> i;
    head = deleteNode(head, i);
    print(head);
}


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

class node
{
    public:
    int v;
    node *next;
    node()
    {
        next= NULL;
    }
}*first, *save, *ptr, *newptr, *rear;
int m = 0;
node* createnode(int j)
{
    newptr = new node;
    newptr->v = j;
    newptr->next = NULL;
    return newptr;
}
void lib(node *p) //insert at beginning
{
    if(first == NULL)
    {
        first = p;
        rear = p;
    }
    else
    {
        save = first;
        first = p;
        p->next = save;
    }

    //cout<<rear->v<<" ";
    m++;
}

void lie(node *p) //insert at end
{

    rear->next = p;
    rear = p;

    m++;
    //cout<<rear->v<<" ";
}

void lim(node *p, int pos) //insert in mid
{
    ptr = first;
    //cout<<ptr->v<<" ";
    int i = 1;
    while(i < pos-1)
    {
        i++;
        ptr = ptr->next;
    }

    save = ptr->next;
    ptr->next = p;
    p->next = save;

    m++;
}
void del(int x)
{
    ptr = first;
    int flag = 1;
    while(flag)
    {
        if(x == first->v)
            {
                save = ptr;
                first = first->next;
                delete(save);
                m--;
                flag = 0;
            }
        else
        if((ptr->next)->v == x)
        {

            save = ptr->next;
            if((ptr->next)->next == NULL)
                rear = ptr;
            ptr->next = (ptr->next)->next;

            delete(save);
            flag = 0;
            m--;

        }
        else ptr = ptr->next;
        if(ptr->next == NULL)
           break;
    }
    if(flag)
      cout<<"Number doesn't exist\n";
}

void display()
{
    ptr = first;
    int flag = 1;
    while(flag)
    {
        cout<<ptr->v<<" ";
        if(ptr->next == NULL)
           break;
        ptr = ptr->next;

    }
    cout<<endl;

}

int main()
{
    //first = rear = NULL;
    char ch = 'y';
    while(tolower(ch) == 'y')
    {
        int n;
        cout<<"3 CHOICES:\n";
        cout<<"1. insert  2. delete 3. display\n";
        cout<<"Enter your choice- ";
        cin>>n;
        switch(n)
        {
            case 1: {cout<<"No of list elements- "<<m<<endl;
                    cout<<"Enter position of insertion : ";
                    int pos;
                    cin>>pos;
                    if(pos>m+1 || pos<1)
                       cout<<"Position doesn't exist\n";
                    else
                    {
                        cout<<"Enter number to be inserted- ";
                        int j; cin>>j;
                        node *pp = createnode(j);
                        if(pos == 1)
                            lib(pp);

                        else if(pos == m+1)
                            lie(pp);
                        else
                            lim(pp, pos);

                    }}
                    break;

            case 2: {cout<<"Elements present: \n";
                    display();
                    cout<<"Enter number to be deleted: ";
                    int j; cin>>j;
                    del(j);}
                    break;

            case 3: display();
        }
        cout<<"Do you want to continue? (n/y): ";
        cin>>ch;

    }
    return 0;
}


text:
Write a program to reverse a given linked list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

#include <iostream>
using namespace std;

class Node
{
public:
    Node(int val)
    {
        this->data = val;
        this->next = NULL;
    }
	int data;
	Node* next;
};

void reverse(Node** head_ref)
{
	Node* curr = *head_ref;

	Node* prev = NULL;
	Node* next = NULL;

	while (curr != NULL)
	{
		next = curr->next;
		curr->next = prev;
		prev = curr;
		curr = next;
	}
	*head_ref = prev;
}

void push( Node** head_ref, int val)
{
	Node* new_node = new Node(val);
	new_node->next = (*head_ref);
	(*head_ref) = new_node;
}

void printList( Node* head)
{
	Node* curr = head;
	while (curr != NULL)
	{
		cout << curr->data << " ";
		curr = curr->next;
	}
	cout << endl;
}

int main()
{
	Node* head = NULL;

	push(&head, 20);
	push(&head, 4);
	push(&head, 15);
	push(&head, 85);

	cout << "Given Linked List: " << endl;
	printList(head);

	reverse(&head);

	cout << "Reversed Linked list: " << endl;
	printList(head);

	return 0;
}


text:
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head=new  ListNode();
         ListNode* output=head;
        int c=0; //carry
        while(l1 != 0 || l2 != 0)
        {
            int sum=(l1 != 0 ? l1 ->val :0)+(l2 !=0? l2 ->val :0)+c;
            output ->next = new  ListNode(sum %10);
            output=output ->next;
            c=sum/10;
            l1=(l1 !=NULL ? l1 ->next : NULL);
            l2=(l2 !=NULL ? l2 ->next : NULL);
        }
        if(c==1)
        {
            output ->next = new  ListNode(1);
        }
        return head ->next;

    }
};


text:
#include <iostream>
using namespace std;

class node{
   public:
  int data;
  node*next;
 node(int d){
      data=d;
      next=NULL;
  }
};
 void insertAtTail(node* &head, int data){
     if(head==NULL){
         head= new node(data);
         return;
     }
     node* temp=head;
     while(temp->next!=NULL){
         temp=temp->next;
     }
     temp->next=new node(data);
     return;
 }
 void buildList(node* &head){
     int data;
     cin>>data;
     while(data!=-1){
         insertAtTail(head,data);
         cin>>data;
     }
     head->next->next->next=head;
 }

  void print(node* &head){
     node*temp=head;
     while(temp!=NULL){
         cout<<temp->data<<"-->";
         temp=temp->next;
     }
     cout<<endl;
 }

void breakCycle(node* &head,node* &slow,node* &fast){
    node*p=head;
    slow=head;
    node *next=fast->next;
    slow->next=NULL;
    print(slow);
    for(node *temp=next;temp!=slow;temp=temp->next)
    cout<<temp->data<<"-->";
    cout<<endl;
}

bool detectCycle(node* &head){
    node*slow=head;
    node*fast=head;
    while(fast!=NULL && fast->next!=NULL){
         fast=fast->next->next;
         slow=slow->next;
         if(slow==fast){
             breakCycle(head,slow,fast);
             return true;
         }
    }
    return false;
}

int main() {

   node* head=NULL;
   cout<<"Enter nodes of tree: "<<endl;
   buildList(head);
   if(detectCycle(head)){
       cout<<"cycle was present in the linked list"<<endl;
       cout<<"if we break the cycle, the linked list becomes : "<<endl;
       print(head);
   }
   else{
       cout<<"No cycle was present"<<endl;
   }

 return 0;
}


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

class Node{

    public:
        Node* prev;
        int data;
        Node* next;

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

    ~Node(){
        int value = this->data;
        if(next != NULL){
            delete next;
            next = NULL;
        }
        cout<<"Deleted value is : "<< value << endl;
    }
};

void insertAtHead(Node* &head , Node* &tail , int data){

    if(head == NULL){
        Node* temp = new Node(data);
        head = temp;
    }

    else{
        //new node created
        Node* temp = new Node(data);

        temp->next = head;
        head->prev = temp;
        head = temp;
}

}

void insertAtTail(Node* &head , Node* &tail , int data){

    if(head == NULL){
        Node* temp = new Node(data);
        head = temp;
    }

    else{
        //new node created
        Node* temp = new Node(data);

        tail->next = temp;
        temp->prev = tail;
        tail = temp;
    }

}

void insertAtPosition(Node* &head , Node* &tail , int data , int pos){

    if(pos == 1){
        insertAtHead(head,tail,data);
        return ;
    }

    Node* temp = new Node(data);
    Node* p = head;
    int count = 1;
    while(count < pos){
        p = p->next;
        count++;
    }

    if(temp -> next == NULL){
        insertAtTail(head , tail , data);
        return;
    }

    temp->next = p->next;
    p->next->prev = temp;
    p->next = temp;
    temp->prev = p;
}

void deleteAtPosition(Node* &head , Node* &tail , int pos){

    if(pos == 1){
        Node* temp = head;
        head = head->next;
        temp->next->prev = NULL;
        temp->next = NULL;
        delete temp;
    }

    else
    {
        //deleting any middle node or last node
        Node* curr = head;
        Node* prev = NULL;

        int cnt = 1;
        while(cnt < pos) {
            prev = curr;
            curr = curr -> next;
            cnt++;
        }

        curr -> prev = NULL;
        prev -> next = curr -> next;
        curr -> next = NULL;

        delete curr;
    }
}

void display(Node* &head){

    Node* p = head;
    while(p != NULL){
        cout<<p->data<< " ";
        p = p->next;
    }
    cout<<endl;
}

int main(){

    Node* head = new Node(10);
    Node* tail = head;

    insertAtHead(head , tail , 5);
    display(head);

    insertAtTail(head , tail , 15);
    display(head);

    insertAtPosition(head , tail , 100 , 4);
    display(head);

    deleteAtPosition(head,tail,3);
    display(head);
}


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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
ListNode* addTwoNumbers(ListNode* A, ListNode* B) {

	if(!A) return B;
	if(!B) return A;

	int carry = 0;
	ListNode* head = NULL;
	ListNode* last = head;

	while(A and B){
		int sum = A->val + B->val + carry;
		carry = sum/10;

		ListNode* t = new ListNode(sum%10);

		if(head == NULL) {
			head = t; last = head;
		}
		else {
			last->next = t;
			last = last->next;
		}

		A = A->next;
		B = B->next;
	}

	while(A){
		int sum = A->val + carry;
		carry = sum/10;

		ListNode* t = new ListNode(sum%10);

		last->next = t;
		last = last->next;

		A = A->next;
	}

	while(B){
		int sum = B->val + carry;

		carry = sum/10;

		ListNode* t = new ListNode(sum%10);

		last->next = t;
		last = last->next;

		B = B->next;
	}

	if(carry != 0){
		ListNode* t = new ListNode(carry);
	    last->next = t;
	}

	return head;
}


text:
import java.io.*;
import java.util.*;

class LinkedListNode<T> {
    T data;
    LinkedListNode<T> next;

    public LinkedListNode(T data) {
        this.data = data;
    }
}

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static LinkedListNode<Integer> takeInput() throws IOException {
        LinkedListNode<Integer> head = null, tail = null;

        String[] datas = br.readLine().trim().split("\\s");

        int i = 0;
        while(i < datas.length && !datas[i].equals("-1")) {
            int data = Integer.parseInt(datas[i]);
            LinkedListNode<Integer> newNode = new LinkedListNode<Integer>(data);
            if(head == null) {
                head = newNode;
                tail = newNode;
            }
            else {
                tail.next = newNode;
                tail = newNode;
            }
            i += 1;
        }

        return head;
    }

    public static void print(LinkedListNode<Integer> head){
        while(head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }

        System.out.println();
    }

     public static LinkedListNode<Integer> removeDuplicates(LinkedListNode<Integer> head) {
        if (head == null || head.next == null)
            return head;

        LinkedListNode<Integer> newList= new LinkedListNode<Integer> (head.data), newNode= null, copy= null;
        copy= newList;
        head= head.next;

        while (head != null)
        {
            if (!(newList.data).equals(head.data))
            {
                newNode= new LinkedListNode<Integer> (head.data);
                newList.next= newNode;
                newList= newList.next;
            }
            head= head.next;
        }
        return copy;
	  }

    public static void main(String[] args) throws NumberFormatException, IOException {
        int t = Integer.parseInt(br.readLine().trim());

        while (t > 0) {
            LinkedListNode<Integer> head = takeInput();
            head = removeDuplicates(head);
            print(head);
            t--;
        }
    }
}


text:
/* Question:
    Given two singly linked lists of size N and M,
    write a program to get the point where two linked lists intersect each other.

    Example:
    Input:
    Linked List 1 = 4->1->common
    Linked List 2 = 5->6->1->common
    common = 8->4->5->NULL
    Output: 8
    Explanation:

    4              5
    |              |
    1              6
     \             /
      8   -----  1
       |
       4
       |
      5
      |
      NULL
*/
#include<bits/stdc++.h>

using namespace std;

//Linked List Node
struct Node {
  int data;
  struct Node *next;
  Node(int x) {
    data = x;
    next = NULL;
  }
};

// Function to take Linked List elements as input.

Node* inputList(int size)
{
    if(size==0) return NULL;

    int val;
    cin>> val;

    Node *head = new Node(val);
    Node *tail = head;

    for(int i=0; i<size-1; i++)
    {
        cin>>val;
        tail->next = new Node(val);
        tail = tail->next;
    }

    return head;
}

//Function to find intersection point in Y shaped Linked Lists.

int intersectPoint(Node* head1, Node* head2)
{
    // Your Code Here
    Node* p = head1;
    while(p->next!=NULL)
    {
        p=p->next;

    }
    p->next = head1;
    Node* s = head2;
    Node* f = head2;
    while(f!=NULL && f->next!=NULL)
    {
        f=f->next->next;
        s=s->next;
        if(f==s)
        break;
    }
    if(f==NULL || f->next==NULL)
    return -1;
    s = head2;
    while(s!=f)
    {
        s=s->next;
        f=f->next;
    }
    return s->data;

}

int main()
{
    int n1,n2,n3;

    cout<<"Enter No. of elements in list 1"<<endl;
    cin>>n1;
    cout<<"Enter No. of elements in list 2"<<endl;
    cin>>n2;
    cout<<"Enter No. of elements in the common list"<<endl;
    cin>>n3;

    cout<<"Enter elements for first list"<<endl;
    Node* head1 = inputList(n1);
    cout<<"Enter elements for second list"<<endl;
    Node* head2 = inputList(n2);
    cout<<"Enter elements for the common list"<<endl;
    Node* common = inputList(n3);

    Node* temp = head1;
    while(temp!=NULL && temp->next != NULL)
        temp = temp->next;
    if(temp!=NULL) temp->next = common;

    temp = head2;
    while(temp!=NULL && temp->next != NULL)
        temp = temp->next;
    if(temp!=NULL) temp->next = common;

    cout << "intersection point is: "<<intersectPoint(head1, head2) << endl;
    return 0;
}


text:
kReverse
Send Feedback
Given a singly linked list of integers, reverse the nodes of the linked list 'k' at a time and return its modified list.
 'k' is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of 'k,' then left-out nodes, in the end, should be reversed as well.
Example :
Given this linked list: 1 -> 2 -> 3 -> 4 -> 5

For k = 2, you should return: 2 -> 1 -> 4 -> 3 -> 5

For k = 3, you should return: 3 -> 2 -> 1 -> 4 -> 5
 Note :
No need to print the list, it has already been taken care. Only return the new head to the list.
 Input format :
The first line contains an Integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case or query contains the elements of the singly linked list separated by a single space.

The second line of input contains a single integer depicting the value of 'k'.
 Remember/Consider :
While specifying the list elements for input, -1 indicates the end of the singly linked list and hence, would never be a list element
Output format :
For each test case/query, print the elements of the updated singly linked list.

Output for every test case will be printed in a seperate line.
Constraints :
1 <= t <= 10^2
0 <= M <= 10^5
Where M is the size of the singly linked list.
0 <= k <= M

Time Limit:  1sec
Sample Input 1 :
1
1 2 3 4 5 6 7 8 9 10 -1
4
Sample Output 1 :
4 3 2 1 8 7 6 5 10 9
Sample Input 2 :
2
1 2 3 4 5 -1
0
10 20 30 40 -1
4
Sample Output 2 :
1 2 3 4 5
40 30 20 10
*********************************************
//head is the head of the linked list, n is number of elements to be reversed
// Following is the node structure
/**************
class node{
public:
    int data;
    node * next;
    node(int data){
        this->data=data;
        this->next=NULL;
    }
};
***************/
Node* revelist(Node *head){

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

    Node *prev=head;
    Node *cur=head->next;
    prev->next=NULL;
    while(cur){
        Node *temp=cur->next;
        cur->next=prev;
        prev=cur;
        cur=temp;
    }

    return prev;

}
Node* kReverse(Node*head,int n)
{
    //write your code here
    if(head==NULL)
        return NULL;
    int count=0;

    Node* front=head;
    Node* tail=head;
    Node* newHead;

    for(int i=1;i<n;i++){
        if(tail->next==NULL)
            break;
        else
            tail=tail->next;
    }
    Node *newtail=front;
    Node *temp=tail->next;
    tail->next=NULL;
    newHead=revelist(front);

    Node* ans=kReverse(temp,n);
    newtail->next=ans;
    return newHead;
}

********************

#include <iostream>

class Node
{
public:
	int data;
	Node *next;
	Node(int data)
	{
		this->data = data;
		this->next = NULL;
	}
};

using namespace std;
#include "solution.h"

Node *takeinput()
{
	int data;
	cin >> data;
	Node *head = NULL, *tail = NULL;
	while (data != -1)
	{
		Node *newnode = new Node(data);
		if (head == NULL)
		{
			head = newnode;
			tail = newnode;
		}
		else
		{
			tail->next = newnode;
			tail = newnode;
		}
		cin >> data;
	}
	return head;
}

void print(Node *head)
{
	Node *temp = head;
	while (temp != NULL)
	{
		cout << temp->data << " ";
		temp = temp->next;
	}
	cout << endl;
}

int main()
{
	int t;
	cin >> t;

	while (t--)
	{
		Node *head = takeinput();
		int k;
		cin >> k;
		head = kReverse(head, k);
		print(head);
	}

	return 0;
}


text:
class Node(object):

    def __init__(self, val):
        self.val = val
        self.next = None

class MyLinkedList(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.head = None
        self.size = 0

    def get(self, index):
        """
        Get the value of the index-th node in the linked list. If the index is invalid, return -1.
        :type index: int
        :rtype: int
        """
        if index < 0 or index >= self.size:
            return -1

        if self.head is None:
            return -1

        curr = self.head
        for i in range(index):
            curr = curr.next
        return curr.val

    def addAtHead(self, val):
        """
        Add a node of value val before the first element of the linked list.
        After the insertion, the new node will be the first node of the linked list.
        :type val: int
        :rtype: void
        """
        node = Node(val)
        node.next = self.head
        self.head = node

        self.size += 1

    def addAtTail(self, val):
        """
        Append a node of value val to the last element of the linked list.
        :type val: int
        :rtype: void
        """
        curr = self.head
        if curr is None:
            self.head = Node(val)
        else:
            while curr.next is not None:
                curr = curr.next
            curr.next = Node(val)

        self.size += 1

    def addAtIndex(self, index, val):
        """
        Add a node of value val before the index-th node in the linked list.
        If index equals to the length of linked list, the node will be appended to the end of linked list.
        If index is greater than the length, the node will not be inserted.
        :type index: int
        :type val: int
        :rtype: void
        """
        if index < 0 or index > self.size:
            return

        if index == 0:
            self.addAtHead(val)
        else:
            curr = self.head
            for i in range(index - 1):
                curr = curr.next
            node = Node(val)
            node.next = curr.next
            curr.next = node

            self.size += 1

    def deleteAtIndex(self, index):
        """
        Delete the index-th node in the linked list, if the index is valid.
        :type index: int
        :rtype: void
        """
        if index < 0 or index >= self.size:
            return

        curr = self.head
        if index == 0:
            self.head = curr.next
        else:
            for i in range(index - 1):
                curr = curr.next
            curr.next = curr.next.next

        self.size -= 1


text:
import java.io.*;
import java.util.*;

class LinkedListNode<T> {
    T data;
    LinkedListNode<T> next;

    public LinkedListNode(T data) {
        this.data = data;
    }
}

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static LinkedListNode<Integer> takeInput() throws IOException {
        LinkedListNode<Integer> head = null, tail = null;

        String[] datas = br.readLine().trim().split("\\s");

        int i = 0;
        while(i < datas.length && !datas[i].equals("-1")) {
            int data = Integer.parseInt(datas[i]);
            LinkedListNode<Integer> newNode = new LinkedListNode<Integer>(data);
            if(head == null) {
                head = newNode;
                tail = newNode;
            }
            else {
                tail.next = newNode;
                tail = newNode;
            }
            i += 1;
        }

        return head;
    }

    public static void print(LinkedListNode<Integer> head){
        while(head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }

        System.out.println();
    }

    public static LinkedListNode<Integer> swapNodes(LinkedListNode<Integer> head, int i, int j) {

        if (head == null || i == j)
            return head;

        LinkedListNode<Integer> curr2= head, curr1= head, p1= null, p2= null, temp= null;
        int ci= i, cj= j;

        i= Math.min(ci, cj);
        j= Math.max(ci, cj);
        j-= i;

        while (curr2 != null)
        {
            i--;
            if (i == 0)
            {
                p1= curr2;
                curr1= curr2.next;
            }
            else if (i < 0)
        		j--;

            if (j == 0){
                p2= curr2;
                curr2= curr2.next;
                temp= curr2.next;
                //System.out.println(curr1.data + ", " + curr2.data);
                if (p1 != null)
                	p1.next= curr2;
                else
                    head= curr2;

                p2.next= curr1;
                curr2.next= curr1.next;
                curr1.next= temp;
                break;
            }
            curr2= curr2.next;
        }
        return head;
	  }

    public static void main(String[] args) throws NumberFormatException, IOException {

        int t = Integer.parseInt(br.readLine().trim());

        while (t > 0) {

            LinkedListNode<Integer> head = takeInput();
            String[] i_j = br.readLine().trim().split("\\s");

            int i = Integer.parseInt(i_j[0]);
            int j = Integer.parseInt(i_j[1]);

            LinkedListNode<Integer> newHead = swapNodes(head, i, j);
            print(newHead);

            t -= 1;
        }

    }
}


text:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==NULL && l2==NULL)
            return l1;
        else
        {
            if(l1==NULL) return l2;
            else if(l2==NULL) return l1;
        }

        if(l1->val > l2->val)
        {
            ListNode* l3=l1;
            l1=l2;
            l2=l3;
        }

        ListNode* list=l1;

        while(l2)
        {
            while(l1->next!=NULL && l1->val < l2->val && l1->next->val < l2->val )
           {
            l1=l1->next;
           }
            ListNode* temp1=l2->next;
            l2->next=l1->next;
            l1->next=l2;
            l2=temp1;
        }
        return list;

    }
};