How to solve this question

#1

no of possible n digit numbers which only consists of 4 5 6
such that there are no three consecutive digits

#2

hi @tusharkhandelwal315,if u are looking for recursive solution then one way i can think of is to have last two digits as the parameter in the function. and before inserting any digit , check if it forms three consequtive integer if yes then don;t include it in your answer

refer the code: -

#define ll long  long

ll int answer(ll int n,ll int prev,ll int prev_prev){
    if(n==0){
        return 1;
    }
    ll int ans=0;
    
    // case 1 : selecting nth digit as 4
    if(prev!=4||prev_prev!=4){
        ans+=answer(n-1,4,prev);
    }
    // case 2 : selecting nth digit as 5
    if(prev!=5||prev_prev!=5){
        ans+=answer(n-1,5,prev);
    }
    // case 1 : selecting nth digit as 6
    if(prev!=6||prev_prev!=6){
        ans+=answer(n-1,6,prev);
    }
    return ans;
}

In case of any doubt feel free to ask :slight_smile:
if you got the answer then mark your answer as resolved

#3

sir, n<=400
i think we have to use dp

#4

i don’t have the question with me , surely you can use dp to optimize it further

#5

Capture1
Capture11220×734 41.5 KB

#6

using dp will be suffice for this question , memoize the above recursive solution i have provided

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.