GeeksForGeeks - POTD | GFG POTD Answer

class Solution{
    public:
    long long solve(int i, int n, int arr[], vector<vector<long long>>& dp) {
        if(i > n)
            return 0;
        if(dp[i][n] != -1)
            return dp[i][n];
        long long ans1 = arr[i] + min(solve(i + 1, n - 1, arr, dp), solve(i + 2, n, arr, dp));
        long long ans2 = arr[n] + min(solve(i + 1, n - 1, arr, dp), solve(i, n - 2, arr, dp));
        return dp[i][n] = max(ans1, ans2);
    }
    long long maximumAmount(int n, int arr[]){
        
        vector<vector<long long>> dp(n + 2, vector<long long>(n + 2, -1));
        return solve(0, n - 1, arr, dp);
    }
};

class Solution{
 public:
 int maxDotProduct(int n, int m, int a[], int b[]) {
 int res[m+1] = {};
 for(int i=0;i<n;i++) {
     for(int j=min(m,i+1);j>0;j--)
         res[j] = max(res[j],a[i]*b[j-1]+res[j-1]);
 }
 return res[m];
}
};

class Solution {
  public:
  long long countWays(int n)
    {
        long long ans=1;
        while(n>=2)
        {
            n=n-2;
            ans+=1;
        }
        return ans;
        
    }
};

class Solution {
  public:

    int min_operations(vector<int>& nums) 
    {
    int n = nums.size();
    vector<int> dp(n,1);
    int LIS=1;
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(nums[i]>nums[j] && (nums[i]-nums[j])>=(i-j))
            {
                dp[i] = max(1+dp[j],dp[i]);
                LIS = max(LIS,dp[i]);
            }
        }
    }
    return (n-LIS);
}
};

class Solution{
    public:
    int mod = 1e9+7;
    long long sumSubstrings(string s)
    {
        int n= s.size();
        vector<long long> dp(n,0);
        dp[0] = s[0]-'0';
        long long ans = dp[0];
        for(int i=1;i<n;i++)
        {
            dp[i] = ((dp[i-1]*10)%mod + ((s[i]-'0')*(i+1))%mod)%mod;
            ans = (ans + dp[i])%mod;
        }
        return ans;
    }
};

class Solution
{
    public:
    void getParent(Node* root, map<Node*, Node*> &m)
    {
        if(root==NULL) return;
        if(root->left){
            m[root->left] = root;
            getParent(root->left, m);
        }
        if(root->right){
            m[root->right] = root;
            getParent(root->right, m);
        }
    }
    Node* LCA(Node* root, int p, int q){
        if(root==NULL){
            return NULL;
        }
        if(root->data==p){
            return root;
        }
        if(root->data==q){
            return root;
        }
        Node* l = LCA(root->left, p, q);
        Node* r = LCA(root->right, p, q);
        if(l==NULL){
            return r;
        }
        if(r==NULL ){
            return l;
        }
        return root;
    }

    int kthCommonAncestor(Node *root, int k,int x, int y)
    {
      
        if(root==NULL) return -1;
        Node *lca = LCA(root, x, y);
        map<Node*, Node*> m;
        m[root] = NULL;
        getParent(root, m);
        if(lca==NULL) return -1;
        while(--k){
            lca = m[lca];
            if(lca==NULL) return -1;
        }
        return lca->data;
    }
};

class Solution
{
    void inOrder(Node* root , vector<int>& arr){
        if(root == nullptr) return;

        inOrder(root->left , arr);
        arr.push_back(root->data);
        inOrder(root->right , arr);
    }

    public:
    int absolute_diff(Node *root)
    {
        
        int ans = INT_MAX;
        vector<int> arr;
        inOrder(root , arr);
        
        for(int i = 0 ; i < arr.size()-1 ; i++){
            ans = min(ans , abs(arr[i]-arr[i+1]));
        }
        return ans;
    }
};

class Solution {
  public:
void fun(Node* root, vector<int>& v) {
    if (!root) return;
    fun(root->left, v);
     v.push_back(root->data);
    fun(root->right, v);
}

void merge(vector<int>& v, int l, int mid, int r, int& count) {
    vector<int> ans(r - l + 1);
    int left = l, right = mid + 1, k = 0;
    while (left <= mid && right <= r) {
        if (v[left] <= v[right]) {
            ans[k++] = v[left++];
        } else {
            ans[k++] = v[right++];
            count += (mid - left + 1); // Count inversions
        }
    }
    while (left <= mid) {
        ans[k++] = v[left++];
    }
    while (right <= r) {
        ans[k++] = v[right++];
    }
    for (int i = 0; i < k; i++) {
        v[l + i] = ans[i];
    }
}

void mergeSortAndCount(vector<int>& v, int l, int r, int& count) {
    if (l < r) {
        int mid = l + (r - l) / 2;
        mergeSortAndCount(v, l, mid, count);
        mergeSortAndCount(v, mid + 1, r, count);
        merge(v, l, mid, r, count);
    }
}

int pairsViolatingBST(int n, Node *root) {
    vector<int> v;
    fun(root, v);
    int count = 0;
    mergeSortAndCount(v, 0, n - 1, count);
    return count;
}

};

class Solution {
  public:
    int ans=-1;
    int findMaxForN(Node* root, int n) {
        
        if(root==NULL)
        return 0;
        if(root->key<=n)
        ans=max(ans,root->key);
        findMaxForN(root->left,n);
        findMaxForN(root->right,n);
        return ans;
    }
};