Wednesday, 15 July 2015

AMZSEQ

Standard

AMZ Word

Link to the question : AMZSEQ 

HINT : 

A very good question on dynamic programming. We take an array a[] and assign a[0] = 1. Now, we can make  1 letter words in 3 ways , i.e, use any of the digit. Similarly if you solve for 2 letter words by applying a bit of permutation and combination, you will get it to be 7. Similarly, by using the relation , a[2] = 7 , in 3 letter words, you will find number of ways to be 17. Hence we conlude the conclusion that a[i]= 2* a[i-1] + a[i-2]. 

RECOMMENDED QUESTION :

Try your hands on this simple question.

SOURCE CODE: 

#include <iostream>
using namespace std;
int main()
{
long long int a[25];
int  x;
a[0] = 1;
a[1] = 3;
for(int i = 2; i < 25; i++)
a[i] = 2*a[i-1] + a[i-2];
cin >> x;
cout << a[x] << endl;
return 0;
}

2 comments:

  1. there is a problem in you hint, that is there should be 17 in place of 15.

    ReplyDelete