LeetCode, GeeksForGeeks Problem of the day solution
Open in Telegram
Complete daily challenges from LeetCode, GeeksForGeeks and redeem their rewards Channel link : https://t.me/leetcode_gfg_potd
Show more1 250
Subscribers
+224 hours
+147 days
+2930 days
Posts Archive
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;
}
};
