LeetCode, GeeksForGeeks Problem of the day solution

class Solution { public: int trap(vector& height) { if (height.empty()) return 0; int trap = 0; int left = 0; int right = height.size() - 1; int max1 = height[left]; int max2 = height[right]; while (left < right) if (max1 < max2) { trap += max1 - height[left]; max1 = max(max1, height[++left]); } else { trap += max2 - height[right]; max2 = max(max2, height[--right]); } return trap; } };

class Solution { public: long long pairAndSum(int n, long long arr[]) { long long result = 0; for(int i = 31; i >= 0; i--) { long long bits = 0; for(int j = 0; j < n; j++) { bits += ((arr[j]>>i) & 1); } result = (result << 1) + bits * (bits - 1) / 2; } return result; } };

class Solution { public: string removeKdigits(string nums, int k) { int x = nums.size(); if(x==k) return "0"; string s; int i=0; while( i0 && !s.empty() && s.back()>nums[i]) { s.pop_back(); k--; } s.push_back(nums[i]); i++; } while(k>0 && !s.empty() ) { s.pop_back(); k--; } while(!s.empty() && s[0]=='0') { s.erase(0,1); } return !s.empty()? s:"0" ; } };

class Solution{ public: // function to convert a given Gray equivalent n to Binary equivalent. int grayToBinary(int n) { int prev = 0; for (int i = 31; i >= 0; i--) { n ^= (1 << i) * prev; if (n & (1 << i)) prev = 1; else prev = 0; } return n; } };

class Solution { public: vector deckRevealedIncreasing(vector& deck) { int n = deck.size(); sort(deck.begin(),deck.end()); if(n<3)return deck; queue q; int i = n-1; q.push(deck[i]); q.push(deck[i-1]); i-=2; while(i>=0){ int t = q.front(); q.pop(); q.push(t); q.push(deck[i--]); } vector ans; while(q.size()){ ans.push_back(q.front()); q.pop(); } reverse(ans.begin(),ans.end()); return ans; } };

class Solution{ public: int findSingle(int n, int arr[]){ int ans=0; for(int i=0; i

class Solution { public: int timeRequiredToBuy(vector& a, int k) { int n = a.size(); int count=0; while(a[k]!=0){ for(int i=0;i0){ a[i]= a[i]-1; count++; } if(a[i]==0)continue; } } return count; } };

class Solution{ public: int minPoints(int M, int N, vector> points) { vector> dp(M, vector(N, 0)); dp[M - 1][N - 1] = max(1, 1 - points[M - 1][N - 1]); for (int i = M - 2; i >= 0; --i) { dp[i][N - 1] = max(1, dp[i + 1][N - 1] - points[i][N - 1]); } for (int j = N - 2; j >= 0; --j) { dp[M - 1][j] = max(1, dp[M - 1][j + 1] - points[M - 1][j]); } for (int i = M - 2; i >= 0; --i) { for (int j = N - 2; j >= 0; --j) { int minPointsRequired = min(dp[i + 1][j], dp[i][j + 1]); dp[i][j] = max(1, minPointsRequired - points[i][j]); } } return dp[0][0]; } };

class Solution { public: int countStudents(vector& students, vector& sandwiches) { int arr[2] = {0}; for(auto i:students){ arr[i]++; } for(auto i:sandwiches){ if(arr[i]==0){ break; } arr[i]--; } return arr[0]+arr[1]; } };

class Solution{ public: long long solve(int n, int i, int j, int arr[],vector<vector<long long>> &dp){ if(i>j) return 0; if(dp[i][j]!=-1) return dp[i][j]; long long c1 = arr[i] - solve(n,i+1,j,arr,dp); long long c2 = arr[j] - solve(n,i,j-1,arr,dp); return dp[i][j] = max(c1,c2); } long long maximumAmount(int n, int arr[]){ vector<vector<long long>> dp(n+1, vector<long long>(n+1,-1)); long long v = solve(n,0,n-1,arr,dp); long long tsum = 0; for(int i = 0;i<n;i++) tsum += arr[i]; return (tsum-v)/2+v; } };