LeetCode, GeeksForGeeks Problem of the day solution

class MyQueue { public: stack<int> s1; stack<int> s2; /** Initialize your data structure here. */ MyQueue() { } /** Push element x to the back of queue. */ void push(int x) { while(!s1.empty()) { s2.push(s1.top()); s1.pop(); } s2.push(x); while(!s2.empty()) { s1.push(s2.top()); s2.pop(); } } /** Removes the element from in front of queue and returns that element. */ int pop() { int curr = s1.top(); s1.pop(); return curr; } /** Get the front element. */ int peek() { return s1.top(); } /** Returns whether the queue is empty. */ bool empty() { return s1.empty(); } };

class Solution{ public: int solve(string &str,int idx,int prev,vector>&dp) { if(idx==str.size()) { return 1; } if(dp[idx][prev]!=-1) { return dp[idx][prev]; } int ans=0; int sum=0; for(int i=idx;i=prev) { ans+=solve(str,i+1,sum,dp); } } return dp[idx][prev]=ans; } int TotalCount(string str){ // Code here int n=str.size(); vector>dp(n,vector(1000,-1)); return solve(str,0,0,dp); } };

class Solution { public: int numSubmatrixSumTarget(vector>& A, int target) { int res = 0, m = A.size(), n = A[0].size(); for (int i = 0; i < m; i++) for (int j = 1; j < n; j++) A[i][j] += A[i][j - 1]; unordered_map counter; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { counter = {{0,1}}; int cur = 0; for (int k = 0; k < m; k++) { cur += A[k][j] - (i > 0 ? A[k][i - 1] : 0); res += counter.find(cur - target) != counter.end() ? counter[cur - target] : 0; counter[cur]++; } } } return res; } };

class Solution { public: long long findNthNumber(long long n, int k) { long long low = 0, high = pow(10, 18); dp = std::vector>>(2, std::vector>(65, std::vector(65, -1))); while (low <= high) { long long mid = low + (high - low) / 2; long long count = find(mid, k); if (count >= n) { high = mid - 1; } else { low = mid + 1; } } return low; } long long find(long long n, int k) { std::string s = std::bitset<64>(n).to_string(); reset(); return dpf(s, s.length(), 1, k); } long long dpf(const std::string &s, int n, int tight, int k) { if (k < 0) { return 0; } if (n == 0) { return 1; } if (dp[tight][k][n] != -1) { return dp[tight][k][n]; } int ub = (tight == 1) ? s[s.length() - n] - '0' : 1; long long ans = 0; for (int dig = 0; dig <= ub; ++dig) { if (dig == ub) { ans += dpf(s, n - 1, tight, k - dig); } else { ans += dpf(s, n - 1, 0, k - dig); } } dp[tight][k][n] = ans; return ans; } void reset() { for (int i = 0; i < 65; ++i) { for (int j = 0; j < 65; ++j) { dp[0][i][j] = -1; dp[1][i][j] = -1; } } } private: std::vector>> dp; };

class Solution { public: int kInversePairs(int n, int k) { vector dp(k+1, 0); int mod = 1e9+7; for(int i=1; i<=n; i++){ vector tmp(k+1, 0); tmp[0] = 1; for(int j =1; j<=k; j++){ long long val = (dp[j] + mod - ((j-i) >=0 ? dp[j-i] : 0))%mod; tmp[j] = (tmp[j-1] + val)%mod; } dp = tmp; } return (dp[k] + mod - (k>0 ? dp[k-1] : 0))%mod; } };

class Solution{ public: pair dp[27][27]; string matrixChainOrder(int p[], int n){ return f(1,n-1,p).second; } pair f(int i,int j,int p[]){ if(i==j){ string curr = ""; curr += 'A' + i-1; return {0,curr}; } if(dp[i][j].second != "") return dp[i][j]; int val = INT_MAX; string s = ""; for(int k=i;k a = f(i,k,p); pair b = f(k+1,j,p); int q = p[i-1]*p[j]*p[k] + a.first + b.first; if(q

#define mod 1000000007 class Solution { public: long solveMem(int m, int n, int maxMove, int i, int j, int dp[51][51][51]){ if(i<0 j<0 i>=m ||j>=n){ return 1; } if(maxMove==0){ return 0; } if(dp[i][j][maxMove] != -1){ return dp[i][j][maxMove]; } long res = 0; res += solveMem(m, n, maxMove-1, i+1, j, dp); res += solveMem(m, n, maxMove-1, i, j+1, dp); res += solveMem(m, n, maxMove-1, i-1, j, dp); res += solveMem(m, n, maxMove-1, i, j-1, dp); return dp[i][j][maxMove] = res%mod; } int findPaths(int m, int n, int maxMove, int startRow, int startColumn) { int dp[51][51][51]; memset(dp, -1, sizeof(dp)); return solveMem(m, n, maxMove, startRow, startColumn, dp)%mod; } };

class Solution { public: //Function to get the maximum total value in the knapsack. struct comp { bool operator()(const pair<double, int>& p1, const pair<double, int>& p2) { return p1.first < p2.first; } }; double fractionalKnapsack(int wt, Item arr[], int n) { priority_queue< pair<double,int> ,vector< pair<double,int>>,comp>pq; for(int i=0;i<n;i++){ pq.push({arr[i].value/(double)arr[i].weight,arr[i].weight}); } double ans=0; while(wt>0&&!pq.empty()){ double a=pq.top().first; int b=pq.top().second; pq.pop(); ans+=(min(b,wt)*a); wt-=min(b,wt); } return ans ; } };

class Solution { public: vector> dp; int lcs(int i,int j,string &a, string &b) { if(i==-1 || j==-1) return 0; if(dp[i][j] != -1) return dp[i][j]; if(a[i] == b[j]) return dp[i][j] = 1+lcs(i-1,j-1,a,b); return dp[i][j] = max(lcs(i-1,j,a,b), lcs(i,j-1,a,b)); } int longestCommonSubsequence(string text1, string text2) { int n1 = text1.size(); int n2 = text2.size(); dp.resize(n1,vector(n2,-1)); return lcs(n1-1,n2-1,text1,text2); } };

class Solution{ public: bool flag=0; vector sieve; //prime sieve void prime_sieve() { sieve.resize(10000,1); int n=10000; sieve[0]=0; sieve[1]=0; for(int i=2;i*i<=n;i++) { if(sieve[i]) { for(int j=i*i;j<=n;j+=i) sieve[j]=0; } } flag=1; } //function to check , number is prime or not bool is_prime(string s) { int num=stoi(s); return bool(sieve[num]); } //helper function int help(string& s1,string& s2) { if(s1==s2) return 0; unordered_set vis;; queue q; q.push(s1); vis.insert(s1); int res=0; while(!q.empty()) { int size=q.size(); while(size--) { string curr=q.front(); q.pop(); if(curr==s2) return res; string temp=curr; for(int i=0;i<4;i++) { temp=curr; for(char ch='0';ch<='9';ch++) { if(i==0 and ch=='0') continue; temp[i]=ch; if(is_prime(temp) and vis.find(temp)==vis.end()) { q.push(temp); vis.insert(temp); } } } } res++; } return -1; } int solve(int Num1,int Num2) { if(!flag) prime_sieve(); string s1=to_string(Num1); string s2=to_string(Num2); int ans=help(s1,s2); return ans; } };