So he basically created frequency map from 0 to 23, where he stores value he faced % 24, why modulo is being used is basically makes things here easier, like if we have 12 and it can be paired with 12, 36... so if we just make % 24 for them we will only deal with 12 in this case. So from here map from 0 to 23, the only thing to consider is 24 itself it will be treated as 0 in our map. Required one is the (24 - (hours[i] % 24)) with extra % 24 to deal with case where 24 comes out. Very helpful will be rewatching and proving everything on paper for yourself, peace!
Consider in this way (a + b ) % k where k is any number according to modulo rule (a + b) % k can also be written as (a % k + b % k ) % k now think in this case where we have two number (a + b) % k = 0 that means any two number whose come in the table k it's remainder will be the zero now if we mod any number with if it'll come in (0 - k-1) range (e.g... 50 % 24 = 2 or 2 % 24 == 2 ) now here is the acutal logic come i have two number ( a % 24 + b % 24) if it's sum become 0 or 24 so our answe also the divisble by 24 our a%24 alwasy < 24 (that means it's come in 0 - 23) now check any two number if i have (a % 24) == 6 then what will be the (b % 24 ) it' must be the 24 - 6 = 18 a ny number remainder is 18 that'll divisible by 24 (eg my orignal a either (6, 30 , 54 ) when you divide this number by 24 the remainder will always 6 and our orignal number b will be either(18 , 42, 66) if you divide this by 24 the remainder will be the 18 ) now add any two number from a & b the answer i always divisble by 24 I hope you'll understand it now
Sir..How you thought that it will be 1d dp..as i thought i can take index and the last index chosen as variables..it would be 2d dp..and just memoized it..but it got tle...Sir is it wrong that we have to take x d dp if there are total x variables changing with every state..
class Solution { public long maximumTotalDamage(int[] power) { return f(0,new HashMap(),power); } public long f(int i,Map map,int p[]) { if(i>=p.length) return 0; long nottake=f(i+1,map,p);
long contain=0,max=0,take=0; if(map.containsKey(p[i])) take=0+f(i+1,map,p); else{ map.put(p[i]-2,1); map.put(p[i]-1,1); map.put(p[i]+2,1); map.put(p[i]+1,1);
max=Math.max(take,nottake); return max; } } can we do 3rd question like this logic is simple values which we cant take store in map so that after going forward we cant take that value
@@roshangeorge97 We r calculating out answer using *ans+=freq[req]* , where *req=(24-a[j]%24)%24* , and then we r updating *freq[a[j]%24]++* what it means is, when we have a[j]=6, we will check req=24-6=18, so we will search for frequency of 18 in our freq array, and update our answer.. then, we will do *freq[6]++* , to update our frequency array. and, when we come to 18.. we will get req=24-18=6, so we update answer using ans+=freq[6], and then update freq[18]++ I hope that is clear. If not, u can look at the code again and try to dry run yourself.
bhaiya maine c question me map nhi set use kiya tha but error de diya 338 testcases pass ho gya but submit nhi hua can you tell me why this approach fails ??? class Solution { public: void insertInStack(int n, set&st){ for(int i=n-2; i
Please fill the feedback form: forms.gle/kYqtzVfTFbVUwzm37
The 3 rd question was tough since conventional memomization solution didnt work
i also did the same...but got Memory limit exceeded 533/553 test case passed
Use array instead of vector
please buy some good quality microphones
Please Post last weekly and last biweekly solutions
Thankyou for the solutions !
why we don't need to consider power[i] + 1, and power[i] + 2 for dp[i] ?
can someone break down the 2nd question the modulo arithmetic part?
So he basically created frequency map from 0 to 23, where he stores value he faced % 24, why modulo is being used is basically makes things here easier, like if we have 12 and it can be paired with 12, 36... so if we just make % 24 for them we will only deal with 12 in this case. So from here map from 0 to 23, the only thing to consider is 24 itself it will be treated as 0 in our map.
Required one is the (24 - (hours[i] % 24)) with extra % 24 to deal with case where 24 comes out.
Very helpful will be rewatching and proving everything on paper for yourself, peace!
Consider in this way
(a + b ) % k where k is any number
according to modulo rule (a + b) % k can also be written as (a % k + b % k ) % k
now think in this case where we have two number (a + b) % k = 0 that means any two number whose come in the table k it's remainder will be the zero now if we mod any number with if it'll come in (0 - k-1) range (e.g... 50 % 24 = 2 or 2 % 24 == 2 ) now here is the acutal logic come i have two number ( a % 24 + b % 24) if it's sum become 0 or 24 so our answe also the divisble by 24
our a%24 alwasy < 24 (that means it's come in 0 - 23) now check any two number
if i have (a % 24) == 6 then what will be the (b % 24 ) it' must be the 24 - 6 = 18 a ny number remainder is 18 that'll divisible by 24 (eg my orignal a either (6, 30 , 54 ) when you divide this number by 24 the remainder will always 6 and our orignal number b will be either(18 , 42, 66) if you divide this by 24 the remainder will be the 18 ) now add any two number from a & b the answer i always divisble by 24
I hope you'll understand it now
I got 3 wrong submissions in 3rd question Came back to lc after 3months😓
❤❤loved it 🔥 🔥
Sir..How you thought that it will be 1d dp..as i thought i can take index and the last index chosen as variables..it would be 2d dp..and just memoized it..but it got tle...Sir is it wrong that we have to take x d dp if there are total x variables changing with every state..
#define ll long long int
class Solution {
public:
long long maximumTotalDamage(vector& nums) {
mapm;
int n=nums.size();
for(int i=0;i
class Solution {
public long maximumTotalDamage(int[] power) {
return f(0,new HashMap(),power);
}
public long f(int i,Map map,int p[])
{
if(i>=p.length)
return 0;
long nottake=f(i+1,map,p);
long contain=0,max=0,take=0;
if(map.containsKey(p[i]))
take=0+f(i+1,map,p);
else{
map.put(p[i]-2,1);
map.put(p[i]-1,1);
map.put(p[i]+2,1);
map.put(p[i]+1,1);
take=p[i]+f(i+1,map,p);
map.remove(p[i]-2);
map.remove(p[i]-1);
map.remove(p[i]+2);
map.remove(p[i]+1);
}
max=Math.max(take,nottake);
return max;
}
} can we do 3rd question like this logic is simple values which we cant take store in map so that after going forward we cant take that value
This may give MLE because of the map
@@Mmk-gi4ug why it will give mle explain
the TC of this code would go exponential, as u have not done any memiozation here.. its simply recursivve brute force.
@@abhinavkumariitism it will optimise easily using 1dp I know but I want to know it will work
does it give MLE for you...
Nice one!!
atleast invest in good mics
@9:36 how freq[6]++; ? can anyone help
6%24 = 6, so freq[6]++, but ig there was a mistake.. we need to search for 24-6 ie: 18. so for the element 6 it should be freq[18++]//..
do you want to know what does freq[6]++ means
@@roshangeorge97 I also thought that
@@roshangeorge97 We r calculating out answer using *ans+=freq[req]* , where *req=(24-a[j]%24)%24* , and then we r updating *freq[a[j]%24]++*
what it means is, when we have a[j]=6, we will check req=24-6=18, so we will search for frequency of 18 in our freq array, and update our answer.. then, we will do *freq[6]++* , to update our frequency array.
and, when we come to 18.. we will get req=24-18=6, so we update answer using ans+=freq[6], and then update freq[18]++
I hope that is clear. If not, u can look at the code again and try to dry run yourself.
bhaiya maine c question me map nhi set use kiya tha but error de diya 338 testcases pass ho gya but submit nhi hua can you tell me why this approach fails ???
class Solution {
public:
void insertInStack(int n, set&st){
for(int i=n-2; i
in 3rd question inner loop will run at max 3 times , isn't it??
yep..
time to change the tutor I think....