Count Number of Binary Strings, TLE

#1

My recursive solution is showing TLE in 2 test cases among 3 test cases. Help me with time limit
code is here https://pastebin.com/0bwTRsCK

#2

N can be up to 90, and recursion complexity will be 2^N, which will definitely give TLE. Use memoization to reduce complexity.

#3

We are supposed to solve the questions using recursion right, I have not learned DP yet, so why are these question have such a time constraint!!?? Anyway thanks for help

#4

You can do it in another way because the recurrence is same as of Fibonacci number. If we take a closer look at the pattern, you can observe that the count is actually (n+2)’th Fibonacci number for n >= 1. The Fibonacci Numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141.

1 Like
#5

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.