The way I solved the question is giving TLE. I am able to dry run the code given in the editorial for this question, but I cant understand the approach or concept behind that code?
can you please explaing me
this is the question’s link : https://hack.codingblocks.com/contests/c/547/875/
Class Assignment question
hi sagar
you might have solved the question using some bruteforce approach but the most efficient way to solve is to do the question by dynamic programming approach.
the logic is consider a[i] be the number of strings which do not contain consecutive digits(of bi say) but end with ai.
and b[i] be the number of strings which end in ai
we can only add either ai or bi to the strings ending with ai
but we can only add ai to the strings ending with bi
so recursive formula is
a[i] = a[i - 1] + b[i - 1]
b[i] = a[i - 1]
The base cases of above recurrence are a[1] = b[1] = 1. The total number of strings of length i is just a[i] + b[i].
consider ai to be 0 and bi to be 1(for your reference. it would easy for you to understand)
if you still dont understand i will explain again
@AASTHA011 I am really sorry for bothering again, but I am unable to understand this approach.
Also, I noticed, if I am writing down answers for different cases, Fibonacci series starts coming up. Is it just a coincidence, or there is some reason behind this approach?
@sgrarora3 yes there is a pattern of fibbonacci numbers as well
we can observe that the count is actually (n+2)’th Fibonacci number for n >= 1.
n = 1, count = 2 = fib(3)
n = 2, count = 3 = fib(4)
n = 3, count = 5 = fib(5)
n = 4, count = 8 = fib(6)
n = 5, count = 13 = fib(7)
Thanks a lot 
I used the fibbonacci approach and it’s working now.
if you don’t have any further queries you can mark your doubt as resolved.