Please answer this

#1

How f(n-2) guarantees me that 1,1 cases are not counted but 0,1 has been…also i am not getting the base case for it…not able to get at n=0…

#2

@garganshul151 please point out the time stamp where this was mentioned

#3

3:05 3:10 is the time frame…also tell me the base case

#4

@garganshul151 the recurrence relation is
f(n) = f(n-1) + f(n-2)
its obvious that n cant be <= 0 (string length cant be 0 or negative), so the relation stands for n > 2 this means that we need to define the values for n = 1 and n = 2 ourselves. Another base case will be for n <= 0.
So the base cases are:

if (n <= 0) return 0;
if (n == 1) return 2;
if (n == 2) return 3;

Explanation:
if n <= 0 no strings can be made so answer is 0
if n = 1, possible strings: {0, 1} valid strings: {0, 1} so answer is 2
if n = 2, possible strings: {00, 01, 10, 11} valid strings: {00, 01, 10} so answer is 3

As for the rec relation:

we have to ensure that 2 1’s do not occur together
so suppose you have string of length n and you are at ith index. You can fill either 0 or 1
if you fill it with 0, i+1th can have ANY digit, it does not matter. So the length of our subproblem is reduced by 1, so call the function for “n-1” ie f(n-1)
if you fill it with 1, i+1th index can have only 0. it cannot have 1. So now you know what are the digits of 2 indices, so length of subproblem is reduced by 2, so call the function for n-2, ie f(n-2)

I hope I have cleared all your doubts now. Mark the doubt as resolved if that is the case :slight_smile:

#5

thanks for such a solution…one more think will the code be same for without consecutige 0’s?

#6

@garganshul151 yes there will be no difference, same logic

#7

can there be a question saying only those which have atleast 2 0s or 2 1s together?if yes what ,will the answer

#8

@garganshul151 you can use string.find() function for that

#9

can i do it using recursion?

#10

@Ishitagambhir U explained it well. I am revising the P&C concepts. Can you explain in try of permutation like he we have N=3 then we have _ _ _ 3 slots,2 choices for the 1 slots 1/0 and if we choose 1 then we only have 1 choices left for the second slot and 2 remaining for the next slot like this hope u got my points…

#11

@garganshul151
a very easy answer would be to simply subtract it from total number of strings
ie num of strings with at least 2 0s together = total no of strings - no of strings with no 0s together

#12

hi @Vikaspal please raise a separate doubt for your queries to avoid any confusion