Home »
Interview coding problems/challenges
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 countandsay sequence is the sequence of integers with the first five terms as following:
 1
 11
 21
 1211
 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:
Prerequisite:
to_string function: In C++ we have an inbuild 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:
 Check for base cases
if(n==0)
return "";
if(n==1)
return "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.
 Print result for level 1. (As level >1 now)
 Declare a temporary string only to get the current level result. Let the temporary string be temp.

For i=1:n //iterate for rest of the rows
 Store the length of result (carrying the result of last processed level actually) string length
 Let the length be len

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
 Current level string is processed in temp, So update result=temp
 Print result
 Clear temp for further levels
 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 n1 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 level1
1

1^{st} 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 level2
11
So output printed up to now:
1
11

2^{nd} 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 level3
21
So output printed up to now:
1
11
21

3^{rd} iteration
i=3 thus loop ends
Output is printed
Thus count and say sequence for n=3
1
11
21
TOP Interview Coding Problems/Challenges