Algo++ : class assignment problem

#1

I think this problem can be converted into fibonacci series
let f(n) gives no. of n digit numbers that can be formed
if 1st digit is a then we have to solve for f(n-1)
if 1st digit is b then 2nd digit must be ‘a’ , so we have to solve for f(n-2)
that means
f(n)=f(n-1)+f(n-2)
but it shows wrong answer on implementing this.
int f(int n)
{
if(n==1)
return 2;

if(n==2)
return 3;

if(n==0)
return 0;

int dp[n+1];
dp[0]=0;
dp[1]=2;
dp[2]=3;

for(int i=3;i<=n;i++)
{
	dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];

}

#2

Hi @amandahiya.3572
Your approach is absolutely right. Please share your entire code using ide.codingblocks.com so I can take a look and help you out.

#3
#4

@amandahiya.3572
As I said , your approach is absolutely fine.
There were two small issues with your code. First being that you should use long long int in place of int as Fibonacci series grows extremely fast and is likely to exceed the range of int for slightly larger numbers.
Secondly there is an issue with your output format .
Line No. 31. After the # , it shouldn’t be n. Instead make a counter variable count=1 before the testcase loop and output the count variable in place of n. Increment count after every iteration.

cout<<"#"<<count++<<" : "<<f(n)<<endl;;

The # number is to only show the testcase number and does not have anything to do with the entered input. It just so happened in the testcase that the sample inputs happened to coincide with the counter.

#5

still the test case is not passing.??

#6

@vardaan_sharma
Increase your array size slightly by 1 or 2 , also make the required changes in the loop . Should work.

#7

thanks - now it’s working fine