Q:

# For a given n, Print the count and say sequence using c++

The count-and-say sequence is the sequence of integers with the first five terms as following:

1. 1
2. 11
3. 21
4. 1211
5. 111221

1 is read off as "one 1" or 11.

11 is read off as "two 1s" or 21.

21 is read off as "one 2, then one 1" or 1211.

That means every integer (repeated continuously) is read off with its count value.

For a given n, Print the count and say sequence.

Examples

```For n=0
It's a blank string
-------------------------

For n=1
Its "1"
-------------------------

For n=2, we need to evaluate the previous string which is for n=1
For n=1
"1"
So one "1"
Thus For n=2
"11"
-------------------------

Needless to say for n=3
Evaluating n=2 results in two "1"->"21"
So on...```

Pre-requisite:

to_string function: In C++ we have an in-build function which converts a numerical value to its string representation. Like 1 is converted to "1" (the first 1 is of int datatype, while the second is of string datatype).

prototype of the function is:

```    string to_string (int value);
```

Algorithm:

1. Check for base cases
```    if(n==0)
return "";
if(n==1)
return "1";
```
1. For rest of the cases, it must start from 1, thus initialize result with string "1". result is our output string which will be printed for each label.
2. Print result for level 1. (As level >1 now)
3. Declare a temporary string only to get the current level result. Let the temporary string be temp.
4. For i=1:n //iterate for rest of the rows
1. Store the length of result (carrying the result of last processed level actually) string length
2. Let the length be len
3. For j=0:len
Initialize a count variable to store repeating number's frequency
While same number( character in result string actually) is repeating
Increment count
End While
Convert count value to string using the to_string function.
temp=temp+ to_string(count) + result[j] //count comes first
End FOR
4. Current level string is processed in temp, So update result=temp
5. Print result
6. Clear temp for further levels
5. End For

C++ implementation

``````#include <bits/stdc++.h>
using namespace std;

void countAndSay(int n) {
//base cases
if(n==0)
return "";
if(n==1)
return "1";
//for rest of the cases, it must start from 1
//initialize result with string "1"
string result="1";
cout<<result<<endl;
string temp;//temporary string to hold levelwise result
for(int i=1;i<n;i++){ //iterate for n-1 rows
//iterate upto current string length
int len=result.length();
for(int j=0;j<len;j++){
int count=1;//initialize count as 1
//find count for repeated number
while(j+1<len && result[j]==result[j+1] ){
count++;
j++;
}
//convert the count to string and add to
//temprary result, then add original no
temp+=to_string(count)+result[j];
}
//assign temporary result to original result
//& print for current level
result=temp;
cout<<result<<endl;
//clear the temporary result
temp="";
}
}

int main(){
int n;

cout<<"count and Say problem.....\n";
cout<<"enter n, no of rows\n";
cin>>n;
//function to print count and say sequence
coutAndSay(n);

return 0;
}
``````

Output

```First run:
count and Say problem.....
enter n, no of rows
3
Printing Count and Say sequence...
1
11
21

Second run:
enter n, no of rows
6
Printing Count and Say sequence...
1
11
21
1211
111221
312211

Third run:
count and Say problem.....
enter n, no of rows
10
Printing Count and Say sequence...
1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211
```