https://ide.geeksforgeeks.org/lSPDwfyuoU
this is my solution it got accepted for all test cases but when i saw the editorial i found the question has a pattern of fibonnaci numbers.I am not able to understand the pattern and how fibonnaci series is linked with the problem.Please Explain.
hello @mikki18
let say we need to form n digit number with following constraints
a) we can use only digit a and b.
b) no 2 b two come together.
now lets say ways(n) is a function which tells us number of such n digit number.
ways(n) =
if we place a at nth position then total number of ways for this case will be ways(n-1)
if we place b at nth position then n-1 th position must contain a so total number of ways for this case will be ways(n-2)
on adding both the cases we get
ways(n)=ways(n-1)+ ways(n-2)
clearly this sequence is fibonnacci
When you say this
if we place a at nth position then total number of ways for this case will be ways(n-1)
then suppose for 2nd place (two digit no)there are 3 options f(2) = 3 so now if we place a at 3rd position then total no of ways is 1 + f(2) i.e. 4 right ??.
Similarly for b.
no dont add 1.
it will be f(2) only
because on every 2 digit valid number we will append a at the last and resultant will be a 3 digit valid number.
thats why
ways(3)=ways(2) // when a is placed at 3rd place.
and for b.
we will append ab to every one digit valid number to get 3 digit valid number.
therfore
ways(3)=ways(1) // when b is place at 3rd position and a at 2nd.
so when we merge both the cases.
we will get
ways(3)=ways(1) + ways(2)
okay got it thank you.
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.