LeetCode, GeeksForGeeks Problem of the day solution

class Solution { public: int solve(vector>&obstacleGrid, int i, int j, vector>& dp){ if(i<0 || j<0){ return 0; } if(i==0 && j==0){ return 1; } if(obstacleGrid[i][j]==1){ return 0; } if(dp[i][j] != -1){ return dp[i][j]; } int up = solve(obstacleGrid, i-1, j, dp); int left = solve(obstacleGrid, i, j-1, dp); return dp[i][j] = up+left; } int uniquePathsWithObstacles(vector>& obstacleGrid) { int m=obstacleGrid.size(); int n=obstacleGrid[0].size(); int i=m-1; int j=n-1; if(obstacleGrid[0][0]==1 || obstacleGrid[m-1][n-1]==1){ return 0; } vector> dp(m, vector(n, -1)); return solve(obstacleGrid, i, j, dp); } };

class Solution { public: //Function to find length of longest increasing subsequence. int longestSubsequence(int n, int a[]) { vector temp; temp.push_back(a[0]); for(int i=1;i

class Solution { public: int change(int amount, vector& coins) { vector dp(amount+1, 0); dp[0] = 1; for(int i=0;i=0){ dp[j] += dp[j-coins[i]]; } } } return dp[amount]; } };

class Solution { public: long long int count(int coins[], int N, int sum) { vector prev(sum + 1, 0); fill(prev.begin(), prev.end(), 0); for (int i = 0; i <= sum; i++) { if (i % coins[0] == 0) { prev[i] = 1; } } for (int i = 1; i < N; i++) { vector curr(sum + 1, 0); fill(curr.begin(), curr.end(), 0); for (int j = 0; j <= sum; j++) { long long int a, b; a = b = 0; a = prev[j]; if (j >= coins[i]) { b = curr[j - coins[i]]; } curr[j] = a + b; } prev = curr; } return prev[sum]; } };

class Solution { public: bool binarySearch(int s, int e, int &target, vector<int> &nums){ if(s>e) return false; int mid = (s+e)/2; if(nums[mid]==target) return true; else if(nums[mid]>target) return binarySearch(s, mid-1, target, nums); return binarySearch(mid+1, e, target, nums); } bool search(vector<int>& nums, int target) { int idx=0; for(int i=1; i<nums.size(); i++){ if(nums[i-1]>nums[i]) idx = i; } return binarySearch(0, idx-1, target, nums)|binarySearch(idx, nums.size()-1, target, nums); } };

class Solution { public: //Function to find the length of longest common subsequence in two strings. int lcs(int n, int m, string s1, string s2) { vectorprev(m+1,0),cur(m+1,0); for(int i = 1;i<=n;i++){ for(int j = 1;j<=m;j++){ if(s1[i-1] == s2[j-1]){ cur[j] = 1 + prev[j-1]; } else { cur[j] = fmax(cur[j-1],prev[j]); } } prev = cur; } return cur[m]; } };

class Solution { public: int minimizeMax(vector& A, int p) { sort(A.begin(), A.end()); int n = A.size(), left = 0, right = A[n - 1] - A[0]; while (left < right) { int mid = (left + right) / 2, k = 0; for (int i = 1; i < n && k < p; ++i) { if (A[i] - A[i - 1] <= mid) { k++; i++; } } if (k >= p) right = mid; else left = mid + 1; } return left; } };

class Solution{ public: long long int largestPrimeFactor(int N){ long long ans = 0; for(long long i = 2 ; i * i <= N ; i++) { if(N % i == 0) { ans = max(ans , i); while(N % i == 0) { N = N / i; } } } ans = max(ans , (long long)N); return ans; } };

class Solution { public: int getPivot(vector<int>& nums){ int s = 0; int e = nums.size()-1; while(s<e){ int mid = s + (e-s)/2; if(nums[mid]>=nums[0]){ s = mid+1; } else{ e = mid; } } return s; } int binarySearch(vector<int>& nums, int s, int e, int key){ while(s<=e){ int mid = s +(e-s)/2; if(nums[mid]==key){ return mid; } else if(nums[mid]>key){ e = mid- 1; } else{ s = mid +1; } } return -1; } int search(vector<int>& nums, int target) { int pivot = getPivot(nums); int n = nums.size(); if(target >= nums[pivot] && target <= nums[n-1]){ return binarySearch(nums, pivot, n-1, target); } else{ return binarySearch(nums, 0, pivot-1, target); } } };

class Solution { public: int countFractions(int n, int num[], int den[]) { unordered_map mp; int count = 0; for(int i = 0; i < n; i++) { int gcd = __gcd(num[i], den[i]); double nm = num[i] / gcd; double dm = den[i] / gcd; double x = (dm - nm) / dm; double y = (nm / dm); if(mp[x] > 0) count = count + mp[x]; mp[y]++; } return count; } };