# Count and Say sequence

In this article, we are going to see how to solve the Count and Say sequence in C++? This problem is one of the top interview problems that can be featured in top company coding rounds.
Submitted by Radib Kar, on January 09, 2019

Problem statement:

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...
```

Solution:

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
2. ```    if(n==0)
return "";
if(n==1)
return "1";
```
3. 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.
4. Print result for level 1. (As level >1 now)
5. Declare a temporary string only to get the current level result. Let the temporary string be temp.
6. 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
7. 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

```

How the program works?

```Let's solve an example for n=3
Base case not matched
Result="1"
Thus it prints "1" and proceeds for rest of two level
Output at level-1
1
--------------------------------------------------------

1st iteration
In the outer for loop
i=1 & i< 3
Length of result=1 (result="1")
Inner loop executes only once, since len=1
Thus count=1
temp =to_string(1) +"1"
="1"+"1" ="11"
result="11"
temp=""
output at level-2
11
So output printed up to now:
1
11
--------------------------------------------------------

2nd iteration
In the outer for loop
i=2& i< 3
Length of result=2 (result="11")
Inner loop executes twice, since len=2
Thus count=2 // "1" repeating twice, no other character
temp =""+to_string(2) +"1" ("" is temp previously updated, cleared basically)
="2"+"1" ="21"
result="21"
temp=""
output at level-3
21
So output printed up to now:
1
11
21
--------------------------------------------------------

3rd iteration
i=3 thus loop ends
Output is printed
Thus count and say sequence for n=3
1
11
21
```

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates