I am not getting what the problem statement is trying to convey. Can someone please clear that to me? Only the problem statement, Not the solution.
Can someone please simplify the problem statement for me?
Hello @raghav6,
Explanation:
In the question you have to print the count of strings of length n, that can be made using only a and b:
With a condition, that you cannot place b at consecutive positions.
Let’s understand with the help of an example:
3 //this is the no. of test cases and following are the values of n for different testcases
1
2
3
-
In the first testcase, the value of n is 1.
The possible strings of length 1 with a and b as characters are:
a, b i.e. 2 -
In the second testcase, n=2.
The possible strings of length 1 with a and b as characters are:
aa, ab, ba i.e. 3
bb is not included in the count as in this b are at consecutive position -
Similarly, for n=3 in the third testcase.
The possible strings of length 1 with a and b as characters are:
aaa, aba, baa, aab, bab i.e. 5
Now, considering the output format, the output will be:
#1 : 2
#2 : 3
#3 : 5
You can refer to the video, Count Binary Strings Hint from your course as it is a similar question.
Try to solve yourself before reading the below-mentioned hint.
HINT:
It can be solved in a manner similar to computing Fibonacci sequence.
For n=1 i.e. string of length 1
{a,b}=2
(First base case)
For n=2 i.e. string of length 2
{aa,ab,ba}=3 //b cannot be together
(second base case)
For n=3
{aaa,aba,baa,aab,bab}=5
fib[3]=fib[2]+fib[1]=3+2=5
For n=4
{aaaa,abaa,baaa,aaba,baba,aaab,abab,baab}=8
fib[4]=fib[3]+fiib[2]=5+3=8
so on…
Concluding: fib[n]=fib[n-1]+fib[n-1]
Hope, this would help.
Give a like if you are satisfied.
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.