3154. Find Number of Ways to Reach the K-th Stair | Time Complexity Analysis | No Returning DP

[@ARYANMITTAL]

Mass Cheating in every Leetcode Contest (More shorts on this New Channel) - th-cam.com/users/shortshH473URZWnk?si=VHvc-zg59h7kbR-u
.
.
To solve it in O(32*32) time (Iterative) - leetcode.com/problems/find-number-of-ways-to-reach-the-k-th-stair/solutions/5177275/math-o-log-n/

[@ardhidattatreyavarma5337]

I did the same except didn't think of the base case as you did. Awesome solution mate!

[@theexplorer9012]

maksad nhi bhulna

[@pokerfaced8139]

13:08 thik h aryan bhai

[@sangdilbiswal30]

His code below...
#define ll long long int
class Solution {
public:
unordered_map dp;
int solve( int i, int& k, int wasLastDown, int jump){

if(i>k+1)return 0;

if( dp.count(i) && dp[i].count(wasLastDown)&& dp[i][wasLastDown].count(jump))return dp[i][wasLastDown][jump];

ll ans = (i==k);
ans += solve(i+pow(2,jump),k,0,jump+1);
if(i!= 0 && !wasLastDown) ans += solve(i-1, k, 1, jump);
return dp[i][wasLastDown][jump]=ans;

}
int waysToReachStair(int k) {
int ans = (int)solve(1,k,0,0);
return (int)ans;
}
};

[@Codingiisgreat]

I tried to solve but only 134/600 testcases passed im glad to see your solution .
void func(int p,int k,int jump,int &cnt,bool down){
if(p>=k+2) return ;
if(p==k) cnt++;
if(p==0) down = false;
if(down){
func(p - 1,k,jump,cnt,!down);
func(p + pow(2,jump),k,jump+1,cnt,down);
}
else{
func(p + pow(2,jump),k,jump+1,cnt,!down);
}
return;
}

int waysToReachStair(int k) {
int cnt = 0 ;
int jump = 0 ;
int p = 1 ;
func(p,k,jump,cnt,true); // moving down
func(p,k,jump,cnt,false); // Moving Up
return cnt;
}

[@agam3932]

Nice solution bro!! Love the little comedy moments in bw, explore more like ur ex lmaoooo

[@ajayprabhu465]

helpfull, june july ill be grinding leetcode. If possbile make all contest discussion videos or videos on question which teach us something. Ill be waiting ,Thank you.

[@ARYANMITTAL]

Yaa yaa bro, "Weekly Contest Discussion by Aryan Mittal", write this on TH-cam, you will get a playlist of nearly every contest all problems discussed on our Channel 🫂

[@abhinavnarula7300]

How to even think of something like at max 32 up jumps are possible and stuff?

[@theLonelyBandit6984]

Can you tell why this can't be done without memorisation?

[@Vishnu-it8st]

bro can u provide the link code or something asits not working

[@satwiktatikonda764]

aryan bro
this mass cheting thing
is this the case even before 2-3 yrs back

[@Codingiisgreat]

Didnt understand the 32*32*32*2 can anyone help
??

[@fraserdab]

Last weekly contest ka hard ka video if possible?

[@brp3522]

Arayn bhai aaj ka POTD??

[@ARYANMITTAL]

Already live on channel sir, Community post dekho ek baar ❤️

[@brp3522]

@@ARYANMITTAL ohh well yeah I checked. Thanks alot for helping me learn a lot of concepts🤗

[@gui-codes]

It's very confusing bhai. Or I believe this is not for beginners.

[@ARYANMITTAL]

Let's try again & if again, then do let me know, ki kha dikkat aati hai ❤️

[@gui-codes]

@@ARYANMITTAL sure thanks bhai

[@user-bh9ts7db5r]

@ARYANMITTAL
class Solution {
public:
unordered_map m;
int help( int k,int i,int j, int prev){
int c=0;
if(i>k+1)return 0;
if(i==k )c=1;
if(m[i][j][prev]!=0)return m[i][j][prev];
int op1=0;
if(i!=0 && prev!=0)
op1 = help(k,i-1,j, 0);
int op2 = help(k,i+pow(2,j), j+1 , 1);
return m[i][j][prev] = c + op1 + op2;
}
int waysToReachStair(int k) {
return help(k,1,0,-1);
}
};
Please tell me what am I doing wrong? I have memoised this but it is still giving TLEwww.youtube.com/@ARYANMITTAL

[@sangdilbiswal30]

code seem correct but the check for map is incorrect m.count(i) && m[i].count(prev)&& m[i][prev].count(j) this in place of m[i][j][prev]!=0
class Solution {
public:
unordered_map m;
int help( int &k,int i,int j, bool prev){

if(i>k+1)return 0;

if( m.count(i) && m[i].count(prev)&& m[i][prev].count(j))return m[i][prev][j];

return m[i][prev][j] = ((i==k )?1:0) + ((i!=0 && prev==0)?help(k,i-1,j, 1):0) + help(k,i+(1