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 [Last updated : March 20, 2023]

Problem Description

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

    if(n==0)
        return "";
    if(n==1)
        return "1";

2. 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.
3. Print result for level 1. (As level >1 now)
4. Declare a temporary string only to get the current level result. Let the temporary string be temp.
5. 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
6. End For

C++ implementation for Count and Say sequence

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

int countAndSay(int n)
{
    //base cases
    if (n == 0)
        return 0;
    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
    countAndSay(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

---