GeeksForGeeks - POTD | GFG POTD Answer

class Solution {
  public:
    vector<int> constructList(int q, vector<vector<int>> &queries) {
        // t.me/geeksforgeeks_POTD
         int val=0;
        vector<int>ans;
        for(int i=q-1;i>=0;i--)
        {
            int x=queries[i][1];
            if(queries[i][0]==0) {x^=val; ans.push_back(x);}
            else val^=x;
        }
        ans.push_back(val);
        sort(ans.begin(),ans.end());
        return ans;
    }
};

class Solution {
  public:
    int swapNibbles(int n) {
        
        //t.me/geeksforgeeks_potd

        int a = n&15;
        int b = n&240;
        b=b>>4;
        a=a<<4;
        return a+b;
    }
};

class Solution {
  public:
    int mod=1e9+7;
    int countWays(string s1, string s2) {
        int n1=s1.size();
        int n2=s2.size();
        vector<vector<int>> dp(n1+1,vector<int>(n2+1,0));
        
        for(int i=0;i<=n1;i++)
        dp[i][0]=1;
        for(int i=1;i<=n1;i++)
        {
            for(int j=1;j<=n2;j++)
            {
                if(s1[i-1]==s2[j-1])
                {
                    dp[i][j]=dp[i-1][j-1];
                }
                dp[i][j]+=dp[i-1][j];
                dp[i][j]%=mod;
            }
        }
        return dp[n1][n2];
    }
};

class Solution {
  public:
    int solve(int n, int x, int y, vector<int> &dp)
    {
        if(n <= 1)
            return n;
        if(dp[n] != -1)
            return dp[n];
        int ans = 1;
        if(n >= x)
            ans &= solve(n - x, x, y, dp);
        if(n >= y)
            ans &= solve(n - y, x, y, dp);
        ans &= solve(n - 1, x, y, dp);
        return dp[n] = ans ^ 1;
    }
    int findWinner(int n, int x, int y) {
        vector<int> dp(n + 1, -1);
        return solve(n, x, y, dp);
    }
};

class Solution {
  public:
    int minimumCost(int n, int w, vector<int> &cost) {
        
        vector<int> prev(w+1, 1e8);
        vector<int> curr(w+1, 1e8);
        prev[0] = curr[0] = 0;
        
        for(int i = 1; i <= n; i++){
            curr[0] = 0;
            for(int k = 0; k <= w; k++){
                int nontake = prev[k];
                int take = 1e8;
                if(cost[i-1] != -1 && i <= k){
                    take = cost[i-1] + curr[k-i];
                }
                curr[k] = min(take, nontake);
            }
            prev = curr;
        }
        if(prev[w] == 1e8) return -1;
        return prev[w];
    }
};

class Solution {
  public:
    int longestSubseq(int n, vector<int> &a) {
        unordered_map<int,int>mp;
        int mx = 0;
        for(int i = 0; i < n; i ++){
            int l = a[i] - 1;
            int r = a[i] + 1;
            mp[a[i]] = 1 + max(mp[l], mp[r]);
            mx = max(mx, (int)mp[a[i]]);
        }
        return mx;
        
    }
};

class Solution {
public:
    int findMinCost(string x, string y, int costX, int costY) {
        int n = x.size(), m = y.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(x[i - 1] == y[j - 1])
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        
        int lcs = dp[n][m];
        int xLen = (n - lcs) * costX;
        int yLen = (m - lcs) * costY;
        
        return xLen + yLen;
    }
};

class Solution {
  public :
    long long max_Books(int arr[], int n, int k) {
        long long sum = 0, max_sum = 0;
        
        for(int i = 0; i < n; i++)
        {
            sum = 0;
            if(arr[i] > k)
                continue;
            else
            {
                while(i < n && arr[i] <= k)
                {
                    sum += arr[i];
                    i++;
                }
                max_sum = max(max_sum, sum);
            }
        }
        return max_sum;
    }
};