Given an integer N, we have to generate the nth sequence of the following pattern.
- “1”
- “11” as the previous item contains one instance of 1.
- “21” as the previous entry contains two 1’s.
- “1211” as the previous entry contains one 2 and one 1.
Following is the program which generates such a sequence. It runs in O(n*k) (where k is the length of the sequence) time and it utilizes only constant extra space.