Count and Say problem C++

January 3, 2022

Count and say

Today in this article we will be discussing how to solve Count and say problem .

Lets understand this with the help of example :- 

in this problem we need to first print the occurrence or count then the  number for which we have calculated the count.

Lets understand this with the help of example.

  • Input: n = 4
  • Output: “1211”

Explanation:

countAndSay(1) = “1”  , countAndSay(2) = say “1” = one 1 = “11” , countAndSay(3) = say “11” = two 1’s = “21”  , countAndSay(4) = say “21” = one 2 + one 1 = “12” + “11” = “1211”

Count and say

Algorithm

  • First let’s say if the value of n  is 1 then we will return “1” & if the value of n is 2 then will return “11” that is the base case
  • To find the next sequence we will add a delimiter $ at the end of the string just to check the last element and initialize c = 1as every element must have at least 1 time occurrence.
  • Iterate the loop  from i=3 to i<n and initialize a temporary string s and will again run a loop from j=1 to size of j<the s.length() 
  • Inside the loop check if the s[j] != s[j-1] if the previous element is not equal to the the current element then add the value of count after converting it into string and then add the data for which you have counted the occurrence and again set the value of count c =1 
  • Otherwise if the value of s[j]==s[j-1] then just increment the value of  c and then out of the loop store the value of t in s.
  • And then return the string s that is the final answer.
Count and Say problem

C++ Code :-

#include<iostream.h> 

using namespace std;

string countAndSay(int n) {
  if (n==1)
   return "1";

  if(n==2)
   return "11";

  string s = "11";
  for(int i=3;i<=n;i++){
    string t="";
    s=s+'&';
    int c=1;

     for(int j=1;j<s.length();j++){

        if(s[j]!=s[j-1]){
          t=t+to_string(c);
          t=t+s[j-1];
          c=1;
        } 

        else
          c++;
       }
    s=t;
   }
  return s;
 }

int main()
{
  int n=4;
  cout<<countAndSay(n);
  return 0;
}

Output:-

1211
//Since the value of n is 4 so the solution is 1211