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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <string> | |
| #include <sstream> | |
| using namespace std; | |
| string countAndSay(int n) | |
| { | |
| //Base cases: for empty string | |
| if( n < 1) | |
| { | |
| return ""; | |
| } | |
| //1st sequence | |
| if( n == 1 ) | |
| { | |
| return "1"; | |
| } | |
| string sequence("1");//init | |
| string result(""); //used as a temp sequence | |
| stringstream ss; //to convert numbers to string | |
| //generate from second sequence | |
| for( int i = 1; i < n ; i++ ) | |
| { | |
| char d = sequence[0]; | |
| int count = 1; | |
| result = ""; | |
| for ( int j = 1; j < sequence.size(); j++ ) | |
| { | |
| if( sequence[j] == d ) | |
| count++; | |
| else | |
| { | |
| ss.str(""); //reset to empty string | |
| ss << count << d; | |
| result += ss.str(); | |
| d = sequence[j]; | |
| count = 1; | |
| } | |
| } | |
| ss.str(""); | |
| ss << count << d; | |
| result += ss.str(); | |
| sequence = result; | |
| } | |
| return sequence; | |
| } | |
| int main() | |
| { | |
| cout << countAndSay(1) << endl; | |
| cout << countAndSay(2) << endl; | |
| cout << countAndSay(3) << endl; | |
| cout << countAndSay(4) << endl; | |
| cout << countAndSay(5) << endl; | |
| return 0; | |
| } |
by