Monday, May 5, 2014

Generating the counting sequence

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.