<repo_name>TheShivamMishra/Coding<file_sep>/Practice/bookAllocation.cpp
#include <bits/stdc++.h>
#define ll long long int 
using namespace std;

bool findsol(int a[],int n,int m ,ll ans)
{
    
    int i=0,j=0;
    ll sump=0;//assign the maximum pages
          //that can read which less than equal to ans
   
    while(i<n)
    {
     if(sump+a[i]<=ans)
     {
         sump+=a[i++];
     }else{
         ++j;
         sump=0;
     }
    //No of sudent greater than m to assign all book return false
     if(j>=m)return false;
    }
// at last all check and student equal to  m;
    return true;  
}

// finding ans with binary search
ll binarysearch(int a[],int n,int m,ll end ,ll start)
{
    ll ans=a[n-1];
    while(start<=end)
    {
        ll mid=(start+end)/2;
        if(findsol(a,n,m,mid))
        {
// if mid is valid then assign this to answer
//change the end to mid-1 so minimize the answer till start ==end
            ans=mid;
            end=mid-1;
        }else{
//if mid is not valid then search  between mid+1 and end
            start=mid+1;
        }
       
    }
    return ans;
}

int main() {
    //code
    int t;
    cin>>t;
    while(t--)
    {

       int  n,m;
       ll sum=0;
        cin>>n;
        int a[n];

        for(int i=0;i<n;++i)
        {
            cin>>a[i];
            sum+=a[i];
        }
       
        cin>>m;
       //if no of sudent is greater than book then return -1 as at least one book
       // is allocate every one student
        if(m>n)
        cout<<-1<<endl;
          else if(n==m){
      //if no of student is equal to no of book then return book with  maximum page
            cout<<*max_element(a,a+n)<<endl;
            }
            else{
            cout<<binarysearch(a,n,m,sum,a[0])<<endl;
        }
       
       
    }
    return 0;
}<file_sep>/Practice/sudoku.cpp
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define vi vector<int>
#define vb vector<bool>
#define lli long long int
#define vvi vector<vector<int>>
#define loop(n) for (int i = 0; i < n; i++)
using namespace std;

bool isSafeToPlaceNumber(vector<vector<int>> &board, int r, int c, int num)
{
    // for row
    for (int i = 0; i < board[0].size(); i++)
        if (board[r][i] == num)
            return false;

    // for col
    for (int i = 0; i < board.size(); i++)
        if (board[i][c] == num)
            return false;

    //for each sub box 3x3 Matrix
    int x = (r / 3) * 3;
    int y = (c / 3) * 3;

    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
            if (board[x + i][y + j] == num)
                return false;
    }

    return true;
}

bool sudoku_02(vector<vector<int>> &board, int idx, vector<int> &list)
{
    if (idx == list.size())
        return 1;

    int r = list.at(idx) / 9;
    int c = list.at(idx) % 9;
    int count = 0;
    bool res = false;

    for (int num = 1; num < 10; num++)
    {
        if (isSafeToPlaceNumber(board, r, c, num))
        {
            board[r][c] = num;
            res = sudoku_02(board, idx + 1, list);
            if (res)
                return true;
            board[r][c] = 0;
        }
    }

    return res;
}

void solve()
{
    vvi mat(9, vi(9, 0));
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            cin >> mat[i][j];
    // cout << "hi" << endl;
    vi list;
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
        {
            if (mat[i][j] == 0)
                list.push_back(i * 9 + j);
            // else
            // {
            //     int mask = 1 << mat[i][j];
            //     row[i] ^= mask;
            //     col[j] ^= mask;
            //     submat[i / 3][j / 3] ^= mask;
            // }
        }

    if (sudoku_02(mat, 0, list))
    {
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                cout << mat[i][j] << " ";
        cout << endl;
    }
    else
        cout << "-1" << endl;
}

int main()
{
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    // cout.tie(NULL);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}<file_sep>/SegmentTrees/l001.cpp
#include "bits/stdc++.h"
#define lli long long int
#define vi vector<int>
#define vb vector<bool>
#define vvi vector<vector<int>>
#define loop(n) for (int i = 0; i < n; i++)
using namespace std;

// building segment tree using segtree array;

void makeST(vi &arr, vi &segtree, int l, int r, int idx)
{
    if (l == r)
    {
        segtree[idx] = 1;
        return;
    }
    int mid = (l + r) / 2;
    makeST(arr, segtree, l, mid, 2 * idx + 1);
    makeST(arr, segtree, mid + 1, r, 2 * idx + 2);
    int count = 0;
    unordered_set<int> map;
    for (int i = l; i <= r; i++)
    {
        if (map.find(arr[i]) == map.end())
            count++;
        map.insert(arr[i]);
    }
    segtree[idx] = count;
    // cout<<segtree[idx]<<endl;
}

void createSegmentTree(vi &arr, vi &segtree, int n)
{
    int size = 0;
    int x = (int)ceil(log(n));  // height of a compelete binary tree i.e a segmetntree;
    size = 2 * (pow(2, x)) - 1; // size of the segment tree : because their will be exacty n leaves and (n-1){internal nodes in a completer binary tree};
                                // hence total nodes will be n + n-1
    segtree.assign(size, 0);
    makeST(arr, segtree, 0, n - 1, 0);
}

int getQuery(vi &segtree, int l, int r, int low, int high, int pos) // using overlaping structre to get query result;
{
    cout<<low<<" "<<high<<endl;
    if (low >= l && high <= r)
        return segtree[pos]; // total overlap;

    if (high < l || low > r)
        return 0; //no overlap;

    int mid = (low + high) / 2;
    return getQuery(segtree, l, r, low, mid, 2 * pos + 1) + getQuery(segtree, l, r, mid + 1, high, 2 * pos + 1);
}

void solve()
{
    int n;
    cin >> n;
    vi arr(n, 0);
    loop(n) cin >> arr[i];
    int size = 0;
    int x = (int)ceil(log2(n)); // height of a compelete binary tree i.e a segmetntree;
    size = 2 * (pow(2, x)) - 1;
    // cout<<size<<endl;
    vi segtree(size, 0);
    makeST(arr, segtree, 0, n - 1, 0);
    // loop(size) cout << segtree[i] << " ";
    int queries;
    cin >> queries;
    while (queries--)
    {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        cout << getQuery(segtree, l, r, 0, n - 1, 0) << "\n";
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
    return 0;
}
<file_sep>/Graph/l002_directedGraph.java
import java.util.ArrayList;
import java.util.LinkedList;

public class l002_directedGraph {

    public static void main(String[] args) {
        solve();
    }

    static int N = 8;
    static ArrayList<Integer> graph[];

    public static void display() {
        for (int i = 0; i < graph.length; i++) {
            System.out.print(i + "->");
            for (Integer e : graph[i]) {
                System.out.print("(" + e + ") ");
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void constructGraph() {
        graph = new ArrayList[N];
        for (int i = 0; i < graph.length; i++)
            graph[i] = new ArrayList<Integer>();

        graph[7].add(5);
        graph[7].add(6);
        graph[5].add(4);
        graph[5].add(2);
        graph[6].add(4);
        graph[6].add(3);
        graph[2].add(1);
        graph[3].add(1);
        graph[1].add(0);

        display();

    }

    // Topological sort for directed
    // Graph===================================================
    public static void topologicalSort_(int src, boolean[] vis, ArrayList<Integer> ans) { // dfs
        vis[src] = true;

        for (Integer e : graph[src])
            if (!vis[e])
                topologicalSort_(e, vis, ans);

        ans.add(src);
    }

    public static void topologicalSort() {
        ArrayList<Integer> ans = new ArrayList<>();
        boolean vis[] = new boolean[N];

        for (int i = 0; i < N; i++) // calling the topologicalsort_ for all the gcc of graph.
            if (!vis[i])
                topologicalSort_(i, vis, ans);

        for (int i = ans.size() - 1; i >= 0; i--) // printing the stack in revrse order.
            System.out.print(i + " ");
    }

    // Kahns Algo For used for topological sort and cycle founding in
    // graph=====================
    public static void KahnsAlgo() {

        int[] indegree = new int[N];

        for (int i = 0; i < N; i++) { // creating indegree array.
            for (Integer e : graph[i])
                indegree[e]++;
        }

        LinkedList<Integer> que = new LinkedList<>();
        for (int i = 0; i < N; i++) // adding all the 0 indgree in queue.
            if (indegree[i] == 0)
                que.addLast(i);

        ArrayList<Integer> ans = new ArrayList<>();
        while (que.size() != 0) {
            int size = que.size();
            while (size-- > 0) {
                int rvtx = que.removeFirst();
                ans.add(rvtx);

                for (int e : graph[rvtx]) {
                    if (--indegree[e] == 0)
                        que.addLast(e);
                }

            }

        }

        if (ans.size() != N)
            System.out.println("Cycle");
        else
            System.out.println(ans);

    }

    // topological sort using dfs marking the array 1 for current path as visiting
    // to find cycle.
    public static boolean topologicalSort_(int src, int[] vis, ArrayList<Integer> ans) {
        if (vis[src] == 1)// visited vertex in my path.
            return true;
        if (vis[src] == 2) // already viseited vertex but not by my path.
            return false;

        vis[src] = 1;
        boolean res = false;
        for (int e : graph[src]) {
            res = res || topologicalSort_(e, vis, ans);
        }

        vis[src] = 2;
        ans.add(src);
        return res;
    }

    public static void topologicalSortCycle() {
        int[] vis = new int[N];
        ArrayList<Integer> ans = new ArrayList<>();

        boolean res = false;
        for (int i = 0; i < N && !res; i++)
            if (vis[i] == 0)
                res = res || topologicalSort_(i, vis, ans);

        if (!res) {
            System.out.println(ans);
        } else
            System.out.println("Cycle :" + ans);
    }

    // Scc of a graph using kosa raju algo.======================
    public static void dfs_scc(int src, ArrayList<Integer>[] ngraph, boolena[] vis, ArrayList<Integer> ans) {
        vis[src] = true;
        for (int ele : ngraph[src]) {
            if (!vis[ele])
                dfs_scc(e, ngraph, vis, ans);
        }
    }

    public static void KosaRajuAlgo() {
        boolean vis[] = new boolean[N];
        ArrayList<Integer> ans = new ArrayList<>(); // getting topo Order in which we have to travel;
        for (int i = 0; i < N; i++)
            if (!vis[i])
                topologicalSort_(i, vis, ans);

        ArrayList<Integer>[] ngraph = new ArrayList[N]; // creation of a new graph;
        for (int i = 0; i < N; i++)
            ngraph[i] = new ArrayList<>();

        for (int i = 0; i < N; i++) { // inversion of old graph and storing it into ngraph;
            for (int ele : graph[i]) {
                ngraph[ele].add(i);
            }
        }

        vis = new boolean[N];
        count = 0;
        for (int i = ans.size() - 1; i >= 0; i--) // running again dfs but now on topo Order obtianed;
        {
            if (!vis[ans.get(i)]) {
                ArrayList<Integer> ans_ = new ArrayList<>();
                dfs_scc(ans.get(i), ngraph, vis, ans_);
                System.out.println(ans_);
                count++;
            }
        }

        System.out.println(count);

    }

    public static void solve() {
        constructGraph();
        // topologicalSort();
        // KahnsAlgo();
        topologicalSortCycle();
    }
}<file_sep>/Tree/question.java
public class question {

    
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    // Leetcode: 863.=======================================================
    public boolean rootToNodePath_(TreeNode root, int data, ArrayList<TreeNode> path) {
        if (root == null)
            return false;
        if (root.val == data) {
            path.add(root);
            return true;
        }

        boolean res = rootToNodePath_(root.left, data, path) || rootToNodePath_(root.right, data, path);
        if (res)
            path.add(root);
        return res;
    }

    public void kDown(TreeNode root, int level, TreeNode blockNode, List<Integer> ans) {
        if (root == null || root == blockNode)
            return;

        if (level == 0) {
            ans.add(root.val);
            return;
        }

        kDown(root.left, level - 1, blockNode, ans);
        kDown(root.right, level - 1, blockNode, ans);

    }

    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        ArrayList<TreeNode> path = new ArrayList<>();
        rootToNodePath_(root, target.val, path);

        TreeNode blockNode = null;
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < path.size(); i++) {
            if (K - i < 0)
                break;
            kDown(path.get(i), K - i, blockNode, ans);
            blockNode = path.get(i);
        }
        return ans;
    }

    // Leetcode: 112.=======================================================
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null)
            return false;
        if (root.left == null && root.right == null && sum - root.val == 0)
            return true;

        boolean res = false;
        res = res || hasPathSum(root.left, sum - root.val);
        res = res || hasPathSum(root.right, sum - root.val);
        return res;
    }

    // Leetcode: 113.========================================================

    public void pathSum(TreeNode root, int sum, List<List<Integer>> res, List<Integer> smallAns) {
        if (root == null)
            return;
        if (root.left == null && root.right == null && sum - root.val == 0) {
            List<Integer> base = new ArrayList<>(smallAns);// res.push_back(smallAns); res.back().push_back(root.val);
            base.add(root.val);
            res.add(base);
            return;
        }

        smallAns.add(root.val);
        pathSum(root.left, sum - root.val, res, smallAns);
        pathSum(root.right, sum - root.val, res, smallAns);
        smallAns.remove(smallAns.size() - 1);
    }

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null)
            return new ArrayList<>();

        List<List<Integer>> res = new ArrayList<>();
        List<Integer> smallAns = new ArrayList<>();
        pathSum(root, sum, res, smallAns);
        return res;
    }

    // geeks:
    // https://www.geeksforgeeks.org/find-maximum-path-sum-two-leaves-binary-tree/

    public static int maxPathSum(Node root) {
        max_leafToLeafSum = (int) -1e8;
        leafToLeaf(root);
        return max_leafToLeafSum;
    }

    public static int leafToLeaf(Node node) {
        if (node == null)
            return 0;

        int leftNodeToLeafSum = leafToLeaf(node.left);
        int rightNodeToLeafSum = leafToLeaf(node.right);

        if (node.left != null && node.right != null) {
            max_leafToLeafSum = Math.max(max_leafToLeafSum, leftNodeToLeafSum + rightNodeToLeafSum + node.data);
            return Math.max(leftNodeToLeafSum, rightNodeToLeafSum) + node.data;
        }

        return (node.left == null ? rightNodeToLeafSum : leftNodeToLeafSum) + node.data;
    }

    // Leetcode 124.========================================================

    int max_nodeToNodeSum = (int) -1e8;

    public int maxPathSum(TreeNode root) {
        maxPathSum_(root);
        return max_nodeToNodeSum;
    }

    public int maxPathSum_(TreeNode node) {
        if (node == null)
            return 0;

        int leftNodeToNodeSum = maxPathSum_(node.left);
        int rightNodeToNodeSum = maxPathSum_(node.right);

        int max_ = Math.max(leftNodeToNodeSum, rightNodeToNodeSum) + node.val;
        max_nodeToNodeSum = Math.max(Math.max(max_nodeToNodeSum, node.val),
                Math.max(leftNodeToNodeSum + node.val + rightNodeToNodeSum, max_));

        return Math.max(max_, node.val);
    }

    // Leetcode 987.====================================================

    static int leftMinValue = 0;
    static int rightMaxValue = 0;

    public static void width(TreeNode node, int lev) {
        if (node == null)
            return;

        leftMinValue = Math.min(leftMinValue, lev);
        rightMaxValue = Math.max(rightMaxValue, lev);

        width(node.left, lev - 1);
        width(node.right, lev + 1);
    }

    public static class pairVO implements Comparable<pairVO> {
        TreeNode node; // actual Node
        int vl = 0; // vertical Level

        public pairVO(TreeNode node, int vl) {
            this.node = node;
            this.vl = vl;
        }

        @override
        public int compareTo(pairVO o) { // for c++: bool opeartor < ( pairvo const & o) const{
            if (this.vl == o.vl)
                return this.node.val - o.node.val; // in c++: replace '-' with '>'
            return this.vl - o.vl; // default behaviour of que // in c++: replace '-' with '>'
        }
    }

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null)
            return ans;

        width(root, 0);
        int n = rightMaxValue - leftMinValue + 1;
        for (int i = 0; i < n; i++)
            ans.add(new ArrayList<>());

        PriorityQueue<pairVO> pque = new PriorityQueue<>();
        PriorityQueue<pairVO> cque = new PriorityQueue<>();

        pque.add(new pairVO(root, -leftMinValue));

        while (pque.size() != 0) {
            int size = pque.size();
            while (size-- > 0) {
                pairVO rpair = pque.poll();
                ans.get(rpair.vl).add(rpair.node.val);

                if (rpair.node.left != null)
                    cque.add(new pairVO(rpair.node.left, rpair.vl - 1));
                if (rpair.node.right != null)
                    cque.add(new pairVO(rpair.node.right, rpair.vl + 1));
            }

            PriorityQueue<pairVO> temp = pque;
            pque = cque;
            cque = temp;
        }
    }

}<file_sep>/Recursion/l002.cpp
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>

using namespace std;

void display2D(vector<vector<int>> &board)
{
    for (auto ele : board)
    {
        for (auto item : ele)
            cout << item << " ";
        cout << endl;
    }
}

// Nqueen Optimized using 4 Arrays

vector<bool> rowA(4, false);
vector<bool> colA(4, false);
vector<bool> diagA(4, false);
vector<bool> adiagA(4, false);

int Nqueen2D_01(int n, int m, int idx, int tnq, string ans)
{
    if (tnq == 0)
    {
        cout << ans << endl;
        return 1;
    }
    int count = 0;
    for (int i = idx; i < n * m; i++)
    {
        int x = i / m;
        int y = i % m;
        if (!rowA[x] && !colA[y] && !diagA[x - y + (m - 1)] && !adiagA[x + y])
        {
            rowA[x] = true;
            colA[y] = true;
            diagA[x - y + (m - 1)] = true;
            adiagA[x + y] = true;

            count += Nqueen2D_01(n, m, i + 1, tnq - 1, ans + "(" + to_string(x) + "," + to_string(y) + ")");

            rowA[x] = false;
            colA[y] = false;
            diagA[x - y + (m - 1)] = false;
            adiagA[x + y] = false;
        }
    }

    return count;
}

// Nqueens using bits ====================================

int rowA_ = 0;
int colA_ = 0;
int diagA_ = 0;
int adiagA_ = 0;

int Nqueen2D_02(int n, int m, int idx, int tnq, string ans)
{
    if (tnq == 0)
    {
        cout << ans << endl;
        return 1;
    }
    int count = 0;
    for (int i = idx; i < n * m; i++)
    {
        int x = i / m;
        int y = i % m;
        if (!(rowA_ & (1 << x)) && !(colA_ & (1 << y)) && !(diagA_ & (1 << (x - y + (m - 1)))) && !(adiagA_ & (1 << (x + y))))
        {
            rowA_ ^= (1 << x);
            colA_ ^= (1 << y);
            diagA_ ^= (1 << (x - y + (m - 1)));
            adiagA_ ^= (1 << (x + y));

            count += Nqueen2D_02(n, m, i + 1, tnq - 1, ans + "(" + to_string(x) + "," + to_string(y) + ")");

            rowA_ ^= (1 << x);
            colA_ ^= (1 << y);
            diagA_ ^= (1 << (x - y + (m - 1)));
            adiagA_ ^= (1 << (x + y));
        }
    }

    return count;
}

// Nqueen more optimized by placing one queen per row
//i.e one queen can sit at any place in that row
// next queen will have next row;
int Nqueen2D_03(int n, int m, int r, int tnq, string ans)
{
    if (r == n || tnq == 0)
    {
        if (tnq == 0)
        {
            cout << ans << endl;
            return 1;
        }
        return 0;
    }
    int count = 0;
    for (int i = r; i < m; i++)
    {
        int x = r;
        int y = 0;
        if (!(rowA_ & (1 << x)) && !(colA_ & (1 << y)) && !(diagA_ & (1 << (x - y + (m - 1)))) && !(adiagA_ & (1 << (x + y))))
        {
            rowA_ ^= (1 << x);
            colA_ ^= (1 << y);
            diagA_ ^= (1 << (x - y + (m - 1)));
            adiagA_ ^= (1 << (x + y));

            count += Nqueen2D_03(n, m, r + 1, tnq - 1, ans + "(" + to_string(x) + "," + to_string(y) + ")");

            rowA_ ^= (1 << x);
            colA_ ^= (1 << y);
            diagA_ ^= (1 << (x - y + (m - 1)));
            adiagA_ ^= (1 << (x + y));
        }
    }

    return count;
}

void NqueenSet()
{
    int n = 4;
    int m = 4;
    rowA.resize(n, false);
    colA.resize(m, false);
    diagA.resize(n + m - 1, false);
    adiagA.resize(n + m - 1, false);
    // cout << Nqueen2D_01(n, m, 0, n, "") << endl;
    // cout << Nqueen2D_02(n, m, 0, n, "") << endl;
    cout << Nqueen2D_03(n, m, 0, n, "") << endl;
}

// suduko set===================================

bool isSafeToPlaceNumber(vector<vector<int>> &board, int r, int c, int num)
{
    // for row
    for (int i = 0; i < board[0].size(); i++)
        if (board[r][i] == num)
            return false;

    // for col
    for (int i = 0; i < board.size(); i++)
        if (board[i][c] == num)
            return false;

    //for each sub box 3x3 Matrix
    int x = (r / 3) * 3;
    int y = (c / 3) * 3;

    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
            if (board[x + i][y + j] == num)
                return false;
    }

    return true;
}

int suduko_01(vector<vector<int>> &board, int idx)
{
    if (idx == 81)
    {
        display2D(board);
        return 1;
    }

    int r = idx / 9;
    int c = idx % 9;
    int count = 0;

    if (board[r][c] == 0)
    {
        for (int num = 1; num < 10; num++)
        {
            if (isSafeToPlaceNumber(board, r, c, num))
            {
                board[r][c] = num;
                count += suduko_01(board, idx + 1);
                board[r][c] = 0;
            }
        }
    }
    else
    {
        count += suduko_01(board, idx + 1);
    }

    return count;
}

// suduko 2 in this we use a list in which all the zeros of the board are present
// and just call on them hence we save the calls;
int suduko_02(vector<vector<int>> &board, int idx, vector<int> &list)
{
    if (idx == list.size())
    {
        cout << "===========================" << endl;
        display2D(board);
        return 1;
    }

    int r = list.at(idx) / 9;
    int c = list.at(idx) % 9;
    int count = 0;

    for (int num = 1; num < 10; num++)
    {
        if (isSafeToPlaceNumber(board, r, c, num))
        {
            board[r][c] = num;
            count += suduko_02(board, idx + 1, list);
            board[r][c] = 0;
        }
    }

    return count;
}

//suduko 3 More optimization of isSafeToPlaceNumber by using bits.
vector<int> row(10, 0);
vector<int> col(10, 0);
vector<vector<int>> mat(4, vector<int>(4, 0));

int suduko_03(vector<vector<int>> &board, int idx, vector<int> &list)
{
    if (idx == list.size())
    {
        cout << "===========================" << endl;
        display2D(board);
        return 1;
    }

    int r = list.at(idx) / 9;
    int c = list.at(idx) % 9;
    int count = 0;

    for (int num = 1; num < 10; num++)
    {
        int mask = 1 << num;
        if ((row[r] & mask) == 0 && (col[c] & mask) == 0 && (mat[r / 3][c / 3] & mask) == 0)
        {
            board[r][c] = num;
            row[r] ^= mask;
            col[c] ^= mask;
            mat[r / 3][c / 3] ^= mask;
            count += suduko_03(board, idx + 1, list);
            board[r][c] = 0;
            row[r] ^= mask;
            col[c] ^= mask;
            mat[r / 3][c / 3] ^= mask;
        }
    }

    return count;
}

void sudukoSet()
{
    vector<vector<int>> board = {{3, 0, 6, 5, 0, 8, 4, 0, 0},
                                 {5, 2, 0, 0, 0, 0, 0, 0, 0},
                                 {0, 8, 7, 0, 0, 0, 0, 3, 1},
                                 {0, 0, 3, 0, 1, 0, 0, 8, 0},
                                 {9, 0, 0, 8, 6, 3, 0, 0, 5},
                                 {0, 5, 0, 0, 9, 0, 6, 0, 0},
                                 {1, 3, 0, 0, 0, 0, 2, 5, 0},
                                 {0, 0, 0, 0, 0, 0, 0, 7, 4},
                                 {0, 0, 5, 2, 0, 6, 3, 0, 0}};

    // cout << suduko_01(board, 0) << endl;
    // for suduko 2 ==================================
    vector<int> list;
    // for (int i = 0; i < 9; i++)
    // {
    //     for (int j = 0; j < 9; j++)
    //         if (board[i][j] == 0)
    //             list.push_back(i * 9 + j);
    // }
    // cout << suduko_02(board, 0,list) << endl;
    // for suduko 3 ==================================
    // seting the bits;
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            if (board[i][j] == 0)
                list.push_back(i * 9 + j);
            else
            {
                int mask = 1 << board[i][j];
                row[i] ^= mask;
                col[j] ^= mask;
                mat[i / 3][j / 3] ^= mask;
            }
        }
    }
    cout << suduko_03(board, 0, list) << endl;

    display2D(board);
}

// Word Break ===========================================
unordered_set<string> map;
int wordBreak_01(string word, string ans)
{
    if (word.length() == 0)
    {
        cout << ans << endl;
        return 1;
    }

    int count = 0;
    for (int i = 1; i <= word.length(); i++)
    {
        string temp = word.substr(0, i);
        if (map.find(temp) != map.end())
        {
            count += wordBreak_01(word.substr(i), ans + temp + " ");
        }
    }

    return count;
}

void wordBreak()
{
    vector<string> words = {"mobile", "samsung", "ilike", "sam", "sung",
                            "man", "mango", "icecream", "and",
                            "go", "i", "like", "ice", "cream"};
    for (string word : words)
        map.insert(word);
    string word = "ilikesamsungandmango";
    cout << wordBreak_01(word, "");
}

// Crypto code =====================================================

string str1 = "send";
string str2 = "more";
string str3 = "money";
vector<int> Charmap(26, 0);
int numused = 0;

int strToNum(string str)
{
    int res = 0;
    for (int i = 0; i < str.length(); i++)
    {
        int temp = Charmap[str[i] - 'a'];
        res = res * 10 + temp;
    }
    return res;
}

// recursive function which check for crypto code correctness
int crypto_(string str, int idx)
{
    if (idx == str.length())
    {
        int num1 = strToNum(str1);
        int num2 = strToNum(str2);
        int num3 = strToNum(str3);

        if (num1 + num2 == num3)
            return 1;
        return 0;
    }

    int count = 0;
    for (int num = 0; num <= 9; num++)
    {
        int mask = 1 << num;
        if ((numused & mask) == 0)
        {
            numused ^= mask;
            Charmap[str[idx] - 'a'] = num;
            count += crypto_(str, idx + 1);
            numused ^= mask;
            Charmap[str[idx] - 'a'] = num;
        }
    }

    return count;
}

void crypto()
{
    string str = str1 + str2 + str3;
    //======= first generate unique char =======
    int freq = 0;
    for (int i = 0; i < str.length(); i++)
    {
        int mask = (1 << (str[i] - 'a'));
        freq |= mask;
    }

    // then generate no from freq ============
    str = "";
    for (int i = 0; i < 26; i++)
    {
        int mask = (1 << i);
        if ((freq & mask) != 0)
        {
            str += (char)(i + 'a');
        }
    }

    // cout << str << endl;

    //====== then calling the recursive function to get unique no for all unique char in the str
    cout << crypto_(str, 0) << endl;
}

// Cross Word puzzel placing horizontal and vertical ============

//crossword.========================================================
vector<vector<char>> board{{'+', '-', '+', '+', '+', '+', '+', '+', '+', '+'},
                           {'+', '-', '+', '+', '+', '+', '+', '+', '+', '+'},
                           {'+', '-', '-', '-', '-', '-', '-', '-', '+', '+'},
                           {'+', '-', '+', '+', '+', '+', '+', '+', '+', '+'},
                           {'+', '-', '+', '+', '+', '+', '+', '+', '+', '+'},
                           {'+', '-', '-', '-', '-', '-', '-', '+', '+', '+'},
                           {'+', '-', '+', '+', '+', '-', '+', '+', '+', '+'},
                           {'+', '+', '+', '+', '+', '-', '+', '+', '+', '+'},
                           {'+', '+', '+', '+', '+', '-', '+', '+', '+', '+'},
                           {'+', '+', '+', '+', '+', '+', '+', '+', '+', '+'}};
vector<string> words = {"agra", "norway", "england", "gwalior"};

bool canPlaceWordH(int r, int c, string &word)
{
    if (c == 0 && word.length() < board[0].size())
    {
        if (board[r][c + word.length()] != '+')
            return false;
    }
    else if ((c + word.length()) == board[0].size() && word.length() != board[0].size())
    {
        if (board[r][c - 1] != '+')
            return false;
    }
    else
    {
        if (((c - 1) >= 0 && board[r][c - 1] != '+') || ((c + word.length()) < board[0].size() && board[r][c + word.length()] != '+'))
            return false;
    }

    for (int i = 0; i < word.length(); i++)
    {
        if ((c + i) < board[0].size() && board[r][c + i] != '-' && board[r][c + i] != word[i])
        {
            return false;
        }
    }
    return true;
}

vector<bool> placeWordH(int r, int c, string &word)
{
    vector<bool> mark(word.length(), false);
    for (int i = 0; i < word.length(); i++)
    {
        if (board[r][c + i] == '-')
        {
            mark[i] = true;
            board[r][c + i] = word[i];
        }
    }
    return mark;
}

void unPlaceWordH(int r, int c, string &word, vector<bool> &mark)
{
    for (int i = 0; i < word.length(); i++)
    {
        if (mark[i])
            board[r][c + i] = '-';
    }
}

bool canPlaceWordV(int r, int c, string &word)
{
    if (r == 0 && r + word.length() < board.size())
    {
        if (board[r + word.length()][c] != '+')
            return false;
    }
    else if ((r + word.length()) == board.size() && word.length() != board.size())
    {
        if (board[r - 1][c] != '+')
            return false;
    }
    else
    {
        if (((r - 1) >= 0 && board[r - 1][c] != '+') || ((r + word.length()) < board.size() && board[r + word.length()][c] != '+'))
            return false;
    }

    for (int i = 0; i < word.length(); i++)
    {
        if ((r + i) < board.size() && board[r + i][c] != '-' && board[r + i][c] != word[i])
        {
            return false;
        }
    }
    return true;
}

vector<bool> placeWordV(int r, int c, string &word)
{
    vector<bool> mark(word.length(), false);
    for (int i = 0; i < word.length(); i++)
    {
        if (board[r + i][c] == '-')
        {
            mark[i] = true;
            board[r + i][c] = word[i];
        }
    }
    return mark;
}

void unPlaceWordV(int r, int c, string &word, vector<bool> &mark)
{
    for (int i = 0; i < word.length(); i++)
    {
        if (mark[i])
            board[r + i][c] = '-';
    }
}

bool crossWord_(int idx)
{
    if (idx == words.size())
    {
        for (vector<char> &ar : board)
        {
            for (char ch : ar)
                cout << ch << " ";
            cout << endl;
        }
        return true;
    }

    string word = words[idx];
    bool res = false;
    for (int i = 0; i < board.size(); i++)
    {
        for (int j = 0; j < board[0].size(); j++)
        {
            if (board[i][j] == '-' || board[i][j] == word[0])
            {
                if (canPlaceWordH(i, j, word))
                {
                    vector<bool> mark = placeWordH(i, j, word);
                    res = res || crossWord_(idx + 1);
                    unPlaceWordH(i, j, word, mark);
                }

                if (canPlaceWordV(i, j, word))
                {
                    vector<bool> mark = placeWordV(i, j, word);
                    res = res || crossWord_(idx + 1);
                    unPlaceWordV(i, j, word, mark);
                }
            }
        }
    }

    return res;
}

void crossWord()
{
    cout << crossWord_(0) << endl;
}

int main(int argc, char const *argv[])
{
    // NqueenSet();
    // sudukoSet();
    // wordBreak();
    // crypto();
    crossWord();
    return 0;
}
<file_sep>/MyStack/l001.cpp
#include <iostream>
#include <vector>

using namespace std;

class Mystack
{
    int sz = 0;
    int *arr;
    int N = 1000;
    int tos = -1;

public:
    Mystack()
    {
        arr = new int[N];
    }

    Mystack(int sz)
    {
        N = sz;
        arr = new int[sz];
    }

    int size()
    {
        return this->sz;
    }

    bool empty()
    {
        return this->sz == 0;
    }

    void push(int val)
    {
        if (sz > N)
            return;
        this->tos++;
        this->arr[tos] = val;
        sz++;
    }

    int top()
    {
        if (sz < 1 || sz > N)
            return -1;
        return this->arr[tos];
    }

    void pop()
    {
        if (sz < 1)
            return;
        int rv = this->arr[tos];
        this->tos--;
        this->sz--;
    }
};

void solve()
{
    Mystack st(10);
    for (int i = 1; i <= 10; i++)
        st.push(i * 10);
    for (int i = 0; i < 10; i++)
    {
        cout << st.top() << endl;
        st.pop();
    }
}

int main()
{
    solve();
    return 0;
}<file_sep>/Tree/l001.java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

import org.graalvm.compiler.phases.common.RemoveValueProxyPhase;

public class l001 {

    public static void main(String[] args) {
        solve();
    }

    public static class Node {
        int data;
        Node left = null; // Node* left=nullptr;
        Node right = null; // Node* right=nullptr;

        Node(int data) {
            this.data = data;
        }

        Node() {
        }
    }

    static int idx = 0;

    public static Node constructTree(int[] arr) {
        if (idx >= arr.length || arr[idx] == -1) {
            idx++;
            return null;
        }

        Node node = new Node(arr[idx++]); // Node* node=new Node(arr[idx++]);
        node.left = constructTree(arr);
        node.right = constructTree(arr);

        return node;
    }

    public static void display(Node node) {
        if (node == null)
            return;

        String str = "";
        str += ((node.left != null) ? node.left.data : ".");
        str += " <- " + node.data + " -> ";
        str += ((node.right != null) ? node.right.data : ".");
        System.out.println(str);

        display(node.left);
        display(node.right);

    }

    // Basic.================================================================

    public static int size(Node node) {
        if (node == null)
            return 0;
        return (size(node.left) + size(node.right) + 1);
    }

    public static int height(Node node) {
        if (node == null)
            return -1; // return -1, height w.r.t edge, return 0, height w.r.t node.
        return Math.max(height(node.left), height(node.right)) + 1;
    }

    public static int Maximum(Node node) {
        if (node == null)
            return (int) -1e8; // java: Integer.MIN_VALUE, c++: INT_MIN;
        return Math.max(Math.max(Maximum(node.left), Maximum(node.right)), node.data); // max(leftSubtree,rightSubtree,myself);
    }

    public static int Minimum(Node node) {
        if (node == null)
            return (int) 1e8; // java: Integer.MAX_VALUE, c++: INT_MAX;
        return Math.min(Math.min(Minimum(node.left), Minimum(node.right)), node.data);
    }

    public static int Minimum_02(Node node) {
        int min_ = node.data;

        if (node.left != null)
            min_ = Math.min(min_, Minimum_02(node.left));
        if (node.right != null)
            min_ = Math.min(min_, Minimum_02(node.right));

        return min_;
    }

    public static boolean find(Node node, int data) {
        if (node == null)
            return false;

        if (node.data == data)
            return true;
        return find(node.left, data) || find(node.right, data);
    }

    // Traversal.============================================================

    public static void preOrder(Node node) {
        if (node == null)
            return;

        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

    public static void inOrder(Node node) {
        if (node == null)
            return;

        inOrder(node.left);
        System.out.print(node.data + " ");
        inOrder(node.right);
    }

    public static void postOrder(Node node) {
        if (node == null)
            return;

        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.data + " ");
    }

    // node to root path ==========================================================

    public static boolean rootToNodePath_(Node root, int data, ArrayList<Node> path) {
        if (root == null)
            return false;
        if (root.data == data) {
            path.add(root);
            return true;
        }

        boolean res = rootToNodePath_(root.left, data, path) || rootToNodePath_(root.right, data, path);
        if (res)
            path.add(root);
        return res;
    }

    public static ArrayList<Node> nodeToRoot_path_02(Node node, int val) {
        if (node == null)
            return null;

        if (node.data == val) {
            ArrayList<Node> base = new ArrayList<>();
            base.add(node);
            return base;
        }

        ArrayList<Node> left = nodeToRoot_path_02(node.left, val);

        if (left != null) {
            left.add(node);
            return left;
        }
        ArrayList<Node> right = nodeToRoot_path_02(node.right, val);

        if (right != null) {
            right.add(node);
            return right;
        }

        return null;
    }

    // LCA ========================================================
    public Node lowestCommonAncestor(Node root, int p, int q) {
        ArrayList<Node> path1 = new ArrayList<>();
        ArrayList<Node> path2 = new ArrayList<>();

        rootToNodePath_(root, p, path1);
        rootToNodePath_(root, q, path2);

        Node prev = null;
        int i = path1.size() - 1;
        int j = path2.size() - 1;

        while (i >= 0 && j >= 0) {
            if (path1.get(i).data != path2.get(j).data)
                break;

            prev = path1.get(i);
            i--;
            j--;
        }

        return prev;
    }

    static Node LCANode = null;

    public static boolean lowestCommonAncestor_02(Node root, int p, int q) {
        if (root == null)
            return false;

        boolean selfDone = false;
        if (root.data == p || root.data == q) {
            selfDone = true;
        }

        boolean leftDone = lowestCommonAncestor_02(root.left, p, q);
        if (LCANode != null)
            return true;

        boolean rightDone = lowestCommonAncestor_02(root.right, p, q);
        if (LCANode != null)
            return true;

        if ((selfDone && leftDone) || (selfDone && rightDone) || (leftDone && rightDone))
            LCANode = root;

        return selfDone || leftDone || rightDone;
    }

    // all Nodes k down form a given Node in a BT
    // =========================================
    public static void kDown(Node root, int level, Node blockNode) {
        if (root == null || root == blockNode)
            return;

        if (level == 0) {
            System.out.print(root.data + " ");
            return;
        }

        kDown(root.left, level - 1, blockNode);
        kDown(root.right, level - 1, blockNode);

    }

    public static void allNodeKAway(Node root, int target, int K) {
        ArrayList<Node> path = new ArrayList<>();
        rootToNodePath_(root, target, path);

        Node blockNode = null;
        for (int i = 0; i < path.size(); i++) {
            if (K - i < 0)
                break;
            kDown(path.get(i), K - i, blockNode);
            blockNode = path.get(i);
        }
    }

    public static int allNodeKAway_02_(Node root, int target, int K) {
        if (root == null)
            return -1;

        if (root.data == target) {
            kDown(root, K, null);
            return 1;
        }

        int leftdistance = allNodeKAway_02_(root.left, target, K);
        if (leftdistance != -1) {
            if (K - leftdistance >= 0)
                kDown(root, K - leftdistance, root.left);
            return leftdistance + 1;
        }

        int rightdistance = allNodeKAway_02_(root.right, target, K);
        if (rightdistance != -1) {
            if (K - rightdistance >= 0)
                kDown(root, K - rightdistance, root.right);
            return rightdistance + 1;
        }

        return -1;

    }

    public static void kDown(Node root, int level) {
        if (root == null)
            return;

        if (level == 0) {
            System.out.print(root.data + " ");
            return;
        }

        kDown(root.left, level - 1);
        kDown(root.right, level - 1);

    }

    // Diameter of a Tree : total no of nodes b/w the two end nodes of the longest
    // path in the tree.
    public static int diameter_01(Node root) {
        if (root == null) // O(n2) soltuion becuase needed lh,rh for every root;
            return 0;
        int lh = height(root.left);
        int rh = height(root.right);
        int ld = diameter_01(root.left);
        int rd = diameter_01(root.right);
        int myDia = lh + rh + 2;
        return Math.max(Math.max(ld, rd), myDia);
    }

    public static class diaPair {

        int dia = 0;
        int hei = 0;

        diaPair(int dia, int hei) {
            this.dia = dia;
            this.hei = hei;
        }
    }

    public static diaPair diameter_02(Node node) {
        if (node == null)
            return new diaPair(0, -1);

        diaPair lr = diameter_02(node.left);
        diaPair rr = diameter_02(node.right);

        diaPair myRes = new diaPair(0, -1);
        myRes.dia = Math.max(Math.max(lr.dia, rr.dia), lr.hei + rr.hei + 2);
        myRes.hei = Math.max(lr.hei, rr.hei) + 1;
        return myRes;
    }

    public static int diameter = 0;

    public static int diameter_03(Node node) {
        if (node == null)
            return -1;

        int lh = diameter_03(node.left);
        int rh = diameter_03(node.right);

        diameter = Math.max(diameter, lh + rh + 2);
        return Math.max(lh, rh) + 1;
    }

    public static class pairVO {
        Node node;
        int vl;

        pairVO(Node node, int vl) {
            this.node = node;
            this.vl = vl;
        }
    }

    // View=====================================================================

    public static void leftView(Node node) {
        LinkedList<Node> que = new LinkedList<>(); // addLast and removeFirst.
        que.addLast(node);
        while (que.size() != 0) {
            int size = que.size();
            System.out.print(que.getFirst().data + " ");
            while (size-- > 0) {
                Node rnode = que.removeFirst();
                if (rnode.left != null)
                    que.addLast(rnode.left);
                if (rnode.right != null)
                    que.addLast(rnode.right);
            }
        }
        System.out.println();
    }

    public static void rightView(Node node) {
        LinkedList<Node> que = new LinkedList<>(); // addLast and removeFirst.
        que.addLast(node);
        while (que.size() != 0) {
            int size = que.size();
            Node prev = null;
            while (size-- > 0) {
                Node rnode = que.removeFirst();
                if (rnode.left != null)
                    que.addLast(rnode.left);
                if (rnode.right != null)
                    que.addLast(rnode.right);
                prev = rnode;
            }
            System.out.print(prev.data + " ");
        }
        System.out.println();
    }

    static int leftMinValue = 0;
    static int rightMaxValue = 0;

    public static void width(Node node, int lev) {
        if (node == null)
            return;

        leftMinValue = Math.min(leftMinValue, lev);
        rightMaxValue = Math.max(rightMaxValue, lev);

        width(node.left, lev - 1);
        width(node.right, lev + 1);
    }

    public static class pairVO {
        Node node; // actual Node
        int vl = 0; // vertical Level

        public pairVO(Node node, int vl) {
            this.node = node;
            this.vl = vl;
        }
    }

    public static void verticalOrder(Node node) {
        width(node, 0);
        int n = rightMaxValue - leftMinValue + 1;
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>(); // vector<vector<int>> (n,vector<int>());
        for (int i = 0; i < n; i++)
            ans.add(new ArrayList<>());

        LinkedList<pairVO> que = new LinkedList<>();
        que.addLast(new pairVO(node, -leftMinValue));

        while (que.size() != 0) {
            int size = que.size();
            while (size-- > 0) {
                pairVO rpair = que.removeFirst();
                ans.get(rpair.vl).add(rpair.node.data);
                if (rpair.node.left != null)
                    que.addLast(new pairVO(rpair.node.left, rpair.vl - 1));
                if (rpair.node.right != null)
                    que.addLast(new pairVO(rpair.node.right, rpair.vl + 1));
            }
        }

        for (ArrayList<Integer> ar : ans)
            System.out.println(ar);
        System.out.println();
    }

    public static void verticalOrderSum(Node node) {
        width(node, 0);
        int[] ans = new int[rightMaxValue - leftMinValue + 1];

        LinkedList<pairVO> que = new LinkedList<>();
        que.addLast(new pairVO(node, -leftMinValue));

        while (que.size() != 0) {
            int size = que.size();
            while (size-- > 0) {
                pairVO rpair = que.removeFirst();
                ans[rpair.vl] += rpair.node.data;
                if (rpair.node.left != null)
                    que.addLast(new pairVO(rpair.node.left, rpair.vl - 1));
                if (rpair.node.right != null)
                    que.addLast(new pairVO(rpair.node.right, rpair.vl + 1));
            }
        }

        for (int ele : ans)
            System.out.println(ele);
        System.out.println();
    }

    public static void bottomView(Node node) {
        width(node, 0);
        int[] ans = new int[rightMaxValue - leftMinValue + 1];

        LinkedList<pairVO> que = new LinkedList<>();
        que.addLast(new pairVO(node, -leftMinValue));

        while (que.size() != 0) {
            int size = que.size();
            while (size-- > 0) {
                pairVO rpair = que.removeFirst();
                ans[rpair.vl] = rpair.node.data;
                if (rpair.node.left != null)
                    que.addLast(new pairVO(rpair.node.left, rpair.vl - 1));
                if (rpair.node.right != null)
                    que.addLast(new pairVO(rpair.node.right, rpair.vl + 1));
            }
        }

        for (int ele : ans)
            System.out.println(ele);
        System.out.println();
    }

    public static void topView(Node node) {
        width(node, 0);
        int[] ans = new int[rightMaxValue - leftMinValue + 1];
        Arrays.fill(ans, (int) -1e8);

        LinkedList<pairVO> que = new LinkedList<>();
        que.addLast(new pairVO(node, -leftMinValue));

        while (que.size() != 0) {
            int size = que.size();
            while (size-- > 0) {
                pairVO rpair = que.removeFirst();

                if (ans[rpair.vl] == (int) -1e8)
                    ans[rpair.vl] = rpair.node.data;

                if (rpair.node.left != null)
                    que.addLast(new pairVO(rpair.node.left, rpair.vl - 1));
                if (rpair.node.right != null)
                    que.addLast(new pairVO(rpair.node.right, rpair.vl + 1));
            }
        }

        for (int ele : ans)
            System.out.println(ele);
        System.out.println();
    }

    static int leftDMinValue = 0;

    public static void widthDiagonal(Node node, int lev) {
        if (node == null)
            return;

        leftMinValue = Math.min(leftMinValue, lev);

        width(node.left, lev - 1);
        width(node.right, lev + 0);
    }

    public static void diagonalOrder(Node node) {
        widthDiagonal(node, 0);
        int n = -leftDMinValue + 1;
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>(); // vector<vector<int>> (n,vector<int>());
        for (int i = 0; i < n; i++)
            ans.add(new ArrayList<>());

        LinkedList<pairVO> que = new LinkedList<>();
        que.addLast(new pairVO(node, -leftMinValue));

        while (que.size() != 0) {
            int size = que.size();
            while (size-- > 0) {
                pairVO rpair = que.removeFirst();
                ans.get(rpair.vl).add(rpair.node.data);
                if (rpair.node.left != null)
                    que.addLast(new pairVO(rpair.node.left, rpair.vl - 1));
                if (rpair.node.right != null)
                    que.addLast(new pairVO(rpair.node.right, rpair.vl + 0));
            }
        }

        for (ArrayList<Integer> ar : ans)
            System.out.println(ar);
        System.out.println();
    }

    public static void diagonalSum(Node node) {
        widthDiagonal(node, 0);
        int n = -leftDMinValue + 1;
        int[] ans = new int[n];

        LinkedList<pairVO> que = new LinkedList<>();
        que.addLast(new pairVO(node, -leftMinValue));

        while (que.size() != 0) {
            int size = que.size();
            while (size-- > 0) {
                pairVO rpair = que.removeFirst();
                ans[rpair.vl] += rpair.node.data;
                if (rpair.node.left != null)
                    que.addLast(new pairVO(rpair.node.left, rpair.vl - 1));
                if (rpair.node.right != null)
                    que.addLast(new pairVO(rpair.node.right, rpair.vl + 0));
            }
        }

        for (int ele : ans)
            System.out.println(ele);
        System.out.println();
    }

    static Node DLLhead = null;
    static Node DLLprev = null;

    public static void DLL(Node node) {
        if (node == null)
            return;

        DLL(node.left);

        if (DLLhead == null) {
            DLLhead = node;
        } else {
            DLLprev.right = node;
            node.left = DLLprev;
        }
        DLLprev = node;

        DLL(node.right);

    }

    public static class allSolution {
        int height = 0;
        int size = 0;
        boolean find = false;

        Node pred = null;
        Node succ = null;
        Node prev = null;
    }

    public static void allSol(Node node, int data, int level, allSolution pair) {
        if (node == null)
            return;
        pair.size++;
        pair.height = Math.max(pair.height, level);
        pair.find = pair.find || node.data == data;

        if (node.data == data && pair.pred == null)
            pair.pred = prev;
        if (pair.prev != null && pair.prev.data == data && pair.succ == null)
            pair.succ = node;
        pair.prev = node;

        allSol(node.left, data, level + 1, pair);
        allSol(node.right, data, level + 1, pair);
    }

    // Iterative travesal of the tree using a class
    // ==================================

    // =================================================================

    public static class tpair { // traversalPair
        Node node = null;
        boolean selfDone = false;
        boolean leftDone = false;
        boolean rightDone = false;

        tpair(Node node, boolean selfDone, boolean leftDone, boolean rightDone) {
            this.node = node;
            this.leftDone = leftDone;
            this.selfDone = selfDone;
            this.rightDone = rightDone;
        }
    }

    public static void ItrTraversalOfTree(Node node) {
        Stack<tpair> st = new Stack<>();
        st.push(new tpair(node, false, false, false));

        while (st.size() != 0) {
            if (st.peek().selfDone == false) {
                st.peek().selfDone = true;
                System.out.print(st.peek().node.data + " ");
            } else if (st.peek().leftDone == false) {
                st.peek().leftDone = true;
                if (st.peek().node.left != null) {
                    st.push(new tpair(st.peek().node.left, false, false, false));
                }
            } else if (st.peek().rightDone == false) {
                st.peek().rightDone = true;
                if (st.peek().node.right != null) {
                    st.push(new tpair(st.peek().node.right, false, false, false));
                }
            } else {
                st.pop();
            }
        }
    }

    public static class tpair_ { // traversalPair
        Node node = null;
        boolean selfDone = false;
        boolean leftDone = false;
        boolean rightDone = false;

        int ld = -1;
        int rd = -1;
        int sd = -1;
        boolean isleft = false;

        tpair_(Node node, boolean selfDone, boolean leftDone, boolean rightDone, boolean isleft) {
            this.node = node;
            this.leftDone = leftDone;
            this.selfDone = selfDone;
            this.rightDone = rightDone;
            this.isleft = isleft;
        }
    }

    public static void ItrHeightOfTree(Node node) {
        Stack<tpair_> st = new Stack<>();
        st.push(new tpair_(node, false, false, false, false));

        tpair_ rpair = null;
        while (st.size() != 0) {
            if (st.peek().leftDone == false) {
                st.peek().leftDone = true;
                if (st.peek().node.left != null) {
                    st.push(new tpair_(st.peek().node.left, false, false, false, true));
                }
            } else if (st.peek().rightDone == false) {
                st.peek().rightDone = true;
                if (st.peek().node.right != null) {
                    st.push(new tpair_(st.peek().node.right, false, false, false, false));
                }
            } else if (st.peek().selfDone == false) {
                st.peek().selfDone = true;
                st.peek().sd = Math.max(st.peek().ld, st.peek().rd) + 1;
            } else {
                rpair = st.pop();
                if (st.size() != 0) {
                    if (st.peek().isleft)
                        st.peek().ld = rpair.sd;
                    else
                        st.peek().rd = rpair.sd;
                }
            }
        }

        System.out.println(rpair.sd);
    }

    public static Node rightMost_of_LeftNode(Node lnode, Node curr) {
        while (lnode.right != null && lnode.right != curr) {
            lnode = lnode.right;
        }
        return lnode;
    }

    public static void morrisInOrder(Node node) {
        Node curr = node;
        while (curr != null) {
            if (curr.left == null) {
                System.out.print(curr.data + " ");
                curr = curr.right;
            } else {
                Node leftNode = curr.left;
                Node rightMost = rightMost_of_LeftNode(leftNode, curr);
                if (rightMost.right == null) { // thread create
                    rightMost.right = curr;
                    curr = curr.left;
                } else { // thread break
                    rightMost.right = null;
                    System.out.print(curr.data + " ");
                    curr = curr.right;
                }
            }
        }
        System.out.println();
    }

    public static void morrisPreOrder(Node node) {
        Node curr = node;
        while (curr != null) {
            if (curr.left == null) {
                System.out.print(curr.data + " ");
                curr = curr.right;
            } else {
                Node leftNode = curr.left;
                Node rightMost = rightMost_of_LeftNode(leftNode, curr);
                if (rightMost.right == null) { // thread create
                    rightMost.right = curr;
                    System.out.print(curr.data + " ");
                    curr = curr.left;
                } else { // thread break
                    rightMost.right = null;
                    curr = curr.right;
                }
            }
        }
        System.out.println();
    }

    // psi = preStartIndex, pei=preEndIndex, isi=inStartIndex, iei=inEndIndex
    public static Node ConstructFromPreAndIn(int[] pre, int psi, int pei, int[] in, int isi, int iei) {
        if (psi > pei || isi > iei)
            return null;

        Node node = new Node(pre[psi]);

        int idx = isi;
        while (in[idx] != pre[psi]) {
            idx++;
        }
        int tnel = idx - isi; // total no of elements between isi and idx

        node.left = ConstructFromPreAndIn(pre, psi + 1, psi + tnel, in, isi, idx - 1);
        node.right = ConstructFromPreAndIn(pre, psi + tnel + 1, pei, in, idx + 1, iei);

        return node;
    }

    public static Node ConstructFromPreAndIn(int[] pre, int[] in) {
        return ConstructFromPreAndIn(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }

    // psi = postStartIndex, pei=postEndIndex, isi=inStartIndex, iei=inEndIndex
    public static Node ConstructFromPostAndIn(int[] post, int psi, int pei, int[] in, int isi, int iei) {
        if (psi > pei || isi > iei)
            return null;

        Node node = new Node(pre[pei]);

        int idx = isi;
        while (in[idx] != pre[psi]) {
            idx++;
        }
        int tnel = idx - isi; // total no of elements between isi and idx

        node.left = ConstructFromPostAndIn(post, psi, psi + tnel - 1, in, isi, idx - 1);
        node.right = ConstructFromPostAndIn(post, psi + tnel, pei - 1, in, idx + 1, iei);

        return node;
    }

    public static Node ConstructFromPostAndIn(int[] post, int[] in) {
        return ConstructFromPostAndIn(post, 0, post.length - 1, in, 0, in.length - 1);
    }

    // psi = preStartIndex, pei=preEndIndex, ppsi=postStartIndex, ppei=postEndIndex
    public static Node ConstructFromPreAndPost(int[] post, int psi, int pei, int[] in, int ppsi, int ppei) {
        if (psi > pei || ppsi > ppei)
            return null;

        Node node = new Node(pre[psi]);

        int idx = ppsi;
        while (post[idx] != pre[psi + 1]) {
            idx++;
        }

        int tnel = idx - isi + 1; // total no of elements between isi and idx

        node.left = ConstructFromPreAndPost(post, psi + 1, psi + tnel, in, ppsi, idx);
        node.right = ConstructFromPreAndPost(post, psi + tnel + 1, pei, in, idx + 1, iei - 1);

        return node;
    }

    public static Node ConstructFromPreAndPost(int[] pre, int[] post) {
        return ConstructFromPreAndPost(pre, 0, pre.length - 1, post, 0, post.length - 1);
    }

    public static void set2(Node node) {
        DLL(node);
        while (DLLhead != null) {
            System.out.print(DLLhead.data + " ");
            DLLhead = DLLhead.right;
        }
    }

    public static void view(Node node) {
        // leftView(node);
        // rightView(node);
        // verticalOrder(node);
        // bottomView(node);
        // topView(node);

    }

    public static void levelOrder(Node node) {
        // levelOrder_00(node);
        // levelOrder_01(node);
        // levelOrder_02(node);
        // levelOrder_03(node);
    }

    public static void solve() {
        // int[] arr = { 10, 20, 40, 50, 80, -1, -1, 90, -1, -1, 30, 60, 100, -1, -1,
        // -1, 70, 110, -1, -1, 120, -1,
        // -1 };

        int[] arr = { 11, 6, 4, -1, 5, -1, -1, 8, -1, 10, -1, -1, 19, 17, -1, -1, 43, 31, -1, -1, 49, -1, -1 };
        // int[] arr = { 10, 20 };
        Node root = constructTree(arr);

        display(root);
        // ArrayList<Node> ans = nodeToRoot_path(root, 60);
        // System.out.println(ans);
        view(root);
    }

}<file_sep>/LinkedList/question.java
public class ListNode {

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }

    }

    // Leetcode 876: getMid
    public ListNode getMidNode(ListNode node) {
        if (node == null || node.next == null)
            return node;
        ListNode slow = node;
        ListNode fast = node;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // Leetcode 206 : reverseOfLL
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null)
            return head;

        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode forw = curr.next;

            curr.next = prev;
            prev = curr;
            curr = forw;
        }

        return prev;
    }

    // Class Question: reverse Data.
    public void reverseListData(ListNode head) {
        if (head == null || head.next == null)
            return;

        ListNode curr = head;
        ListNode midNode = getMidNode(curr);

        ListNode nhead = midNode.next;
        midNode.next = null;

        nhead = reverseList(nhead);
        ListNode curr1 = nhead;
        while (curr != null && curr1 != null) {

            int temp = curr.val;
            curr.val = curr1.val;
            curr1.val = temp;

            curr = curr.next;
            curr1 = curr1.next;
        }

        nhead = reverseList(nhead);
        midNode.next = nhead;
    }

    // IN this the middel node is by index wise;
    public ListNode getMidNode2(ListNode node) {
        if (node == null || node.next == null)
            return node;
        ListNode slow = node;
        ListNode fast = node;

        while (fast != null && fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // Leetcode 234: palindrome

    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null)
            return true;

        ListNode curr = head;
        ListNode midNode = getMidNode2(curr);

        ListNode nhead = midNode.next;
        midNode.next = null;

        nhead = reverseList(nhead);
        ListNode curr1 = nhead;
        while (curr != null && curr1 != null) {
            if (curr.val != curr1.val)
                return false;

            curr = curr.next;
            curr1 = curr1.next;
        }

        nhead = reverseList(nhead);
        midNode.next = nhead;

        return true;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (n == 0 || head == null)
            return head;
        if (n == 1 && head.next == null)
            return null;

        ListNode slow = head, fast = head;
        while (n-- > 0) {
            fast = fast.next;
            // if(fast==null && n > 0) return null; // if n is greater than one;
        }

        if (fast == null)
            return slow.next;

        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        ListNode forw = slow.next;
        slow.next = slow.next.next;
        forw.next = null;
        return head;
    }

    public void reorderList(ListNode head) {
        if (head == null || head.next == null)
            return;

        ListNode curr1 = head;
        ListNode midNode = getMidNode2(curr1);

        ListNode nhead = midNode.next;
        midNode.next = null;

        nhead = reverseList(nhead);
        ListNode curr2 = nhead;
        while (curr1 != null && curr2 != null) {
            ListNode forw1 = curr1.next;
            ListNode forw2 = curr2.next;

            curr1.next = curr2;
            curr2.next = forw1;

            curr1 = forw1;
            curr2 = forw2;
        }
    }

    // Leetcode 21: merge Two LL.

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null)
            return l1 == null ? l2 : l1;

        ListNode head = new ListNode(-1);
        ListNode prev = head;

        ListNode curr1 = l1;
        ListNode curr2 = l2;

        while (curr1 != null && curr2 != null) {
            if (curr1.val <= curr2.val) {
                prev.next = curr1;
                prev = curr1;
                curr1 = curr1.next;
            } else {
                prev.next = curr2;
                prev = curr2;
                curr2 = curr2.next;
            }
        }

        if (curr1 != null) {
            prev.next = curr1;
        }

        if (curr2 != null) {
            prev.next = curr2;
        }

        return head.next;
    }
    
    // mergining two linked list using recurson 
    Node mergeTwoLists(Node l1, Node l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        }

        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }

    }

    // Leetcode 328:
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null)
            return head;

        ListNode curr1 = head;
        ListNode nhead = head.next;
        ListNode curr2 = head.next;

        while (curr1.next != null && curr2.next != null) {
            curr1.next = curr2.next;
            curr1 = curr2.next;

            curr2.next = curr1.next;
            curr2 = curr1.next;
        }

        curr1.next = nhead;
        return head;
    }

    // leetcode 41:

    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null)
            return false;

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast)
                return true;
        }

        return false;
    }

    // Leetcode 142: detectCyclePoint
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null)
            return head;

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast)
                break;
        }

        if (slow != fast)
            return head;

        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }

    // LeetCode 25: reverse K nodes in group=====================
    ListNode oh = null;
    ListNode ot = null;

    ListNode th = null;
    ListNode tt = null;

    public void addFirstNode(ListNode node) {
        if (th == null) {
            th = node;
            tt = node;
        } else {
            node.next = th;
            th = node;
        }
    }

    public int len(ListNode node) {
        int l = 0;
        while (node != null) {
            l++;
            node = node.next;
        }
        return l;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null || k == 0 || k == 1)
            return head;

        int len = len(head);
        if (len < k)
            return head;

        ListNode curr = head;
        while (curr != null) {
            int tk = k;

            while (tk-- > 0) {
                ListNode forw = curr.next;

                curr.next = null;
                addFirstNode(curr);

                curr = forw;
            }

            len -= k;

            if (ot == null) {
                oh = th;
                ot = tt;
            } else {
                ot.next = th;
                ot = tt;
            }

            th = null;
            tt = null;

            if (len < k) {
                ot.next = curr;
                curr = null;
            }
        }

        return oh;
    }

    public ListNode reverseKGroup_02(ListNode head, int k) {
        if (head == null || head.next == null)
            return head;

        int len = len(head);

        if (len < k)
            return head;

        ListNode nhead = null;
        ListNode ntail = head;

        while (head != null) {
            int temp = k;
            ListNode ttail = null;
            ListNode rev = null;

            if (len >= k) {
                while (head != null && temp != 0) {
                    if (ttail == null) {
                        ttail = head;
                    }

                    ListNode forw = head.next;

                    head.next = rev;

                    rev = head;
                    head = forw;

                    temp--;
                }
                len -= k;

                if (nhead == null) {
                    nhead = rev;
                } else {
                    ntail.next = rev;
                    ntail = ttail;
                }
            } else {
                ntail.next = head;
                break;
            }

        }

        return nhead;

    }

    // Leetcode 92==============================================
    // ListNode th = null;
    // ListNode tt = null;

    // public void addFirstNode(ListNode node) {
    // if (th == null) {
    // th = node;
    // tt = node;
    // } else {
    // node.next = th;
    // th = node;
    // }
    // }

    public ListNode reverseBetween(ListNode node, int m, int n) {
        if (node.next == null || m == n)
            return node;

        int idx = 1;

        ListNode curr = node;
        ListNode prev = null;
        ListNode nhead = node;

        while (curr != null) {
            while (idx >= m && idx <= n) {
                ListNode forw = curr.next;
                curr.next = null;
                addFirstNode(curr);

                curr = forw;
                idx++;
            }

            if (tt != null) {
                tt.next = curr;
                if (prev != null)
                    prev.next = th;
                else
                    nhead = th;
                break;
            }

            prev = curr;
            curr = curr.next;
            idx++;
        }

        return nhead;
    }
}<file_sep>/Dp/l001.cpp
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <unordered_map>
#define lli long long int
#define vi vector<int>
#define vvi vector<vector<int>>
using namespace std;

void display(vector<int> &dp)
{
    for (int ele : dp)
        cout << ele << " ";
    cout << endl;
}

void display2D(vector<vector<int>> &dp)
{
    for (vector<int> &ar : dp)
    {
        for (int ele : ar)
            cout << ele << " ";
        cout << endl;
    }
    cout << endl;
}

// Fibonacci =====================================================
//memoizatio
int fibo(int n, vector<int> &dp)
{
    if (n <= 1)
        return dp[n] = n;
    if (dp[n] != 0)
        return dp[n];
    return dp[n] = fibo(n - 1, dp) + fibo(n - 2, dp);
}

//tabulation
int fiboDp(int N, vector<int> &dp)
{

    for (int n = 0; n <= N; n++)
    {
        if (n <= 1)
        {
            dp[n] = n;
            continue;
        }
        dp[n] = dp[n - 1] + dp[n - 2]; //fibo(n - 1, dp) + fibo(n - 2, dp);
    }
    return dp[N];
}

void set1()
{
    int n = 6;
    vi dp(n + 1, 0);
    cout << fibo(6, dp) << endl;
    cout << fiboDp(6, dp) << endl;
    display(dp);
}

//MazePathSeries.==============================================

int mazePathHV(int sr, int sc, int er, int ec, vector<vector<int>> &dp)
{
    if (sr == er && sc == ec)
    {
        return dp[sr][sc] = 1;
    }

    if (dp[sr][sc] != 0)
        return dp[sr][sc];

    int count = 0;
    if (sr + 1 <= er)
        count += mazePathHV(sr + 1, sc, er, ec, dp);

    if (sc + 1 <= ec)
        count += mazePathHV(sr, sc + 1, er, ec, dp);

    if (sr + 1 <= er && sc + 1 <= ec)
        count += mazePathHV(sr + 1, sc + 1, er, ec, dp);

    return dp[sr][sc] = count;
}

int mazePathHV_DP(int sr, int sc, int er, int ec, vector<vector<int>> &dp)
{

    for (sr = er; sr >= 0; sr--)
    {
        for (sc = ec; sc >= 0; sc--)
        {
            if (sr == er && sc == ec)
            {
                dp[sr][sc] = 1;
                continue;
            }

            int count = 0;
            if (sr + 1 <= er)
                count += dp[sr + 1][sc]; //mazePathHV(sr + 1, sc, er, ec, dp);

            if (sc + 1 <= ec)
                count += dp[sr][sc + 1]; //mazePathHV(sr, sc + 1, er, ec, dp);

            if (sr + 1 <= er && sc + 1 <= ec)
                count += dp[sr + 1][sc + 1]; //mazePathHV(sr + 1, sc + 1, er, ec, dp);

            dp[sr][sc] = count;
        }
    }
    return dp[0][0];
}

int mazePathMulti(int sr, int sc, int er, int ec, vector<vector<int>> &dp)
{
    if (sr == er && sc == ec)
    {
        return dp[sr][sc] = 1;
    }

    if (dp[sr][sc] != 0)
        return dp[sr][sc];

    int count = 0;
    for (int jump = 1; sr + jump <= er; jump++)
        count += mazePathMulti(sr + jump, sc, er, ec, dp);

    for (int jump = 1; sc + jump <= ec; jump++)
        count += mazePathMulti(sr, sc + jump, er, ec, dp);

    for (int jump = 1; sr + jump <= er && sc + jump <= ec; jump++)
        count += mazePathMulti(sr + jump, sc + jump, er, ec, dp);

    return dp[sr][sc] = count;
}

int mazePathMulti_DP(int sr, int sc, int er, int ec, vector<vector<int>> &dp)
{

    for (sr = er; sr >= 0; sr--)
    {
        for (sc = ec; sc >= 0; sc--)
        {
            if (sr == er && sc == ec)
            {
                dp[sr][sc] = 1;
                continue;
            }

            int count = 0;
            for (int jump = 1; sr + jump <= er; jump++)
                count += dp[sr + jump][sc]; //mazePathMulti(sr + jump, sc, er, ec, dp);

            for (int jump = 1; sc + jump <= ec; jump++)
                count += dp[sr][sc + jump]; //mazePathMulti(sr, sc + jump, er, ec, dp);

            for (int jump = 1; sr + jump <= er && sc + jump <= ec; jump++)
                count += dp[sr + jump][sc + jump]; //mazePathMulti(sr + jump, sc + jump, er, ec, dp);

            dp[sr][sc] = count;
        }
    }

    return dp[0][0];
}

int boardPath(int sp, int ep, vector<int> &dp)
{
    if (sp == ep)
    {
        return dp[sp] = 1;
    }

    if (dp[sp] != 0)
        return dp[sp];

    int count = 0;
    for (int dice = 1; sp + dice <= ep && dice <= 6; dice++)
        count += boardPath(sp + dice, ep, dp);

    return dp[sp] = count;
}

int boardPathDP(int sp, int ep, vector<int> &dp)
{

    for (sp = ep; sp >= 0; sp--)
    {
        if (sp == ep)
        {
            dp[sp] = 1;
            continue;
        }

        int count = 0;
        for (int dice = 1; sp + dice <= ep && dice <= 6; dice++)
            count += dp[sp + dice]; //boardPath(sp + dice, ep, dp);
        dp[sp] = count;
    }

    return dp[0];
}

int boardPath_best(int sp, int ep)
{
    list<int> ll;
    for (sp = ep; sp >= 0; sp--)
    {
        if (sp > ep - 2)
        {
            ll.push_front(1);
            continue;
        }

        if (ll.size() <= 6)
            ll.push_front(2 * ll.front());
        else
        {
            ll.push_front(2 * ll.front() - ll.back());
            ll.pop_back();
        }
    }

    return ll.front();
}

int boardPathWithDiceArrayDP(int sp, int ep, vector<int> &dp, vector<int> &diceArray)
{

    for (sp = ep; sp >= 0; sp--)
    {
        if (sp == ep)
        {
            dp[sp] = 1;
            continue;
        }

        int count = 0;
        for (int dice = 0; sp + diceArray[dice] <= ep && dice < diceArray.size(); dice++)
            count += dp[sp + diceArray[dice]]; //boardPath(sp + dice, ep, dp);
        dp[sp] = count;
    }

    return dp[0];
}

//Leetcode 70.=================================================================================

int climbStairs_01(int n, vector<int> &dp)
{
    if (n <= 1)
    {
        return dp[n] = 1;
    }

    if (dp[n] != 0)
        return dp[n];

    int ans = climbStairs_01(n - 1, dp) + climbStairs_01(n - 2, dp);
    return dp[n] = ans;
}

int climbStairs_DP(int n, vector<int> &dp)
{
    int N = n;
    for (n = 0; n <= N; n++)
    {

        if (n <= 1)
        {
            dp[n] = 1;
            continue;
        }

        int ans = dp[n - 1] + dp[n - 2]; //climbStairs_01(n - 1, dp) + climbStairs_01(n - 2, dp);
        dp[n] = ans;
    }
    return dp[N];
}

int climbStairs_btr(int n)
{
    int a = 1;
    int b = 1;
    int sum = 1;
    for (int i = 2; i <= n; i++)
    {
        sum = a + b;
        a = b;
        b = sum;
    }
    return sum;
}

int climbStairs(int n)
{
    vector<int> dp(n + 1, 0);
    // return climbStairs_01(n, dp);
    // return climbStairs_DP(n,dp);
    return climbStairs_btr(n);
}

int minCostClimbingStairs(int n, vector<int> &dp, vector<int> &cost)
{
    if (n <= 1)
    {
        return dp[n] = cost[n];
    }

    if (dp[n] != 0)
        return dp[n];

    int ans = min(minCostClimbingStairs(n - 1, dp, cost),
                  minCostClimbingStairs(n - 2, dp, cost));
    return dp[n] = ans + cost[n];
}

int minCostClimbingStairsDP(int n, vector<int> &dp, vector<int> &cost)
{
    int N = n;
    for (int n = 0; n <= N; n++)
    {
        if (n <= 1)
        {
            dp[n] = cost[n];
            continue;
        }

        int ans = min(dp[n - 1], dp[n - 2]);
        dp[n] = ans + cost[n];
    }
    return dp[N];
}

int minCostClimbingStairs(vector<int> &cost)
{
    int n = cost.size();

    cost.push_back(0);
    vector<int> dp(n + 1, 0);

    // return minCostClimbingStairs(n, dp, cost);
    return minCostClimbingStairsDP(n, dp, cost);
}

void pathSet()
{
    // int n = 3, m = 3;
    // vector<vector<int>> dp(n, vector<int>(m, 0));
    // cout << mazePathHV(0, 0, n - 1, m - 1, dp) << endl;
    // cout << mazePathHV_DP(0, 0, n - 1, m - 1, dp) << endl;
    // cout << mazePathMulti(0, 0, n - 1, m - 1, dp) << endl;
    // cout << mazePathMulti(0, 0, n - 1, m - 1, dp) << endl;

    // int sp = 0, ep = 10;
    // vector<int> dp(ep + 1, 0);
    // vector<int> diceArray{1, 2, 3, 4, 5, 6};
    // cout << boardPathDP(sp, ep, dp) << endl;
    // cout << boardPathWithDiceArrayDP(sp, ep, dp, diceArray) << endl;
    // cout << boardPath_best(sp, ep);

    // vector<vector<int>> grid = {{1, 3, 1, 5},
    //                             {2, 2, 4, 1},
    //                             {5, 0, 2, 3},
    //                             {0, 6, 1, 2}};
    // int n = grid.size(), m = grid[0].size();
    // vector<vector<int>> dp(n, vector<int>(m, 0));

    // int maxCoin = 0;
    // for (int i = 0; i < n; i++)
    // {
    //     maxCoin = max(maxCoin, goldMin(i, 0, grid, dp));
    // }
    // maxCoin = goldMin_DP(grid, dp);
    // cout << maxCoin << endl;

    // count_of_ways(7, 3);

    // display(dp);
    // display2D(dp);
}

// friends pairing problme gfg ==================================================
int friends_pairing_problem(int n, vi &dp)
{

    if (n <= 1)
        return 1;
    if (!dp[n])
        return dp[n];
    int single = friends_pairing_problem(n - 1, dp);
    int pairUp = friends_pairing_problem(n - 2, dp) * (n - 1);
    return dp[n] = single + pairUp;
}

int friends_pairing_problem_DP(int n, vector<int> &dp)
{
    int N = n;
    for (int n = 0; n <= N; n++)
    {
        if (n <= 1)
        {
            dp[n] = 1;
            continue;
        }

        int single = dp[n - 1];           //friends_pairing_problem(n - 1, dp);
        int pairUp = dp[n - 2] * (n - 1); //friends_pairing_problem(n - 2, dp) * (n - 1);

        dp[n] = (single + pairUp);
    }
    return dp[N];
}

void set2()
{
    int n = 10;
    vector<int> dp(n + 1, 0);
    // cout << friends_pairing_problem(n, dp) << endl;
    cout << friends_pairing_problem_DP(n, dp) << endl;

    display(dp);
}

// Leetcode 64 minpath sum ===================================
int minPathSum(int sr, int sc, vector<vector<int>> &grid, vector<vector<int>> &dp)
{
    if (sr == grid.size() - 1 && sc == grid[0].size() - 1)
    {
        return dp[sr][sc] = grid[sr][sc];
    }

    if (dp[sr][sc] != 0)
        return dp[sr][sc];

    int minCost = 1e8;
    if (sr + 1 < grid.size())
        minCost = min(minCost, minPathSum(sr + 1, sc, grid, dp));
    if (sc + 1 < grid[0].size())
        minCost = min(minCost, minPathSum(sr, sc + 1, grid, dp));

    return dp[sr][sc] = minCost + grid[sr][sc];
}

int minPathSum_DP(int sr, int sc, vector<vector<int>> &grid, vector<vector<int>> &dp)
{

    for (sr = grid.size() - 1; sr >= 0; sr--)
    {
        for (sc = grid[0].size() - 1; sc >= 0; sc--)
        {

            if (sr == grid.size() - 1 && sc == grid[0].size() - 1)
            {
                dp[sr][sc] = grid[sr][sc];
                continue;
            }

            int minCost = 1e8;
            if (sr + 1 < grid.size())
                minCost = min(minCost, dp[sr + 1][sc]);
            if (sc + 1 < grid[0].size())
                minCost = min(minCost, dp[sr][sc + 1]);

            dp[sr][sc] = minCost + grid[sr][sc];
        }
    }
    return dp[0][0];
}

int minPathSum(vector<vector<int>> &grid)
{
    vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size(), 0));
    return minPathSum(0, 0, grid, dp);
}

// Gold Mine problem gfg ====================================================
int goldMin(int sr, int sc, vector<vector<int>> &grid, vector<vector<int>> &dp)
{

    if (sc == grid[0].size() - 1)
    {
        return dp[sr][sc] = grid[sr][sc];
    }

    if (dp[sr][sc] != 0)
        return dp[sr][sc];

    int dir[3][2] = {{-1, 1}, {0, 1}, {1, 1}};
    int maxCoins = 0;
    for (int d = 0; d < 3; d++)
    {
        int x = sr + dir[d][0];
        int y = sc + dir[d][1];
        if (x >= 0 && y >= 0 && x < grid.size() && y < grid[0].size())
        {
            maxCoins = max(maxCoins, goldMin(x, y, grid, dp));
        }
    }

    return dp[sr][sc] = maxCoins + grid[sr][sc];
}

int goldMin_DP(vector<vector<int>> &grid, vector<vector<int>> &dp)
{

    for (int sc = grid[0].size() - 1; sc >= 0; sc--)
    {
        for (int sr = grid.size() - 1; sr >= 0; sr--)
        {
            if (sc == grid[0].size() - 1)
            {
                dp[sr][sc] = grid[sr][sc];
                continue;
            }

            int dir[3][2] = {{-1, 1}, {0, 1}, {1, 1}};
            int maxCoins = 0;
            for (int d = 0; d < 3; d++)
            {
                int x = sr + dir[d][0];
                int y = sc + dir[d][1];
                if (x >= 0 && y >= 0 && x < grid.size() && y < grid[0].size())
                    maxCoins = max(maxCoins, dp[x][y]);
            }

            dp[sr][sc] = maxCoins + grid[sr][sc];
        }
    }

    int maxCoin = 0;
    for (int i = 0; i < grid.size(); i++)
        maxCoin = max(maxCoin, dp[i][0]);
    return maxCoin;
}

// https://www.geeksforgeeks.org/count-number-of-ways-to-partition-a-set-into-k-subsets/

int count_of_ways(int n, int k, vector<vector<int>> &dp)
{
    if (n < k)
        return 0;
    if (n == k || k == 1)
        return dp[k][n] = 1;

    if (dp[k][n] != 0)
        return dp[k][n];

    int newGroup = count_of_ways(n - 1, k - 1, dp);
    int ExistingGroup = count_of_ways(n - 1, k, dp) * k;

    return dp[k][n] = newGroup + ExistingGroup;
}

int count_of_ways_DP(int n, int k, vector<vector<int>> &dp)
{

    int K = k, N = n;
    for (k = 1; k <= K; k++)
    {
        for (n = 0; n <= N; n++)
        {
            if (n < k)
                continue;

            if (n == k || k == 1)
            {
                dp[k][n] = 1;
                continue;
            }

            int newGroup = dp[k - 1][n - 1];
            int ExistingGroup = dp[k][n - 1] * k;

            dp[k][n] = newGroup + ExistingGroup;
        }
    }

    return dp[K][N];
}

void count_of_ways(int n, int k)
{
    if (n < k)
        return;

    vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0));
    // cout << count_of_ways(n, k, dp) << endl;
    cout << count_of_ways_DP(n, k, dp) << endl;

    display2D(dp);
}

// Substirng and Subsequence with palindrome ============================================
vector<vector<bool>> isPlaindromeSubstring(string str)
{
    int n = str.size();
    vector<vector<bool>> dp(n, vector<bool>(n, 0));
    for (int gap = 0; gap < n; gap++)
    {
        for (int i = 0, j = gap; j < n; i++, j++)
        {
            if (gap == 0)
                dp[i][j] = true;
            else if (gap == 1 && str[i] == str[j])
                dp[i][j] = true;
            else
                dp[i][j] = str[i] == str[j] && dp[i + 1][j - 1];
        }
    }
    return dp;
}

//Leetcode 005.==================================================================
string longestPlaindromeSubstring(string str)
{
    int n = str.length();
    vector<vector<int>> dp(n, vector<int>(n, 0));

    int maxLen = 0;
    int si = 0, ei = 0;
    for (int gap = 0; gap < n; gap++)
    {
        for (int i = 0, j = gap; j < n; i++, j++)
        {
            if (gap == 0)
                dp[i][j] = 1;
            else if (gap == 1 && str[i] == str[j])
                dp[i][j] = 2;
            else if (str[i] == str[j] && dp[i + 1][j - 1] != 0)
                dp[i][j] = gap + 1;

            if (dp[i][j] > maxLen)
            {
                maxLen = dp[i][j];
                si = i;
                ei = j;
            }
        }
    }

    return str.substr(si, (ei - si + 1));
}

//Leetcode 647.=================================================================================
int countAllPlaindromicSubstring(string str)
{
    int n = str.length();
    vector<vector<int>> dp(n, vector<int>(n, 0));

    int count = 0;
    for (int gap = 0; gap < n; gap++)
    {
        for (int i = 0, j = gap; j < n; i++, j++)
        {
            if (gap == 0)
                dp[i][j] = 1;
            else if (gap == 1 && str[i] == str[j])
                dp[i][j] = 2;
            else if (str[i] == str[j] && dp[i + 1][j - 1] != 0)
                dp[i][j] = gap + 1;

            count += dp[i][j] != 0 ? 1 : 0;
        }
    }
}

//Leetcode 516.================================================================================================================
int longestPlaindromeSubseq_Rec(string str, int si, int ei, vector<vector<int>> &dp)
{
    if (si > ei)
        return 0;
    if (si == ei)
        return dp[si][ei] = 1;
    if (dp[si][ei] != 0)
        return dp[si][ei];

    int len = 0;
    if (str[si] == str[ei])
        len = longestPlaindromeSubseq_Rec(str, si + 1, ei - 1, dp) + 2;
    else
        len = max(longestPlaindromeSubseq_Rec(str, si + 1, ei, dp), longestPlaindromeSubseq_Rec(str, si, ei - 1, dp));

    return dp[si][ei] = len;
}

int longestPlaindromeSubseq_DP(string &str, vvi &dp, vector<vector<bool>> &isPalin)
{
    int n = str.size();
    for (int gap = 0; gap < n; gap++)
    {
        for (int i = 0, j = gap; j < n; i++, j++)
        {
            if (isPalin[i][j])
            {
                dp[i][j] = j - i + 1;
                continue;
            }

            if (str[i] == str[j])
                dp[i][j] = dp[i + 1][j - 1] + 2;
            else
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
        }
    }
    return dp[0][n - 1];
}

//Leetcode 115 : distinct-subsequences.=========================================================
int distinct_subsequences(string S, string T, int n, int m, vector<vector<int>> &dp)
{
    if (m == 0)
        return dp[n][m] = 1;
    if (m > n)
        return dp[n][m] = 0;

    if (dp[n][m] != -1)
        return dp[n][m];

    if (S[n - 1] == T[m - 1])
        return dp[n][m] = distinct_subsequences(S, T, n - 1, m - 1, dp) + distinct_subsequences(S, T, n - 1, m, dp);

    return dp[n][m] = distinct_subsequences(S, T, n - 1, m, dp);
}

int distinct_subsequences_02(string S, string T, int i, int j, vector<vector<int>> &dp)
{
    if (T.length() - j == 0)
        return dp[i][j] = 1;
    if (S.length() - i > T.length() - j)
        return dp[i][j] = 0;

    if (dp[i][j] != -1)
        return dp[i][j];

    if (S[i] == T[j])
        return dp[i][j] = distinct_subsequences_02(S, T, i + 1, j + 1, dp) + distinct_subsequences_02(S, T, i + 1, j, dp);

    return dp[i][j] = distinct_subsequences_02(S, T, i + 1, j, dp);
}

int distinct_subsequences_DP(string S, string T, int n, int m, vector<vector<int>> &dp)
{
    int N = n, M = m;
    for (n = 0; n <= N; n++)
    {
        for (m = 0; m <= M; m++)
        {
            if (m == 0)
            {
                dp[n][m] = 1;
                continue;
            }
            if (m > n)
            {
                dp[n][m] = 0;
                continue;
            }
            if (S[n - 1] == T[m - 1])
                dp[n][m] = dp[n - 1][m - 1] + dp[n - 1][m];
            else
                dp[n][m] = dp[n - 1][m];
        }
    }

    return dp[N][M];
}

int numDistinct(string s, string t)
{
    int n = s.length();
    int m = t.length();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));
    // cout << distinct_subsequences(s, t, n, m, dp) << endl;
    cout << distinct_subsequences_DP(s, t, n, m, dp) << endl;

    display2D(dp);
}

//Geeks: https://practice.geeksforgeeks.org/problems/count-palindromic-subsequences/1
int countPS(string &s, int i, int j, vector<vector<int>> &dp)
{
    if (i > j)
        return 0;
    if (i == j)
        return dp[i][j] = 1;
    if (dp[i][j] != 0)
        return dp[i][j];

    int middleString = countPS(s, i + 1, j - 1, dp);
    int excludingLast = countPS(s, i, j - 1, dp);
    int excludingFirst = countPS(s, i + 1, j, dp);

    int ans = excludingFirst + excludingLast;
    return dp[i][j] = (s[i] == s[j]) ? ans + 1 : ans - middleString;
}

int countPS_DP(string &s, int i, int j, vector<vector<int>> &dp)
{

    int n = s.length();
    for (int gap = 0; gap < n; gap++)
    {
        for (int i = 0, j = gap; j < n; j++, i++)
        {
            if (i == j)
            {
                dp[i][j] = 1;
                continue;
            }

            int middleString = dp[i + 1][j - 1];
            int excludingLast = dp[i][j - 1];
            int excludingFirst = dp[i + 1][j];

            int ans = excludingFirst + excludingLast;
            dp[i][j] = (s[i] == s[j]) ? ans + 1 : ans - middleString;
        }
    }
    return dp[0][n - 1];
}

// LeetCode : 1143 =========================================================
int longestCommonSubsequence(string &text1, string &text2, int i, int j, vector<vector<int>> &dp)
{
    if (i == text1.length() || j == text2.length())
        return 0;
    if (dp[i][j] != 0)
        return dp[i][j];
    int ans = 0;
    if (text1[i] == text2[j])
        ans = longestCommonSubsequence(text1, text2, i + 1, j + 1, dp) + 1;
    else
        ans = max(longestCommonSubsequence(text1, text2, i + 1, j, dp), longestCommonSubsequence(text1, text2, i, j + 1, dp));

    dp[i][j] = ans;
}

int longestCommonSubsequence_DP(string &text1, string &text2, int i, int j, vector<vector<int>> &dp)
{
    for (i = text1.length(); i >= 0; i--)
    {
        for (j = text2.length(); j >= 0; j--)
        {
            if (i == text1.length() || j == text2.length())
                continue;

            int ans = 0;
            if (text1[i] == text2[j])
                ans = dp[i + 1][j + 1] + 1;
            else
                ans = max(dp[i + 1][j], dp[i][j + 1]);

            dp[i][j] = ans;
        }
    }
    return dp[0][0];
}

int longestCommonSubsequence(string text1, string text2)
{
    vector<vector<int>> dp(text1.length() + 1, vector<int>(text2.length() + 1, 0));
    int ans = 0;
    ans = longestCommonSubsequence(text1, text2, 0, 0, dp);
    // ans = longestCommonSubsequence_DP(text1, text2, 0, 0, dp);
    display2D(dp);
    return ans;
}

int max_ = 0;
int longestCommonSubstring(string &text1, string &text2, int i, int j, vector<vector<int>> &dp)
{
    if (i == text1.length() || j == text2.length())
        return dp[i][j] = 0;
    if (dp[i][j] != 0)
        return dp[i][j];

    int a = longestCommonSubstring(text1, text2, i + 1, j, dp);
    int b = longestCommonSubstring(text1, text2, i, j + 1, dp);

    if (text1[i] == text2[j])
    {
        int a = longestCommonSubstring(text1, text2, i + 1, j + 1, dp) + 1;
        max_ = max(max_, a);
        return dp[i][j] = a;
    }

    return 0;
}

int longestCommonSubstring_DP(string &text1, string &text2, int i, int j, vector<vector<int>> &dp)
{
    int max_ = 0;
    for (i = text1.length(); i >= 0; i--)
    {
        for (j = text2.length(); j >= 0; j--)
        {
            if (i == text1.length() || j == text2.length())
                continue;

            int ans = 0;
            if (text1[i] == text2[j])
            {
                ans = dp[i + 1][j + 1] + 1;
                max_ = max(max_, ans);
            }
            int a = dp[i + 1][j];
            int b = dp[i][j + 1];

            dp[i][j] = ans;
        }
    }
    return dp[0][0];
}

// Leetcode: 1035
// Same as longest common subsequence ==================================================
int lcs(vector<int> &a, vector<int> &b, int i, int j, vector<vector<int>> &dp)
{
    if (i == a.size() || j == b.size())
        return 0;
    if (dp[i][j] != 0)
        return dp[i][j];
    if (a[i] == b[j])
        return dp[i][j] = lcs(a, b, i + 1, j + 1, dp) + 1;
    return dp[i][j] = max(lcs(a, b, i + 1, j, dp), lcs(a, b, i, j + 1, dp));
}

int lcs_DP(vector<int> &a, vector<int> &b, int n, int m, vector<vector<int>> &dp)
{

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

            if (a[i] == b[j])
                dp[i][j] = dp[i + 1][j + 1] + 1;
            else
                dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]);
        }
    }
    return dp[0][0];
}

int maxUncrossedLines(vector<int> &A, vector<int> &B)
{
    int n = A.size();
    int m = B.size();
    vector<vector<int>> dp(n, vector<int>(m, 0));
    // return lcs(A, B, 0, 0, dp);
    return lcs_DP(A, B, n, m, dp);
}

//leetcode 1458.
int maxDotProduct(vector<int> &nums1, vector<int> &nums2)
{
    int n = nums1.size(), m = nums2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = n; i >= 0; i--)
    {
        for (int j = m; j >= 0; j--)
        {
            if (i == n || m == j)
            {
                dp[i][j] = -1e8;
                continue;
            }

            int val = nums1[i] * nums2[j];
            int a = dp[i + 1][j + 1] + val;
            int b = dp[i + 1][j];
            int c = dp[i][j + 1];

            dp[i][j] = max(max(a, b), max(c, val));
        }
    }

    return dp[0][0];
}

// Leetcode 72 convering str1 -> str2;
int editDistance(string &str1, string &str2, int n, int m, vector<vector<int>> &dp)
{
    if (n == 0 || m == 0)
        return dp[n][m] = (n == 0 ? m : n);
    if (dp[n][m] != 0)
        return dp[n][m];
    if (str1[n - 1] == str2[m - 1])
        return dp[n][m] = editDistance(str1, str2, n - 1, m - 1, dp);
    int insert_ = editDistance(str1, str2, n, m - 1, dp) + 1;
    int replace_ = editDistance(str1, str2, n - 1, m - 1, dp) + 1;
    int delete_ = editDistance(str1, str2, n - 1, m, dp) + 1;
    return dp[n][m] = min({insert_, replace_, delete_});
}

int minDistance(string word1, string word2)
{
    int n = word1.length();
    int m = word2.length();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    return editDistance(word1, word2, n, m, dp);
}

void stringSubstringSet()
{
    // string str = "geeksforgeeks";
    // int n = str.length();
    // int si = 0, ei = n - 1;
    // vector<vector<int>> dp(n, vector<int>(n, 0));

    // vector<vector<bool>> isPlalindrome = isPlaindromeSubstring(str);
    // cout << longestPlaindromeSubstring("abcaacbefgpgf") << endl;

    // cout << longestPlaindromeSubseq_Rec(str, si, ei, dp, isPlalindrome) << endl;
    // cout << longestPlaindromeSubseq_DP(str, dp, isPlalindrome) << endl;

    // display2D(dp);

    // numDistinct("geeksforgeeks", "gks");
    // cout << longestCommonSubsequence("abc", "aab") << endl;
}

// Coin_Change/Target_type =========================================================
int coinChangePermutation(int tar, vi &arr, vi &dp)
{
    if (tar == 0)
        return dp[tar] = 1;
    if (dp[tar] != 0)
        return dp[tar];
    int count = 0;
    for (auto ele : arr)
        if (tar - ele >= 0)
            count += coinChangePermutation(tar - ele, arr, dp);
    return dp[tar] = count;
}

int coinChangePermutation_DP(int Tar, vi &arr, vi &dp)
{
    int n = arr.size();
    for (int tar = 0; tar <= Tar; tar++)
    {
        if (tar == 0)
        {
            dp[tar] = 1;
            continue;
        }
        int count;
        for (auto ele : arr)
            if (tar - ele >= 0)
                count += dp[tar - ele];
        dp[tar] = count;
    }
    return dp[Tar];
}

// jugad method for finding the it using 1-d array becuase it doesn't overlap in memoization.
int coinChangeCombination_DP(int Tar, vi &arr, vi &dp)
{
    int n = arr.size();
    dp[0] = 1;
    for (auto ele : arr)
        for (int tar = ele; tar <= Tar; tar++)
            dp[tar] += dp[tar - ele];
    return dp[Tar];
}

//https://www.geeksforgeeks.org/find-number-of-solutions-of-a-linear-equation-of-n-variables/

int LinearEquation_DP(vector<int> &coeff, int rhs)
{
    vector<int> dp(rhs + 1, 0);
    dp[0] = 1;
    for (int ele : coeff)
        for (int tar = ele; tar <= rhs; tar++)
            dp[tar] += dp[tar - ele];
}

//leetcode 322
int coinChange_(vector<int> &coins, int tar, vector<int> &dp)
{
    if (tar == 0)
        return 0;

    if (dp[tar] != 0)
        return dp[tar];
    int minHeight = 1e8;
    for (int ele : coins)
    {
        if (tar - ele >= 0)
        {
            int rMinHeight = coinChange_(coins, tar, dp);
            if (rMinHeight != 1e8 && rMinHeight + 1 < minHeight)
                minHeight = rMinHeight + 1;
        }
    }
    return dp[tar] = minHeight;
}

int coinChange(vector<int> &coins, int tar)
{
    vector<int> dp(tar + 1, 0);
    return coinChange_(coins, tar, dp);
}

void coinChange()
{
    // vector<int> arr{2, 3, 5, 7};
    // int tar = 10;
    // vector<int> dp(tar + 1, 0);
    // cout << coinChangePermutation(arr, tar, dp) << endl;

    // display(dp);
}

int targetSum(vector<int> &coins, int idx, int tar, vector<vector<int>> &dp)
{
    if (idx == coins.size() || tar == 0)
    {
        if (tar == 0)
            return dp[idx][tar] = 1;
        return 0;
    }

    if (dp[idx][tar] != 0)
        return dp[idx][tar];

    int count = 0;
    if (tar - coins[idx] >= 0)
        count += targetSum(coins, idx + 1, tar - coins[idx], dp);
    count += targetSum(coins, idx + 1, tar, dp);
    return dp[idx][tar] = count;
}

int targetSum_02(vector<int> &coins, int idx, int tar, vector<vector<int>> &dp)
{
    if (tar == 0 || idx == 0)
    {
        if (tar == 0)
            return dp[idx][tar] = 1;
        return dp[idx][tar] = 0;
    }

    if (dp[idx][tar] != 0)
        return dp[idx][tar];

    int count = 0;
    if (tar - coins[idx - 1] >= 0)
        count += targetSum_02(coins, idx - 1, tar - coins[idx - 1], dp);

    count += targetSum_02(coins, idx - 1, tar, dp);
    return dp[idx][tar] = count;
}

int printPathOfTargetSum(vector<int> &coins, int idx, int tar, string ans, vector<vector<bool>> &dp)
{
    if (tar == 0 || idx == 0)
    {
        if (tar == 0)
        {
            cout << ans << endl;
            return 1;
        }
        return 0;
    }

    int count = 0;
    if (tar - coins[idx - 1] >= 0 && dp[idx - 1][tar - coins[idx - 1]])
        count += printPathOfTargetSum(coins, idx - 1, tar - coins[idx - 1], ans + to_string(coins[idx - 1]) + " ", dp);

    if (dp[idx - 1][tar])
        count += printPathOfTargetSum(coins, idx - 1, tar, ans, dp);

    return count;
}

void targetSum_02DP(vector<int> &coins, int tar)
{
    int n = coins.size();
    int Tar = tar;
    vector<vector<bool>> dp(n + 1, vector<bool>(tar + 1));

    for (int idx = 0; idx < n + 1; idx++)
    {
        for (tar = 0; tar <= Tar; tar++)
        {
            if (tar == 0 || idx == 0)
            {
                if (tar == 0)
                    dp[idx][tar] = 1;
                continue;
            }

            if (tar - coins[idx - 1] >= 0)
                dp[idx][tar] = dp[idx - 1][tar - coins[idx - 1]];
            dp[idx][tar] = dp[idx][tar] || dp[idx - 1][tar];
        }
    }

    for (vector<bool> &ar : dp)
    {
        for (bool ele : ar)
        {
            cout << ele << " ";
        }
        cout << endl;
    }

    cout << printPathOfTargetSum(coins, coins.size(), Tar, "", dp) << endl; // printing path of dp using back engineering;
}

void targetType()
{
    vi arr = {2, 3, 5, 7};
    int tar = 10;
    // vvi dp(arr.size() + 1, vi(tar + 1, 0));
    // cout << targetSum_02(arr, arr.size(), tar, dp) << endl;
    targetSum_02DP(arr, tar);

    // display2D(dp);
}

int knapsack01(vector<int> &w, vector<int> &p, int weight, int n, vector<vector<int>> &dp)
{
    if (weight == 0 || n == 0)
    {
        return 0;
    }

    if (dp[n][weight] != 0)
        return dp[n][weight];

    int maxProfit = -1e8;
    if (weight - w[n - 1] >= 0)
        maxProfit = max(maxProfit, knapsack01(w, p, weight - w[n - 1], n - 1, dp) + p[n - 1]); // dp[n-1][weight - w[n - 1]]+p[n-1]
    maxProfit = max(maxProfit, knapsack01(w, p, weight, n - 1, dp));                           // dp[n-1][weight]

    return dp[n][weight] = maxProfit;
}

int unbpounded(vector<int> &w, vector<int> &p, int weight)
{
    vector<int> dp(w.size() + 1, -1e8);
    dp[0] = 0;
    for (int i = 0; i < w.size(); i++)
        for (int tar = w[i]; tar <= weight; tar++)
            dp[tar] = max(dp[tar], dp[tar - w[i]] + p[i]);

    return dp[w.size()];
}

void knapsack()
{
    vector<int> p = {100, 280, 120};
    vector<int> w = {10, 40, 20};
    int weight = 60;
    int n = w.size();
    vector<vector<int>> dp(n + 1, vector<int>(weight + 1, 0));

    cout << knapsack01(w, p, weight, n, dp) << endl;
}

//Leetcode 416
bool canPartition_(vector<int> &nums, int n, int sum, vector<vector<int>> &dp)
{
    if (sum == 0 || n == 0)
    {
        if (sum == 0)
            return dp[n][sum] = 1;
        return dp[n][sum] = 0;
    }

    if (dp[n][sum] != -1)
        return dp[n][sum];

    bool res = false;
    if (sum - nums[n - 1] >= 0)
        res = res || canPartition_(nums, n - 1, sum - nums[n - 1], dp) == 1;
    res = res || canPartition_(nums, n - 1, sum, dp) == 1;

    return dp[n][sum] = res ? 1 : 0;
}

bool canPartition(vector<int> &nums)
{
    int sum = 0;
    for (int ele : nums)
        sum += ele;
    if (sum % 2 != 0)
        return false;

    sum /= 2;
    vector<vector<int>> dp(nums.size() + 1, vector<int>(sum + 1, -1));

    return canPartition_(nums, nums.size(), sum, dp);
}

//Leetcode 494
int min_;
int sum(vector<int> &nums, int tar, int idx, int s, vector<vector<int>> &dp)
{
    if (idx == nums.size())
    {
        if (tar == s)
            return dp[idx][tar + max_] = 1;
        return dp[idx][tar + max_] = 0;
    }
    if (dp[idx][tar + max_] != -1)
        return dp[idx][tar + max_];
    int count = 0;
    count += sum(nums, tar - nums[idx], idx + 1, s, dp);
    count += sum(nums, tar + nums[idx], idx + 1, s, dp);
    return dp[idx][tar + max_] = count;
}

int findTargetSumWays(vector<int> &nums, int S)
{
    int n = nums.size();
    min_ = 0;
    max_ = 0;
    for (auto ele : nums)
    {
        max_ += ele;
        min_ -= ele;
    }
    vector<vector<int>> dp(n + 1, vector<int>(max_ - min_ + 1, -1));
    // int ans = targetSum(nums, 0, 0, S, dp);
    int ans = sum(nums, 0, 0, S, dp);
    // for (auto ar : dp)
    // {
    //     for (auto ele : ar)
    //         cout << ele << " ";
    //     cout << endl;
    // }
    return ans;
}

//LIS ======================================================================
int LIS_leftToRight(vector<int> &arr, vector<int> &dp)
{
    int N = arr.size();
    int oMax = 0;
    for (int i = 0; i < N; i++)
    {
        dp[i] = 1;
        for (int j = i - 1; j >= 0; j--)
            if (arr[j] < arr[i])
                dp[i] = max(dp[i], dp[j] + 1);
        oMax = max(oMax, dp[i]);
    }
    return oMax;
}

//LDS
int LIS_rightToLeft(vector<int> &arr, vector<int> &dp)
{
    int N = arr.size();
    int oMax = 0;
    for (int i = N - 1; i >= 0; i--)
    {
        dp[i] = 1;
        for (int j = i + 1; j < N; j++)
            if (arr[j] < arr[i])
                dp[i] = max(dp[i], dp[j] + 1);
        oMax = max(oMax, dp[i]);
    }
    return oMax;
}

//Longest bitonic subsequence
//https://www.geeksforgeeks.org/longest-bitonic-subsequence-dp-15/
int LBS(vector<int> &arr)
{
    int n = arr.size();
    vector<int> LIS(n, 0);
    vector<int> LDS(n, 0);

    LIS_leftToRight(arr, LIS);
    LIS_rightToLeft(arr, LDS);

    int maxLen = 0;
    for (int i = 0; i < n; i++)
    {
        int len = LIS[i] + LDS[i] - 1;
        maxLen = max(maxLen, len);
    }
    return maxLen;
}

// this can also be maximum sum increasing subsequence gfg
// https://practice.geeksforgeeks.org/problems/maximum-sum-increasing-subsequence/0
vi Lis(vi &arr, int n)
{
    vi dp(n, 0);
    for (int i = 0; i < n; i++)
    {
        dp[i] = arr[i];
        for (int j = i - 1; j >= 0; j--)
            if (arr[j] < arr[i])
                dp[i] = max(dp[i], dp[j] + arr[i]);
    }
    return dp;
}

//Lds maximum sum subseqeuence
vi Lbs(vi &arr, int n)
{
    vi dp(n, 0);
    for (int i = n - 1; i >= 0; i--)
    {
        dp[i] = arr[i];
        for (int j = i + 1; j < n; j++)
            if (arr[j] < arr[i])
                dp[i] = max(dp[i], dp[j] + arr[i]);
    }
    return dp;
}

int LBS_Sum()
{
    int n;
    cin >> n;
    vi arr(n, 0);
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    vi Lis_dp = Lis(arr, n);
    vi Lbs_dp = Lbs(arr, n);

    // for (int i = 0; i < n; i++)
    // {
    //     cout << Lis_dp[i] << " " << Lbs_dp[i] << endl;
    // }

    int max_ = 0;
    for (int i = 0; i < n; i++)
    {
        max_ = max(max_, Lis_dp[i] + Lbs_dp[i] - arr[i]);
    }

    return max_;
}

int findNumberOfLIS(vector<int> &arr)
{
    int n = arr.size();
    if (n <= 1)
        return n;

    vector<int> dp(n, 0);
    vector<int> count(n, 0);

    int maxLen = 0;
    int maxCount = 0;
    for (int i = 0; i < n; i++)
    {
        dp[i] = 1;
        count[i] = 1;

        for (int j = i - 1; j >= 0; j--)
        {
            if (arr[i] > arr[j])
            {
                if (dp[j] + 1 > dp[i])
                {
                    dp[i] = dp[j] + 1;
                    count[i] = count[j];
                }
                else if (dp[j] + 1 == dp[i])
                    count[i] += count[j];
            }
        }

        if (dp[i] > maxLen)
        {
            maxLen = dp[i];
            maxCount = count[i];
        }
        else if (dp[i] == maxLen)
            maxCount += count[i];
    }

    return maxCount;
}

// minimum no of deletion to make array in sorted order in increasing order.
int minDeletion(vector<int> &arr)
{
    int n = arr.size();
    vector<int> dp(n, 0);

    int oMax = 0;
    for (int i = 0; i < n; i++)
    {
        dp[i] = 1;
        for (int j = i - 1; j >= 0; j--)
        {
            if (arr[j] <= arr[i])
                dp[i] = max(dp[i], dp[j] + 1);
        }

        oMax = max(oMax, dp[i]);
    }

    return n - oMax;
}

//Leetcode 354
int maxEnvelopes(vector<vector<int>> &arr)
{
    // for Java:
    // Arrays.sort(arr,(int[] a, int[] b)-> {
    //     if (a[0] == b[0])
    //         return b[1] - a[1]; // other - this
    //     return a[0] - b[0];     // this - other. default
    // });

    sort(arr.begin(), arr.end(), [](vector<int> &a, vector<int> &b) {
        if (a[0] == b[0])
            return b[1] < a[1]; // other - this
        return a[0] < b[0];     // this - other., for cpp replace '-' with '<' default
    });

    int n = arr.size();
    vector<int> dp(n, 0);

    int oMax = 0;
    for (int i = 0; i < n; i++)
    {
        dp[i] = 1;
        for (int j = i - 1; j >= 0; j--)
        {
            if (arr[j][1] < arr[i][1])
                dp[i] = max(dp[i], dp[j] + 1);
        }

        oMax = max(oMax, dp[i]);
    }

    return oMax;
}

// Leetcode 1235 :

int Next(int cur, vector<vector<int>> &arr)
{
    for (int next = cur + 1; next < arr.size(); next++)
        if (arr[cur][1] <= arr[next][0])
            return next;
    return -1;
}

int dfs(int cur, vector<vector<int>> &arr, unordered_map<int, int> &dp)
{
    if (cur == arr.size())
        return 0;
    if (dp.find(cur) != dp.end())
        return dp[cur];

    int next = Next(cur, arr);
    int include = arr[cur][2] + (next != -1 ? dfs(next, arr, dp) : 0);
    int exclude = dfs(cur + 1, arr, dp);

    dp[cur] = max(include, exclude);
    return max(include, exclude);
}

int jobScheduling(vector<int> &startTime, vector<int> &endTime, vector<int> &profit)
{
    int n = profit.size();
    vector<vector<int>> arr(n, vector<int>(3, 0));
    for (int i = 0; i < n; i++)
        arr[i] = {startTime[i], endTime[i], profit[i]};
    sort(arr.begin(), arr.end());

    unordered_map<int, int> dp;
    return dfs(0, arr, dp);
    // Lis solution giving TLE;
    //         sort(arr.begin(), arr.end(), [](vector<int> &a, vector<int> &b) {
    //             return a[1] < b[1];
    //         });
    //         vector<int> dp(n, 0);
    //         int maxRes = 0;
    //         for (int i = 0; i < n; i++)
    //         {
    //             dp[i] = arr[i][2];
    //             for (int j = i - 1; j >= 0; j--)
    //             {
    //                 if (arr[i][0] >= arr[j][1])
    //                     dp[i] = max(dp[i], dp[j] + arr[i][2]);
    //             }
    //             maxRes = max(maxRes, dp[i]);
    //         }

    //         return maxRes;
}

// Cut Type ===================================================================
// Matrix chain multiplication.
int MCM(vi &arr, int si, int ei, vvi &dp)
{
    if (si + 1 == ei)
        return dp[si][ei] = 0;

    if (dp[si][ei] != -1)
        return dp[si][ei];

    int ans = 1e9;
    for (int cut = si + 1; cut < ei; cut++)
    {

        int leftAns = MCM(arr, si, cut, dp);
        int rightAns = MCM(arr, cut, ei, dp);

        int myAns = leftAns + arr[si] * arr[cut] * arr[ei] + rightAns;
        if (ans > myAns)
            ans = myAns;
    }

    return dp[si][ei] = ans;
}

int MCM_DP_Ans(vector<int> &arr)
{
    int n = arr.size();
    vector<vector<string>> sdp(n, vector<string>(n, ""));
    vector<vector<int>> dp(n, vector<int>(n, -1));

    for (int gap = 1; gap < arr.size(); gap++)
    {
        for (int si = 0, ei = gap; ei < arr.size(); si++, ei++)
        {
            if (si + 1 == ei)
            {
                dp[si][ei] = 0;
                sdp[si][ei] = (char)(si + 'A');
                continue;
            }

            int ans = 1e8;
            string sans = "";
            for (int cut = si + 1; cut < ei; cut++)
            {
                int leftCost = dp[si][cut];  //MCM_rec(arr, si, cut, dp);
                int rightCost = dp[cut][ei]; //MCM_rec(arr, cut, ei, dp);

                int myCost = leftCost + arr[si] * arr[cut] * arr[ei] + rightCost;
                if (myCost < ans)
                {
                    ans = myCost;
                    sans = "(" + sdp[si][cut] + sdp[cut][ei] + ")";
                }
            }

            dp[si][ei] = ans;
            sdp[si][ei] = sans;
        }
    }

    cout << sdp[0][arr.size() - 1] << endl;
    cout << dp[0][arr.size() - 1] << endl;
}

int costOfSearching(vector<int> &freq, int si, int ei)
{
    int sum = 0;
    for (int i = si; i <= ei; i++)
        sum += freq[i];
    return sum;
}

int OBST_rec(vector<int> &freq, int si, int ei, vector<vector<int>> &dp)
{
    if (dp[si][ei] != 0)
        return dp[si][ei];

    int ans = 1e8;
    for (int cut = si; cut <= ei; cut++)
    {
        int leftTreeCost = (cut == si) ? 0 : OBST_rec(freq, si, cut - 1, dp);
        int rightTreeCost = (cut == ei) ? 0 : OBST_rec(freq, cut + 1, ei, dp);

        int myCost = leftTreeCost + costOfSearching(freq, si, ei) + rightTreeCost;
        if (myCost < ans)
            ans = myCost;
    }

    return dp[si][ei] = ans;
}

int OBST_DP(vector<int> &freq, int si, int ei, vector<vector<int>> &dp)
{
    vector<int> prefixSum(freq.size() + 1, 0);
    for (int i = 1; i < prefixSum.size(); i++)
        prefixSum[i] = prefixSum[i - 1] + freq[i - 1];

    for (int gap = 0; gap < freq.size(); gap++)
    {
        for (si = 0, ei = gap; ei < freq.size(); si++, ei++)
        {
            int ans = 1e8;
            for (int cut = si; cut <= ei; cut++)
            {
                int leftTreeCost = (cut == si) ? 0 : dp[si][cut - 1];  //OBST_rec(freq, si, cut - 1, dp);
                int rightTreeCost = (cut == ei) ? 0 : dp[si][cut + 1]; //OBST_rec(freq, cut + 1, ei, dp);

                int myCost = leftTreeCost + prefixSum[ei + 1] - prefixSum[si] + rightTreeCost;
                if (myCost < ans)
                    ans = myCost;
            }
            dp[si][ei] = ans;
        }
    }
    return dp[0][freq.size() - 1];
}

int burstBallon(vector<int> &arr, int si, int ei, vector<vector<int>> &dp)
{

    if (dp[si][ei] != 0)
        return dp[si][ei];

    int lVal = (si == 0) ? 1 : arr[si - 1];
    int rVal = (ei == arr.size() - 1) ? 1 : arr[ei + 1];

    int ans = 0;
    for (int cut = si; cut <= ei; cut++)
    {
        int leftTreeCost = (cut == si) ? 0 : burstBallon(arr, si, cut - 1, dp);
        int rightTreeCost = (cut == ei) ? 0 : burstBallon(arr, cut + 1, ei, dp);

        int myCost = leftTreeCost + lVal * arr[cut] * rVal + rightTreeCost;
        if (myCost > ans)
            ans = myCost;
    }

    return dp[si][ei] = ans;
}

int maxCoins(vector<int> &nums)
{
    int n = nums.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    cout << burstBallon(nums, 0, n - 1, dp) << endl;
}

void optimalBinarySearchTree()
{
    vector<int> keys{10, 12, 20};
    vector<int> freq{34, 8, 50};

    int n = freq.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));

    cout << OBST_rec(freq, 0, n - 1, dp) << endl;
    // cout << OBST_DP(freq, 0, n - 1, dp) << endl;

    display2D(dp);
}

void MCM()
{
    vector<int> arr{3, 7, 2, 6, 5, 4};
    int n = arr.size();
    vector<vector<int>> dp(n, vector<int>(n, -1));
    // cout << MCM_rec(arr, 0, n - 1, dp) << endl;
    // cout << MCM_DP(arr, 0, n - 1, dp) << endl;
    // MCM_DP_Ans(arr);

    display2D(dp);
}

// leetcode 132 =============================
// soluiton is in java to pass
// int minCut(String str, int si, int ei, boolean[][] isPalin, int[][] dp)
// {

//     if (isPalin[si][ei])
//         return dp[si][ei] = 0;

//     if (dp[si][ei] != -1)
//         return dp[si][ei];

//     int myans = (int)1e9;
//     for (int cut = si + 1; cut <= ei; cut++)
//     {
//         int leftCuts = minCut(str, si, cut - 1, isPalin, dp);
//         int rightCuts = minCut(str, cut, ei, isPalin, dp);

//         int myCost = leftCuts + 1 + rightCuts;
//         if (myCost < myans)
//             myans = myCost;
//     }
//     return dp[si][ei] = myans;
// }

// public  int minCut(String str)
// {
//     int n = str.length();
//     boolean[][] isPalin = new boolean[n][n];

//     for (int gap = 0; gap < n; gap++)
//     {
//         for (int i = 0, j = gap; j < n; i++, j++)
//         {
//             if (gap == 0)
//             {
//                 isPalin[i][j] = true;
//                 continue;
//             }
//             else if (gap == 1 && str.charAt(i) == str.charAt(j))
//                 isPalin[i][j] = true;
//             else if (str.charAt(i) == str.charAt(j))
//                 isPalin[i][j] = isPalin[i + 1][j - 1];
//         }
//     }

//     if (isPalin[0][n - 1])
//         return 0;

//     int[][] dp = new int[n][n];
//     for (int[] ar : dp)
//         Arrays.fill(ar, 0);
//     // return minCut(str, 0, n - 1, isPalin, dp);
//     for (int gap = 1; gap < n; gap++)
//     {
//         for (int si = 0, ei = gap; ei < n; si++, ei++)
//         {

//             if (isPalin[si][ei])
//                 dp[si][ei] = 0;
//             else
//             {
//                 int myans = (int)1e9;
//                 for (int cut = si + 1; cut <= ei; cut++)
//                 {
//                     int leftCuts = dp[si][cut - 1]; //minCut(str, si, cut - 1, isPalin, dp);
//                     int rightCuts = dp[cut][ei];    //minCut(str, cut, ei, isPalin, dp);

//                     int myCost = leftCuts + 1 + rightCuts;
//                     if (myCost < myans)
//                         myans = myCost;
//                 }
//                 dp[si][ei] = myans;
//             }
//         }
//     }
//     return dp[0][n - 1];
// }

//==============================================================================================================

//Leetcode :91. Decode Ways

int numDecodings_(string &s, int vidx, vector<int> &dp)
{
    if (vidx == s.length())
    {
        return dp[vidx] = 1;
    }
    if (dp[vidx] != -1)
        return dp[vidx];

    char ch = s[vidx];
    if (ch == '0')
        return dp[vidx] = 0;

    int count = 0;
    count += numDecodings_(s, vidx + 1, dp);
    if (vidx < s.size() - 1)
    {
        int num = (ch - '0') * 10 + (s[vidx + 1] - '0');
        if (num <= 26)
            count += numDecodings_(s, vidx + 2, dp);
    }

    return dp[vidx] = count;
}

int numDecodings02(string &s)
{

    int a = 0;
    int b = 1;

    int ans = 0;
    for (int i = s.length() - 1; i >= 0; i--)
    {
        char ch = s[i];
        ans = 0;
        if (ch != '0')
        {
            ans = b;
            if (i < s.length() - 1)
            {
                int num = (ch - '0') * 10 + (s[i + 1] - '0');
                if (num <= 26)
                    ans += a;
            }
        }

        a = b;
        b = ans;
    }
}

long mod = 1e9 + 7;
long numDecodingsII_recu(string &str, int idx, vector<long> &dp)
{
    if (idx == str.length())
        return 1;
    if (dp[idx] != 0)
        return dp[idx];

    int count = 0;
    if (str[idx] == '*')
    {
        count = (count % mod + 9 * numDecodingsII_recu(str, idx + 1, dp) % mod) % mod;
        if (idx < str.length() - 1 && str[idx + 1] >= '0' && str[idx + 1] <= '6')
            count = (count % mod + 2 * numDecodingsII_recu(str, idx + 2, dp) % mod) % mod;
        else if (idx < str.length() - 1 && str[idx + 1] >= '7')
            count = (count % mod + numDecodingsII_recu(str, idx + 2, dp) % mod) % mod;
        else if (idx < str.length() - 1 && str[idx + 1] == '*')
            count = (count % mod + 15 * numDecodingsII_recu(str, idx + 2, dp) % mod) % mod;
    }
    else if (str[idx] > '0')
    {

        count = (count % mod + numDecodingsII_recu(str, idx + 1, dp) % mod) % mod;
        if (idx < str.length() - 1)
        {
            if (str[idx + 1] != '*')
            {
                int num = (str[idx] - '0') * 10 + (str[idx + 1] - '0');
                if (num <= 26)
                    count = (count % mod + numDecodingsII_recu(str, idx + 2, dp) % mod) % mod;
            }
            else if (str[idx] == '1')
                count = (count % mod + 9 * numDecodingsII_recu(str, idx + 2, dp) % mod) % mod;
            else if (str[idx] == '2')
                count = (count % mod + 6 * numDecodingsII_recu(str, idx + 2, dp) % mod) % mod;
        }
    }
    return dp[idx] = count;
}

long numDecodingsII_DP(string &str, int idx, vector<long> &dp)
{
    for (idx = str.length(); idx >= 0; idx--)
    {
        if (idx == str.length())
        {
            dp[idx] = 1;
            continue;
        }

        int count = 0;
        if (str[idx] == '*')
        {
            count = (count % mod + 9 * dp[idx + 1] % mod) % mod;
            if (idx < str.length() - 1 && str[idx + 1] >= '0' && str[idx + 1] <= '6')
                count = (count % mod + 2 * dp[idx + 2] % mod) % mod;
            else if (idx < str.length() - 1 && str[idx + 1] >= '7')
                count = (count % mod + dp[idx + 2] % mod) % mod;
            else if (idx < str.length() - 1 && str[idx + 1] == '*')
                count = (count % mod + 15 * dp[idx + 2] % mod) % mod;
        }
        else if (str[idx] > '0')
        {

            count = (count % mod + dp[idx + 1] % mod) % mod;
            if (idx < str.length() - 1)
            {
                if (str[idx + 1] != '*')
                {
                    int num = (str[idx] - '0') * 10 + (str[idx + 1] - '0');
                    if (num <= 26)
                        count = (count % mod + dp[idx + 2] % mod) % mod;
                }
                else if (str[idx] == '1')
                    count = (count % mod + 9 * dp[idx + 2] % mod) % mod;
                else if (str[idx] == '2')
                    count = (count % mod + 6 * dp[idx + 2]) % mod;
            }
        }
        dp[idx] = count;
    }
    return dp[0];
}

long numDecodingsII_Fast(string &str, int idx, vector<long> &dp)
{
    long a = 0;
    long b = 1;
    long count = 0;
    for (idx = str.length() - 1; idx >= 0; idx--)
    {
        count = 0;
        if (str[idx] == '*')
        {
            count = (count % mod + 9 * b % mod) % mod;
            if (idx < str.length() - 1 && str[idx + 1] >= '0' && str[idx + 1] <= '6')
                count = (count % mod + 2 * a % mod) % mod;
            else if (idx < str.length() - 1 && str[idx + 1] >= '7')
                count = (count % mod + a % mod) % mod;
            else if (idx < str.length() - 1 && str[idx + 1] == '*')
                count = (count % mod + 15 * a % mod) % mod;
        }
        else if (str[idx] > '0')
        {

            count = (count % mod + b % mod) % mod;
            if (idx < str.length() - 1)
            {
                if (str[idx + 1] != '*')
                {
                    int num = (str[idx] - '0') * 10 + (str[idx + 1] - '0');
                    if (num <= 26)
                        count = (count % mod + a % mod) % mod;
                }
                else if (str[idx] == '1')
                    count = (count % mod + 9 * a % mod) % mod;
                else if (str[idx] == '2')
                    count = (count % mod + 6 * a) % mod;
            }
        }

        a = b;
        b = count;
    }
    return count;
}

// DP toDo :
// 1. 132
// 2. 044
// 3. https://www.geeksforgeeks.org/boolean-parenthesization-problem-dp-37/
// 4. 096
// 5. 095

// int numDecodings(string str)
// {
//     vector<long> dp(str.length() + 1, 0);
//     // return (int)numDecodingsII_recu(str, 0, dp);
//     // return (int)numDecodingsII_DP(str, 0, dp);
//     return (int)numDecodingsII_Fast(str, 0, dp);
// }

int numDecodings(string s)
{
    vector<int> dp(s.length() + 1, -1);
    int ans = numDecodings_(s, 0, dp);

    display(dp);
    return ans;
}

void questionSet()
{
    numDecodings("1423101112");
}

// gfg count aibjck subsequence.
int AiBjCk(string str)
{
    int acount = 0;
    int bcount = 0;
    int ccount = 0;
    for (int i = 0; i < str.length(); i++)
    {
        if (str[i] == 'a')
            acount = acount + (1 + acount);
        else if (str[i] == 'b')
            bcount = bcount + (acount + bcount);
        else
            ccount = ccount + (bcount + ccount);
    }

    return ccount;
}

// https://www.hackerearth.com/practice/math/number-theory/basic-number-theory-1/tutorial/

// (a+b)%c = (a%c + b%c)%c
// (a-b)%c = (a%c - b%c + c)%c
// (a*b)%c = (a%c * b%c )%c
int distinctSubseqII(string str)
{
    int mod = 1e9 + 7;
    str = '$' + str;
    int n = str.length();
    vector<long> dp(n, 0);
    vector<int> lastOccu(26, -1);

    for (int i = 0; i < n; i++)
    {
        if (i == 0) // empty String.
        {
            dp[i] = 1;
            continue;
        }

        char ch = str[i];
        dp[i] = (dp[i - 1] % mod * 2) % mod;
        if (lastOccu[ch - 'a'] != -1)
            dp[i] = dp[i] % mod - dp[lastOccu[ch - 'a'] - 1] % mod + mod;

        lastOccu[ch - 'a'] = i;
    }
    return dp[n - 1] % mod - 1;
}

void solve()
{
    // set1();
    // pathSet();
    //set2();
    // stringSubstringSet();
    // cutType();
    targetType();
    // MCM();
    // optimalBinarySearchTree();
}

int main()
{
    solve();
    return 0;
}<file_sep>/Recursion/l003_bits.cpp
#include <iostream>
#include <vector>
using namespace std;

int bitOFFToON(int no, int k)
{
    int mask = (1 << k);
    return (no | mask);
}

int bitONToOFF(int no, int k)
{
    int mask = (~(1 << k));
    return (no & mask);
}

int noOfSetBits(int num)
{
    int bitCount = 0;
    int totalBits = 32;

    while (num != 0 && totalBits != 0)
    {
        if ((num & 1) != 0)
            bitCount++;
        num >>= 1;
        totalBits--;
    }
    return bitCount;
}

// Leetcode 191
int noOfSetBits(int num)
{
    int bitCount = 0;
    int totalBits = 32;

    while (num != 0 && totalBits != 0)
    {
        if ((num & 1) != 0)
            bitCount++;
        num >>= 1;
        totalBits--;
    }
    return bitCount;
}

//leetcode 338
int noOfSetBits_01(int num)
{
    int bitcount = 0;
    while (num != 0)
    {
        num &= (num - 1);
        bitcount++;
    }
    return bitcount;
}

// LeetCode Qno : 137 ===============================
int singleNumber(vector<int> &nums)
{
    int no = 0;
    for (int i = 0; i < 32; i++)
    {
        int count = 0;
        int mask = (1 << i);
        for (int ele : nums)
        {
            if ((mask & ele) != 0)
            {
                count++;
            }
        }

        if (count % 3 != 0)
            no |= mask;
    }
    return no;
}

// LeetCode Qno : 260 =============================

vector<int> singleNumberII(vector<int> &nums)
{
    int Xnornum = 0;
    for (int ele : nums)
        Xnornum ^= ele;
    int flsb = (Xnornum & (-Xnornum));
    int a = 0;
    int b = 0;
    for (int ele : nums)
    {
        if ((ele & flsb) == 0)
            a ^= ele;
        else
            b ^= ele;
    }
    return {a, b};
}

//Leetcode Qn0 :231 ===============================

bool isPowerOfTwo(int n)
{

    return n > 0 && !(n & (n - 1));
}

//leetcode 342=========================
bool isPowerOfFour(int n)
{
    if (n > 0 && !(n & (n - 1))) // is num power of 2
    {
        int count = 0; // count of all zeros after 1.
        while (n > 1)
        {
            count++;
            n >>= 1;
        }

        if ((count & 1) == 0)
            return true; // count of zeros after 1 should be a even number.
    }

    return false;
}
void solve()
{
}

int main(int argc, char const *argv[])
{
    solve();
    return 0;
}
<file_sep>/Recursion/l001.cpp
#include <iostream>
#include <vector>
#include <string>
#define vi vector<int>
#define vii vector<vector<int>>

using namespace std;

vii dir = {{0, 1}, {1, 1}, {1, 0}};
vector<string> ch = {"H", "D", "V"};

int MazePath_HVD_01(vii &board, int sr, int sc,string ans)
{
   if (sr == board.size() - 1 && sc == board[0].size() - 1)
   {
      cout << ans << endl;
      return 1;
   }
   int count = 0;
   for (int d = 0; d < dir.size(); d++)
   {
      int nr = sr + dir[d][0];
      int nc = sc + dir[d][1];
      if (nr < board.size() && nc < board[0].size())
         count += MazePath_HVD_01(board, nr, nc, ans + ch[d]);
   }
   return count;
}

vector<string> MazePath_HVD_02(int sr, int sc, int er, int ec)
{
   if (sr == er && sc == ec)
   {
      return {""};
   }
   int count = 0;
   vector<string> myans;
   for (int d = 0; d < dir.size(); d++)
   {
      int nr = sr + dir[d][0];
      int nc = sc + dir[d][1];
      if (nr <= er && nc <= ec)
      {
         vector<string> smans = MazePath_HVD_02(nr, nc, er, ec);
         for (string ele : smans)
            myans.push_back(ch[d] + ele);
      }
   }
   return myans;
}

vector<vector<int>> dir = {{0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}};
vector<string> dirN = {"R", "E", "U", "N", "L", "W", "D", "S"};

// vector<vector<int>> dir = {{0, 1}, {1, 0}, {1, 1}};
// vector<string> dirN = {"H", "V", "D"};

bool isValid(int r, int c, vector<vector<int>> &board)
{
   if (r < 0 || c < 0 || r >= board.size() || c >= board[0].size() || board[r][c] == 0 || board[r][c] == 2)
      return false;

   return true;
}

int floodFill(int sr, int sc, int er, int ec, vector<vector<int>> &board, int rad, string ans)
{
   if (sr == er && sc == ec)
   {
      cout << ans << endl;
      return 1;
   }

   int count = 0;
   board[sr][sc] = 2;

   for (int d = 0; d < dir.size(); d++)
   {
      for (int mag = 1; mag <= rad; mag++)
      {
         int r = sr + mag * dir[d][0];
         int c = sc + mag * dir[d][1];
         if (isValid(r, c, board))
            count += floodFill(r, c, er, ec, board, rad, ans + dirN[d] + to_string(mag));
      }
   }

   board[sr][sc] = 1;
   return count;
}

//leetcode 200.
// int numIslands(vector<vector<char>> &arr)
// {
//    int count = 0;
//    for (int r = 0; r < arr.size(); r++)
//    {
//       for (int c = 0; c < arr[0].size(); c++)
//       {
//          if (arr[r][c] == '1')
//          {
//             count++;
//             floodFill(r, c, arr, 1);
//          }
//       }
//    }

//    return count;
// }

vector<vector<int>> dir_ = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};

bool isValid_(int r, int c, vector<vector<char>> &board)
{
   if (r < 0 || c < 0 || r >= board.size() || c >= board[0].size() || board[r][c] == '0' || board[r][c] == '2')
      return false;

   return true;
}

int dfs(int sr, int sc, vector<vector<char>> &board, int rad)
{
   int count = 0;
   board[sr][sc] = '2';

   for (int d = 0; d < dir.size(); d++)
   {
      for (int mag = 1; mag <= rad; mag++)
      {
         int r = sr + mag * dir_[d][0];
         int c = sc + mag * dir_[d][1];
         if (isValid_(r, c, board))
            count += dfs(r, c, board, rad);
      }
   }

   // board[sr][sc] = 1;
   return count;
}
void MazePathSet()
{
   vii board(3, vi(3));
   // cout << MazePath_HVD_01(board, 0, 0, "") << endl;
   // vector<string> ans = MazePath_HVD_02(0, 0, 2, 2);
   // for(string ele : ans)
   //    cout << ele << endl;
}

int main(int argc, char const *argv[])
{
   MazePathSet();
   return 0;
}
<file_sep>/Practice/Dp/l001.cpp
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define vi vector<int>
#define vb vector<bool>
#define lli long long int
#define vvi vector<vector<int>>
using namespace std;

// www.geeksforgeeks.org/dynamic-programming-set-11-egg-dropping-puzzle/
int minSteps(int n, int k, vvi &dp)
{
    if (k == 0 || k == 1)
        return dp[n][k] = k;

    if (n == 1)
        return dp[n][k] = k;

    int myans = -1e9, ans = 1e9;
    for (int i = 1; i <= k; i++)
    {
        myans = max(minSteps(n - 1, k - 1, dp), minSteps(n, k - i, dp));
        if (ans > myans)
            ans = myans;
    }
    dp[n][k] = ans + 1;
}

int EggDops()
{
    int n, k;
    cin >> n >> k;
    vvi dp(n + 1, vi(k + 1, -1));
    return minSteps(n, k, dp);
}

// Leetcode 96.
int numTrees(int n)
{
    //Catlan no solution
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            dp[i] += dp[j] * dp[i - 1 - j];
        }
    }
    return dp[n];
}

int findLongestRepeatingSubSeq(string &X, int m, int n, vvi &dp)
{

    if (dp[m][n] != -1)
        return dp[m][n];

    // return if we have reached the end of either string
    if (m == 0 || n == 0)
        return dp[m][n] = 0;

    // if characters at index m and n matches
    // and index is different
    if (X[m - 1] == X[n - 1] && m != n)
        return dp[m][n] = findLongestRepeatingSubSeq(X,
                                                     m - 1, n - 1, dp) +
                          1;

    // else if characters at index m and n don't match
    return dp[m][n] = max(findLongestRepeatingSubSeq(X, m, n - 1, dp),
                          findLongestRepeatingSubSeq(X, m - 1, n, dp));
}

int solve()
{
    int n;
    cin >> n;
    string str;
    cin >> str;
    string rstr = string(str.rbegin(), str.rend());
    vvi dp(n + 1, vi(n + 1, -1));
    return findLongestRepeatingSubSeq(str, n, n, dp);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        cout << solve() << endl;
    }
    return 0;
}<file_sep>/Practice/largestRectangleArea.cpp
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define vi vector<int>
#define vb vector<bool>
#define lli long long int
#define vvi vector<vector<int>>
#define loop(n) for (int i = 0; i < n; i++)
using namespace std;

int largestAreaInHistogram(vi &arr)
{
    int maxArea = 0;
    stack<int> st;
    st.push(-1);
    int n = arr.size();
    for (int i = 0; i < n; i++)
    {
        while (st.top() != -1 && arr[st.top()] >= arr[i])
        {
            int h = arr[st.top()];
            st.pop();
            maxArea = max(maxArea, h * (i - st.top() - 1));
        }
        st.push(i);
    }

    while (st.top() != -1)
    {
        int h = arr[st.top()];
        st.pop();
        maxArea = max(maxArea, h * (n - st.top() - 1));
    }
    return maxArea;
}

int solve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> board(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> board[i][j];

    for (int i = 1; i < n; i++) // building the board to run maxAreaInHistogram on each.
        for (int j = 0; j < m; j++)
            if (board[i][j] == 1)
                board[i][j] += board[i - 1][j];

    int myans = 0;

    for (vi &arr : board)
        myans = max(myans, largestAreaInHistogram(arr));

    return myans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        cout << solve() << endl;
    }
    return 0;
}<file_sep>/Graph/Leetcode.java
import java.util.LinkedList;
import java.util.ArrayList;
public class Leetcode {


    public static void main(String[] args) {
        //    int[][] matrix = { { 0, 0, 0 }, { 0, 1, 0 }, { 1, 1, 1 } };
        //    int[][] ans = updateMatrix(matrix);

        //    for(int[] row : ans)
        //    {
        //        for(int el : row)
        //            System.out.print(el + " ");
        //        System.out.println();

        int[][] ar = { { 1, 0 } };
        for (int[] row : ar)
        System.out.println(row[0]+" "+row[1]);
        System.out.println(canFinish(2,ar));
    }
       


    public static void solve(char[][] board) {
        // surroundRegions(board);
       
    }

    // LeetCode 130 Surronding Regions==================
    void mark(char[][] board, int r, int c, int n, int m) {
        if (board[r][c] != 'O')
            return;

        board[r][c] = '#';
        if (r + 1 < n)
            mark(board, r + 1, c, n, m);
        if (c + 1 < m)
            mark(board, r, c + 1, n, m);
        if (r - 1 >= 0)
            mark(board, r - 1, c, n, m);
        if (c - 1 >= 0)
            mark(board, r, c - 1, n, m);
    }

    void surroundRegions(char[][] board) {
        if (board.length == 0)
            return;

        int n = board.length;
        int m = board[0].length;

        for (int i = 0; i < m; i++) {
            if (board[0][i] == 'O')
                mark(board, 0, i, n, m);
            if (board[n - 1][i] == 'O')
                mark(board, n - 1, i, n, m);
        }

        for (int i = 0; i < n; i++) {
            if (board[i][0] == 'O')
                mark(board, i, 0, n, m);
            if (board[i][m - 1] == 'O')
                mark(board, i, m - 1, n, m);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
                else if (board[i][j] == '#')
                    board[i][j] = 'O';
            }
        }
    }

    // qno 542
    public static int[][] updateMatrix(int[][] matrix) {

        int n = matrix.length;
        if (n == 0)
            return matrix;
        int m = matrix[0].length;
        if (m == 0)
            return matrix;

        LinkedList<int[]> que = new LinkedList<>();
        // que.addLast(new int[] { matrix[0][0] });

        int dir[][] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
        boolean[] vis = new boolean[n * m];

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (matrix[i][j] == 0) {
                    que.addLast(new int[] { i * m + j, 0 });
                    break;
                }

        // int[] pair = que.getFirst();
        // System.out.println(pair[0]);
        // System.out.println(pair[1]);

        while (que.size() != 0) {
            int size = que.size();
            while (size-- > 0) {
                int[] rvtx = que.removeFirst();

                int r = rvtx[0] / m;
                int c = rvtx[0] % m;
                int level = rvtx[1];

                for (int d = 0; d < 4; d++) {
                    int x = r + dir[d][0];
                    int y = c + dir[d][1];
                    if (x >= 0 && y >= 0 && x < n && y < m && (vis[x * m + y]==false)) {
                        if (matrix[x][y] == 0) {
                            que.addLast(new int[] { x * m + y, 0 });
                        } else {
                            que.addLast(new int[] { x * m + y, level + 1 });
                            matrix[x][y] = level+1;
                        }
                        vis[x*m+y] = true; //needed to mark inside.
                    }
                }
            }
        }
        return matrix;
    }

    //207
    public static boolean canFinish(int numCourses, int[][] prerequisites) {

        int n = prerequisites.length;
        if (n == 0)
            return true;

        ArrayList<Integer> graph[] = new ArrayList[numCourses];
        for (int i = 0; i < numCourses; i++)
            graph[i] = new ArrayList<Integer>();

        for (int[] row : prerequisites)
            graph[row[0]].add(row[1]);

        int[] indegree = new int[numCourses];
        LinkedList<Integer> que = new LinkedList<>();
        ArrayList<Integer> ans = new ArrayList<>();

        for (int[] row : prerequisites)
            indegree[row[1]]++;

        for (int i = 0; i < numCourses; i++)
            if (indegree[i] == 0)
                que.addLast(i);

        while (que.size() != 0) {
            int size = que.size();
            while (size-- > 0) {
                int rvtx = que.removeFirst();
                ans.add(rvtx);

                for (int e : graph[rvtx])
                    if (--indegree[e] == 0)
                        que.addLast(e);
            }
        }

        return ans.size() == numCourses ? true : false;

    }

    //210
    public int[] findOrder(int numCourses, int[][] prerequisites) {

        int n = prerequisites.length;
        if (n == 0) {
            int[] ar = new int[numCourses];
            int idx = 0;
            for (int i = numCourses - 1; i >= 0; i--)
                ar[idx++] = i;
            return ar;
        }
        if (prerequisites[0].length == 0)
            return new int[] { 0 };
        ArrayList<Integer> graph[] = new ArrayList[numCourses];
        for (int i = 0; i < numCourses; i++)
            graph[i] = new ArrayList<>();

        for (int[] row : prerequisites)
            graph[row[0]].add(row[1]);

        int[] indegree = new int[numCourses];
        LinkedList<Integer> que = new LinkedList<>();
        ArrayList<Integer> ans = new ArrayList<>();

        for (int[] row : prerequisites)
            indegree[row[1]]++;

        for (int i = 0; i < numCourses; i++)
            if (indegree[i] == 0)
                que.addLast(i);

        while (que.size() != 0) {
            int size = que.size();
            while (size-- > 0) {
                int rvtx = que.removeFirst();
                ans.add(rvtx);

                for (int e : graph[rvtx])
                    if (--indegree[e] == 0)
                        que.addLast(e);
            }
        }

        if (ans.size() != numCourses)
            return new int[0];
        else {
            int[] arr = new int[ans.size()];
            int idx = 0;
            for (int i = ans.size() - 1; i >= 0; i--)
                arr[idx++] = ans.get(i);
            return arr;
        }

    }

    //329
    
    int[][] dir = { { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 0 } };

    public int longestIncreasingPath(int[][] matrix) {

        int n = matrix.length;
        if (n == 0)
            return 0;
        int m = matrix[0].length;
        if (m == 0)
            return 0;
        int[][] dp = new int[n][m];
        int[][] dp_ = new int[n][m];

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                for (int d = 0; d < 4; d++) {
                    int x = i + dir[d][0];
                    int y = j + dir[d][1];
                    if (x < n && y < m && x >= 0 && y >= 0 && matrix[i][j] > matrix[x][y])
                        dp[i][j]++;
                }
            }

        int maxLen = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                if (dp[i][j] == 0)
                    maxLen = Math.max(dfs(i, j, n, m, matrix, dp_), maxLen);
            }

        return maxLen;

    }

    int dfs(int sr, int sc, int n, int m, int[][] matrix, int[][] dp) {
        if (dp[sr][sc] != 0)
            return dp[sr][sc];

        int count = 0;
        for (int d = 0; d < 4; d++) {
            int x = sr + dir[d][0];
            int y = sc + dir[d][1];
            if (x < n && y < m && x >= 0 && y >= 0 && matrix[sr][sc] < matrix[x][y])
                count = Math.max(dfs(x, y, n, m, matrix, dp), count);
        }
        dp[sr][sc] = count + 1;
        return count + 1;
    }

}<file_sep>/Graph/l003_UnionFind.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
class Edge
{
public:
    int v = 0;
    int w = 0;

    Edge(int v, int w)
    {
        this->v = v;
        this->w = w;
    }
};

int N = 7;
vector<vector<Edge>> graph(N, vector<Edge>());

void addEdge(vector<vector<Edge>> &gp, int u, int v, int w)
{
    gp[u].push_back(Edge(v, w));
    gp[v].push_back(Edge(u, w));
}

//unionFind.==============================================

// vector<int> par;
// vector<int> setSize;

// //path compression code =================================
// int findPar(int vtx)
// {
//     if (par[vtx] == vtx)
//         return vtx;
//     return par[vtx] = findPar(par[vtx]);
// }

// void mergeSet(int l1, int l2)
// {
//     if (setSize[l1] < setSize[l2])
//     {
//         par[l1] = l2;
//         setSize[l2] += setSize[l1];
//     }
//     else
//     {
//         par[l2] = l1;
//         setSize[l1] += setSize[l2];
//     }
// }

// void unionFind()
// {
// }

void display(vector<vector<Edge>> &gp)
{
    for (int i = 0; i < gp.size(); i++)
    {
        cout << i << "-> ";
        for (Edge e : gp[i])
        {
            cout << "(" << e.v << "," << e.w << ") ";
        }
        cout << endl;
    }
    cout << endl;
}

void constructGraph()
{
    addEdge(graph, 0, 1, 10);
    addEdge(graph, 0, 3, 10);
    addEdge(graph, 1, 2, 10);
    addEdge(graph, 2, 3, 40);
    addEdge(graph, 3, 4, 2);
    addEdge(graph, 4, 5, 2);
    addEdge(graph, 4, 6, 3);
    addEdge(graph, 5, 6, 8);

    // addEdge(graph, 2, 5, 2);

    // display(graph);
    cout << endl;
}


//Kruskal Algo for finding Minimumm cost Spanning Tree using union find
vector<int> par;
vector<int> setSize;

int findPar(int vtx)
{
    if (par[vtx] == vtx)
        return vtx;
    return par[vtx] = findPar(par[vtx]);
}

void mergeSet(int p1, int p2)
{
    if (setSize[p1] < setSize[p2])
    {
        par[p1] = p2;
        setSize[p2] += setSize[p1];
    }
    else
    {
        par[p2] = p1;
        setSize[p1] += setSize[p2];
    }
}

void Kruskal(vector<vector<int>> &arr)
{
    vector<vector<Edge>> Kruskalgraph(arr.size(), vector<Edge>());

    sort(arr.begin(), arr.end(), [](vector<int> &a, vector<int> &b) {
        return a[2] < b[2]; // this - other,default is Increasing, '-' replace with '<'
    });

    for (vector<int> &ar : arr)
    {
        int u = ar[0];
        int v = ar[1];

        int p1 = findPar(u);
        int p2 = findPar(v);
        if (p1 != p2)
        {
            mergeSet(p1, p2);
            addEdge(Kruskalgraph, u, v, ar[2]);
        }
    }

    display(Kruskalgraph);
}

void solve()
{
    constructGraph();
}

int main()
{
    solve();
    return 0;
}
<file_sep>/Practice/Kmp.cpp
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define vi vector<int>
#define vb vector<bool>
#define lli long long int
#define vvi vector<vector<int>>
#define loop(n) for (int i = 0; i < n; i++)
using namespace std;

auto SpeedUp = []() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 0;
}();

void computLps(vi& lps, string p)
{
    int n = p.size();
    lps[0] = 0;
    int i = 1, j=0;
    while (i<n)
    {
        if (p[j]==p[i])
        {
            lps[i] = j+1;
            i++;j++;
        }
        else
        {
            if (j!=0)
                j = lps[j-1];
            else
            {
                lps[i] = 0;
                i++;
            }
        }

    }
}

void KMP()
{
    string text, pattern;
    cin>>text>>pattern;

    int n = text.size(), m =pattern.size();

    vi lps(m, 0);
    computLps(lps, pattern);

    int i=0, j=0;
    while (i<n)
    {
        if (pattern[j]==text[i])
        {
            j++;i++;
        }
        if (j==m)
        {
            cout<<"Found Pattern at"<<(i-j)<<endl;
            j = lps[j-1];
        }
        else if(i<n && pattern[j]!=text[i])
        { 
            if (j!=0)
                j = lps[j-1];
            else
                i++;
        }
    }
}

int main()
{
    int t;
    cin >> t;
    while (t--)
        KMP();
    return 0;
}<file_sep>/Practice/SegmentTree.cpp
#include "bits/stdc++.h"
#define vi vector<int>
#define vb vector<bool>
#define lli long long int
#define vvi vector<vector<int>>
#define loop(n) for (int i = 0; i < n; i++)
using namespace std;

auto SpeedUp = []() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 0;
}();

// segment tree ane different queries on them.
// at max ST takes O(4n) space ans at max O(4longn) search queries time. used array to represent ST
// they ineffective when we have so many updates on the array.
void constructST(vi &arr, vi &segTree, int low, int high, int pos)
{
    if (low == high)
    {
        segTree[pos] = arr[low];
        return;
    }
    int mid = (low + high) / 2;
    constructST(arr, segTree, low, mid, 2 * pos + 1);
    constructST(arr, segTree, mid + 1, high, 2 * pos + 2);
    segTree[pos] = min(segTree[2 * pos + 1], segTree[2 * pos + 2]);
}

int rangeMinQurey(vi &segTree, int l, int r, int low, int high, int pos) // range queries use total overlap, partial overrlap,no overlap method;
{
    if (l <= low && r >= high)
        return segTree[pos]; // total overlap condition;

    if (l > high || r < low)
        return 1e9; // no overlap;

    int mid = (low + high) / 2; //partial overlap condition;
    return min(rangeMinQurey(segTree, l, r, low, mid, 2 * pos + 1), rangeMinQurey(segTree, l, r, mid + 1, high, 2 * pos + 2));
}

void solve()
{
    int n = 4;
    vi arr = {-1, 0, 3, 6};
    //Height of segment tree
    int x = (int)(ceil(log2(n)));

    //Maximum size of segment tree
    int size = 2 * (int)pow(2, x) - 1;

    vi segTree(size, (int)1e9);

    constructST(arr, segTree, 0, n - 1, 0); //function to construct the segment tree;

    int querie;
    cin >> querie;
    int l, r;
    while (querie--)
    {
        cin >> l >> r;
        cout << rangeMinQurey(segTree, l, r, 0, n - 1, 0); // running queries on segtree lakes queries*long(n) time total;
    }
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}<file_sep>/Practice/Dp/largestSquareInMatrix.cpp
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define vi vector<int>
#define vb vector<bool>
#define lli long long int
#define vvi vector<vector<int>>
#define loop(n) for (int i = 0; i < n; i++)
using namespace std;

int omax;
int largetSquareInMatrix(int sr, int sc, vvi &board, vvi &dp)
{
    if (sr == board.size() || sc == board[0].size())
        return 0;
    if (dp[sr][sc] != -1)
        return dp[sr][sc];

    int myans = 0;
    int right = largetSquareInMatrix(sr, sc + 1, board, dp);
    int diag = largetSquareInMatrix(sr + 1, sc + 1, board, dp);
    int down = largetSquareInMatrix(sr + 1, sc, board, dp);
    if (board[sr][sc] == 1)
        myans = min({right, down, diag}) + 1;
    omax = max(omax, myans);
    return dp[sr][sc] = myans;
}

int largetSquareInMatrix_DP(vvi &board)
{

    int omax = 0, n = board.size(), m = board[0].size();
    vvi dp(n, vi(m, 0));
    for (int i = n - 1; i >= 0; i--)
    {
        for (int j = m - 1; j >= 0; j--)
        {

            if (board[i][j] == 1)
                dp[i][j] = min({dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1]}) + 1;
            omax = max(omax, dp[i][j]);
        }
    }
    return omax;
}

int solve()
{
    omax = 0;
    int n, m;
    cin >> n >> m;
    vector<vector<int>> board(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> board[i][j];
    // vvi dp(n, vi(m, -1));
    // largetSquareInMatrix(0, 0, board, dp);
    // return omax;
    return largetSquareInMatrix_DP(board);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        cout << solve() << endl;
    }
    return 0;
}<file_sep>/Practice/painterPartition.cpp
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define vi vector<int>
#define vb vector<bool>
#define lli long long int
#define vvi vector<vector<int>>
#define loop(n) for (int i = 0; i < n; i++)
using namespace std;

auto SpeedUp = []() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 0;
}();

// binary search didn't produce the correct result for some testcases;
bool isCanPaint(vi& arr, int mid, int p)
{
    int sum = 0, reqp=1;
    for (int i=0;i<arr.size();i++)
    {
        if (sum>mid)
        {
            sum = 0;
            reqp++;
            if (reqp>p)
                return false;
        }
        sum+=arr[i];
    }
    return true;
}

int painterPartition(vi& arr, int n, int p)
{
    int si = 0, ei = 0;
    loop(n) ei +=arr[i];
    int ans = 0;
    while (si<=ei)
    {
        int mid = (si+ei)/2;

        if (isCanPaint(arr, mid, p))
        {
            ei = mid - 1;
            ans = mid;
        }
        else
            si = mid+1;
    }

    return ans;
}

int solve()
{
    int k, n;
    cin>>k>>n;
    vi arr(n);
    loop(n) cin>>arr[i];
    
    vvi dp(k+1, vi(n+1, 0)); //using dp method to get correct ans;

    for (int i=1;i<=n;i++)
        dp[1][i] = dp[1][i-1] + arr[i-1];
    for (int j =1;j<=k;j++)
        dp[j][1] = arr[0];

    for(int i=2;i<=k;i++)    
    { 
        for(int j = 2;j<=n;j++)
        { 
            int ans = 1e8;
            int sum = 0;
            for(int z = j;z>=1;z--)
            { 
                sum +=arr[z-1];
                ans = min(ans, max(dp[i-1][z-1], sum));
            }

            dp[i][j] = ans;
        }
    }

    // for(vi& ar:dp)
    // { 
    //     for (int ele : ar)
    //         cout<<ele<<" ";
    //     cout<<endl;
    // }
    return dp[k][n];
    // return painterPartition(arr, n, p);
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        cout << solve() << endl;
    }
    return 0;
}<file_sep>/Practice/Dp/1Kansack.cpp
#include "bits/stdc++.h"
#define vi vector<int>
#define vb vector<bool>
#define lli long long int
#define vvi vector<vector<int>>
#define loop(n) for (int i = 0; i < n; i++)
using namespace std;

auto SpeedUp = []() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    // std::ios::sync_with_stdio(false);
    // cin.tie(nullptr);
    // cout.tie(nullptr);
    return 0;
}();

//  code for 0/1 kanpsack using idx and value to store min weigth req to get that value;
int knapSack(vi &weg, vi &value, int n, int w, int tval, vector<vector<lli>> &dp)
{
    //dp[idx][val] = it will store the min weght to require to get this value;
    dp[0][0] = 0;
    for (int idx = 1; idx <= n; idx++)
    {
        dp[idx][0] = 0; // by not thaking any object thus obtaning 0 value;
        for (int val = 1; val <= tval; val++)
        {
            dp[idx][val] = dp[idx - 1][val]; //not taking current object;

            if (val >= value[idx - 1])
                dp[idx][val] = min(dp[idx][val], dp[idx - 1][val - value[idx - 1]] + weg[idx - 1]);
        }
    }

    for (int val = tval; val >= 0; val--)
        if (dp[n][val] <= w)
            return val;
}

int solve()
{
    int n, w;
    scanf("%d%d", &n, &w);
    vi weg(n, 0), val(n, 0);
    int tval = 0;
    loop(n)
    {
        scanf("%d", &weg[i]);
        scanf("%d", &val[i]);
        tval += val[i];
    }

    vector<vector<lli>> dp(n + 1, vector<lli>(tval + 1, 1e9));
    return knapSack(weg, val, n, w, tval, dp);
}

int main()
{

    printf("%d\n", solve());
    return 0;
}