Count and Say

Count and Say in which we have given a number N and we need to find the Nth term of the count and say sequence. Firstly we need to understand what is count and say sequence. Firstly see some terms of the sequence:

1st term is “1”.

2nd term is “11”.

3rd term is “21”.

4th term is “1211”.

5th term is “111221”

6th term is “312211”…. and so on.

Input Format

Only a single line containing integer value N.

Output Format

Print the result in a string format. In another way, we say that print only one line containing the Nth term.

Constraints

• 1<=N<=50.

Example Input: 
5

Example Output:
111221

Explanation For Count and Say

Here we see a pattern in which we find the nth term by the use of the n-1th term. We need to traverse the n-1th term and add the answer to the nth term. In the n-1 term, we just count the number how many times come continuously. Then store that count in nth term and then the number which we traverse in the n-1th term. Here is the step by step implementation:

1st term: “1” which is our base case.

2nd term: counts_of the number present in n-1th term continuously. Here the count of “1” is 1. So, our second term is “11”.

3rd term: counts_of “1” in the n-1th term is 2. So, our 3rd term is “21”.

4th term: counts_of “2” in the  n-1th term is 1 and count_of “1” is 1. So, our 4th term is “1211”.

5th term: counts_of “1” in the n-1th term is 1, then count_of “2” is 1, and count of the last continuous repeated number “1” is 2.

So, the 5th term is “111221”.

Implementation For Count and Say

/*C++ Implementation of Count and Say Problem*/ 
#include<bits/stdc++.h>
using namespace std;
int main() 
{ 
    int n;
    /*take N as input*/
    cin>>n;
    /*create a vector to store the count and say sequence terms till N.*/
    vector<string> v;
    for(int i=0;i<n;i++)
    {
        /*Base case: 1st term is "1".*/
        if(i==0)
        {
            v.push_back("1");
        }
        else
        {
            /*store the ith term in check string*/
            string check=v[i-1];
            int sz=check.size();
            /*i+1 th term*/
            string ins="";
            /*calculation to find the i+1th term*/
            for(int j=0;j<sz;j++)
            {
                /*freq store the freq of the number which we traverse in the ith term*/
                int freq=1;
                /*number which we traverse in the ith term*/
                char ch=check[j];
                /*move to the next value in ith term and count the frequency of number(ch)*/
                while(j+1<sz&&check[j]==check[j+1])
                {
                    freq++;
                    j++;
                }
                /*convert frequency of ch into string and add to i+1th term*/
                ins+=to_string(freq);
                /*Now, add the number(ch) to i+1th term*/
                ins+=ch;
            }
            /*push the i+1th term into the vector*/
            v.push_back(ins);
        }
    }
    /*Print the Nth term of count and say problem*/
    cout<<v[n-1]<<endl;
    return 0; 
}

15

311311222113111231131112132112311321322112111312211312111322212311322113212221

Time Complexity

Here time complexity can’t be fixed because if we take N>30 then its never possible to store the output string so for worst-case scenario time complexity is O(10^6).

References