0

Hello All,

I had this question asked to me in one of the interviews and I wasn't able to figure it out.I need to write a method CountUniqueSequences(int sum) which returns the number of unique sequences that consist of only 1's and 2's and have an element summation equal to a given N.
For example, below are all unique sequences consisting of 1's and 2's with element summation of N=4:

1 1 1 1
1 1 2
1 2 1
2 1 1
2 2

So, CountUniqueSequences(4) should return 5.

I figured out that the frequency of occurrences of 1 in case of even nos. consist of only even nos. and in case of odd nos. consist of only odd nos.Correspondingly, the frequency of occurrence of 2 gets incremented each time the frequency of occurrence of 1 decreases.

For instance,to obtain 4:
1 can be used 2 times or 4 times and 2 can be used 1 time or 0 time.

To obtain 5: 1 can be used 1,3 or 5 times and correspondingly 2 can be used 2,1 or 0 times.

Although,it's not required in the problem I know that I can permute the number to obtain all possibilities but I do not know how to form a number.
Any suggestions would be greatly appreciated.

3
Contributors
3
Replies
4
Views
7 Years
Discussion Span
Last Post by ChPravin
0

First correct me in this if I'm wrong.

For sum = 0 , return 0;
For sum = 1 , return 1;
For sum = 2 , return 2;
For sum = 3 , return 3;
For sum = 4 , return 5;
For sum = 5 , return 8;
For sum = 6 , return 13;


It looks like its defined by :

F(n) =
{ 0 if n = 0 }
{ 1 if n = 1 }
{ 2 if n = 2 }
{ F(n-1) + F(n-2) for n > 2 }
{ else not defined }

Thats just a guess.

Edited by firstPerson: n/a

0

This is clearly (n choose 0) + (n-1 choose 1) + (n-2 choose 2) + ... which is well known to be the fibonacci function.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.