Class assignment timelimit

#1


giving time limit error

#2

Hello @Faizan-Ali-1395131367301898

The code that you wrote is correct but it has an exponential time complexity. This is the reason why HackerBlocks is producing a Time Limit Exceeded Error.
Try to find some other way to get to the answer.

Hint:-
Let us call the function “f” which calculates the number of distinct integers of length n.
Now if we know
f(n) ending with ai and f(n) ending with bi
we can easily calculate f(n + 1)
f(n + 1) ending with ai = f(n) ending with bi + f(n) ending with ai
f(n + 1) ending with bi = f(n) ending with ai

Here f(n) ending with ai means the number of distinct integers of length n ending in ai.

#3

i didn’t get you can you please explain it

#4

Hello @Faizan-Ali-1395131367301898

Let’s understand by taking an example
Let n = 5

Here we will maintain to arrays of length 6
first[6]
second[6]

Where first[i] stores the number of strings with length = i ending with “a”
second[i] stores the number of strings with length = i ending with “b”

So first[0] will be zero as there will be no strings ending in “a” whose length is 0
second[0] will also be zero as there will be no strings ending in “b” whose length is 0

first[1] = 1 as there will one string ending in “a”
second[1] = 1 as there will be one string ending in “b”

Now to calculate first[2], we can append an “a” at the end of the strings included in first[1] and second[1]
first[2] = first[1] + second[1] = 1 + 1 = 2
To calculate second[2], we can append an “b” only at the end of the strings included in first[1] and NOT in second[1] because there can be NO two consecutive “b’s” in the string
second[2] = first[1] = 1

similarly
first[3] = first[2] + second[2]
second[3] = first[2]
and so on

At the end our answer is first[5] + second[5] i.e., number of strings of length 5 ending with “a” and number of strings of length 5 ending with “b”