LeetCode, GeeksForGeeks Problem of the day solution
Відкрити в Telegram
Complete daily challenges from LeetCode, GeeksForGeeks and redeem their rewards Channel link : https://t.me/leetcode_gfg_potd
Показати більше1 250
Підписники
+224 години
+147 днів
+2930 день
Архів дописів
class Solution {
public:
const int mod = 1e9 + 7;
int numFactoredBinaryTrees(vector& arr) {
int n = arr.size();
sort(arr.begin(), arr.end());
vector dp(n);
dp[0] = 1;
int res = 0;
for (int i = 1; i < n; i++)
{
int target = arr[i];
int p = 0, q = i - 1;
long ways = 1;
while(p <= q)
{
long mul = (((long)arr[p]) * (arr[q]));
if (mul == target)
{
if (p == q) ways += (dp[p] * dp[q]) % mod;
else ways += ((dp[p] * dp[q]) * 2) % mod;
p++;
q--;
}
else if (mul < target) p++;
else if (mul > target) q--;
}
dp[i] = ways;
res = (int)((res + dp[i]) % mod);
}
return res + 1;
}
};
class Solution
{
public:
int minOperation(int n)
{
int count = 1;
while(n!=1)
{
if(n%2 == 1)
{
count++;
n = n-1;
}
n = n/2;
count++;
}
return count;
}
};
class Solution {
public:
int kthGrammar(int n, int k) {
if(n==1 && k==1){
return 0;
}
int mid = pow(2, n-1)/2;
if(k<=mid){
return kthGrammar(n-1, k);
}
else{
return !(kthGrammar(n-1, k-mid));
}
}
};
class Solution{
public:
int knapSack(int N, int W, int val[], int wt[])
{
int arr1[W+1], arr2[W+1];
int* a = arr1;
int* b = arr2;
for(int &i:arr2)
i = 0;
for( int i=0;i
class Solution {
public:
vector largestValues(TreeNode* root) {
if(!root) return {};
vector> lot;
queue q;
q.push(root);
while(!q.empty())
{
int size = q.size();
vector temp;
while(size--)
{
TreeNode * node = q.front();
q.pop();
temp.push_back(node->val);
if(node->left) {
q.push(node->left);
}
if(node->right){
q.push(node->right);
}
}
lot.push_back(temp);
}
vector res;
for(auto i : lot)
{
int maxi = INT_MIN;
for(int j : i)
{
maxi = max(maxi,j);
}
res.push_back(maxi);
}
return res;
}
};
class Solution{
public:
bool isPalindrome(string &s, int i, int j){
while(i dp(n+1, 0);
for(int i=n-1;i>=0;i--){
int mini = INT_MAX;
for(int j=i;j
class Solution {
public:
bool isPowerOfFour(int n) {
if(n<=0){
return false;
}
double res = (log10(n) / log10(4));
return res == (int)res;
}
};
class Solution{
public:
int maxSumIS(int arr[], int n)
{
vectordp(n);
for(int i=0;i
class Solution {
public:
int maximumScore(vector& nums, int k) {
int i =k, j=k;
int maxi = nums[k];
int mini = nums[k];
while(i>0 || j nums[i-1])) {
j++;
}else {
i--;
}
mini = min(mini, min(nums[i], nums[j]));
maxi = max(maxi, (mini * (j-i +1)));
}
return maxi;
}
};
class Solution
{
public:
long long power(long long x,int y, int p)
{
long long res = 1;
while (y > 0)
{
if (y & 1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}
long long modInverse(long long n,int p)
{
return power(n, p - 2, p);
}
long long numberOfPaths(int M, int N)
{
long long path = 1,mod=1e9+7;
for (long long i = N; i < (M + N - 1); i++) {
path = (path*i)%mod;
long long inv=modInverse(i-N+1,mod);
path = (path*inv)%mod;
}
return path;
}
};
