Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Recursive Approach 
3.1.
Algorithm
3.2.
Dry Run
3.3.
Code in C++
3.4.
Complexity
4.
Iterative Approach 
4.1.
Algorithm
4.2.
Dry Run
4.3.
C++ Code
4.4.
Complexity
5.
Dynamic Programming Approach
5.1.
Algorithm
5.2.
Dry Run
5.3.
C++ code
5.4.
Complexity
6.
Frequently asked questions
6.1.
What is a string?
6.2.
How can you find the length of a string in C++?
6.3.
What is the difference between a character and a string?
6.4.
How can you compare two strings in C++?
6.5.
What is dynamic programming?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Count and Say

Author Rishabh
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

The count and say sequence is the sequence of the below integers 1 is said as One 1’s(1 is one in number), hence written as 11. Now 11 is said as Two 1’s, hence written as 21. 21 is said as 'One 2’s, One 1’s', so written as 1211. The sequence continues with 111221, 312211, and so on.

intro image

In this problem, you'll be given an integer 'N', and you have to return the count and say sequence for 'N'. Now let’s jump to the problem statement.

Problem Statement

Ninjas have been given an integer N in the form of a string. You need to check the count and say sequence of N.

Example

Input 

N = 4

Output

“1211”

Explanation

The count and say sequence for N = 1 is “1”. Now count and say sequence for N = 2 is “11” as 1 is appearing once for N = 1. Now count and say for N = 3 is “21” as 1 is appearing two times for N = 2. For N = 4, count and say is “1211” as 2 is appearing once and 1 is appearing once. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Recursive Approach 

The key part of the solution is if we have the sequence string of 'N - 1’, then find the sequence for 'N'.
Function say() will take the sequence generated by countAndSay(N - 1) and return the sequence for countAndSay(N).

Algorithm

  1. A function is named “say” that takes the previous sequence as input and returns the count and say sequence for N.
     
  2. Initialize a counter to 1 and an empty string “output” for the count and say the sequence of N.
     
  3. For each character in the previous sequence, check if the next character is identical. If so, increase the counter.
     
  4. If the next character is different, concatenate the counter and the character to the output string.
     
  5. Reset the counter to 1 for the next group.
     
  6. Return the output string.
     
  7. Now another function named "countAndSay" is called that takes an integer N as input and returns the count and say sequence for N.
     
  8. If N is 1, return "1" as the base case.
     
  9. Otherwise, call the "countAndSay" function recursively with N-1 to get the previous sequence.
     
  10. Use the "say" function to generate the count and say sequence for N from the previous sequence.
     
  11. Return the count and say sequence for N.

Dry Run

dry run 1 working
  • The function countAndSay(4) is called.
    • Inside countAndSay(4), the base case is not met as N is not equal to 1, so the function calls countAndSay(3).
       
    • Inside countAndSay(3), the base case is again not met as N is not equal to 1, so the function calls countAndSay(2).
       
    • Inside countAndSay(2), the base case is again not met as N is not equal to 1, so the function calls countAndSay(1).
dry run 2 - recursive approach base case
  • Inside countAndSay(1), the base case occurs when N is equal to 1, so the function returns "1".
dry run 3
  • countAndSay(2) receives "1" as the previous sequence and calls the say function.
     
  • Inside the say function, the counter is initialized to 1 and the output string is initialized to an empty string.
    • Since there is only one character in the sequence, the else block is executed ,and "11" is appended to the output string.
       
  • The say function returns "11" to countAndSay(2).
dry run 4
  • countAndSay(3) receives "11" as the previous sequence and calls the say function.
    • Inside the say function, the counter is initialized to 1, and the output string is initialized to an empty string.
       
    • The first character is "1", which is followed by another "1". The if block is executed, and the counter is incremented to 2.
       
    • The for loop iterates to the end of the sequence, and the else block is executed. "21" is appended to the output string.
       
  • The say function returns "21" to countAndSay(3).
dry run 5
  • countAndSay(4) receives "21" as the previous sequence and calls the say function.
    • Inside the say function, the counter is initialized to 1, and the output string is initialized to an empty string.
       
    • The first character is "2", which is followed by another "1". The if block is executed, and the counter is incremented to 2.
       
    • The second character is "1", which is followed by another "1". The if block is executed, and the counter is incremented to 3.
       
    • The for loop iterates to the end of the sequence, and the else block is executed. "1211" is appended to the output string.
       
  • The say function returns "1211" to countAndSay(4).
dry run 6
  • The countAndSay(4) function returns "1211" to the main() function.

Code in C++

#include <iostream>
using namespace std;
/* 
   Function say() takes count and say sequence
   of ‘N - 1’ and return count and say sequence
   for ‘N’.
*/
string say(string prevSequence){
    // Initialize COUNTER = 1. Count of numbers in a group.
    int counter = 1;
    
    // Initialize sequence for ‘N’.
    string output;
    
    for (int i = 0; i < prevSequence.length(); i++){
        /*
            Check if the consecutive character is identical.
            In this case, increase the ‘COUNTER’.
        */
        if (i + 1 < prevSequence.length() && prevSequence[i] == prevSequence[i + 1]){
            counter++;
        }
        
        /* 
            End of a Group. Concatenate the count
            of the numbers in the group and the number.
        */
        else{
            output += to_string(counter) + prevSequence[i];
            // Start of the next Group.
            counter = 1;
        }
    }

    // Return count and say sequence for N.
    return output;
}

// Function to find the count and say sequence for ‘N’.
string countAndSay(int n){
    // Base Case.
    if (n == 1){
        return "1";
    }
    
    // Find the count and say sequence for ‘N - 1’.
    string prevSequence = countAndSay(n - 1);

    /*
        Now, using the count and say sequence
        of ‘N - 1’, find the count and say 
        sequence for N.
    */
    string sequence = say(prevSequence);
    return sequence;
}

int main(){
    int n=4;
    string sequence = countAndSay(n);
    cout << "Count and Say sequence for " << n << " is: " << sequence << endl;

    return 0;
}


Output

output 1

Complexity

Time Complexity
O(N2 ), where ‘N’ is the input number.
Since we are looping for N times, it will be N*N = N^2.

Space Complexity
O(N), where ‘N’ is the input number.
Since there are ‘N’ function calls in the recursion stack.

Read More - Time Complexity of Sorting Algorithms, and Euclid GCD Algorithm

Iterative Approach 

We'll implement the above recursive solution iteratively. So the say() function will not change. The logic of this approach is similar to approach 1.

Algorithm

  1. A function ‘say’ is called that takes a previous sequence as input and returns the count and say sequence for 'n'.
     
  2. Initialize a counter variable to 1 and an “output” variable to an empty string.
     
  3. Loop through the input sequence:
    • If the consecutive character is the same, increase the counter.
    • If the consecutive character is different, concatenate the count and the character to the output variable and reset the counter to 1.
       
  4. Return the output variable.
     
  5. Introduce a  function 'countAndSay' that takes an integer 'n' as input and returns the count and say sequence for 'n'.
     
  6. Initialize the sequence variable to “1”.
     
  7. Loop through 1 to ‘n-1’ and find the next count and say sequence using the previous sequence.
     
  8. Return the sequence variable.

Dry Run

  • The code defines two functions, say() and countAndSay(), to generate the count and say sequence for a given integer n.
     
  • The main function sets n=4 and calls countAndSay(4).
     
  • countAndSay(4) initializes the sequence variable to "1", and loops through i from 1 to 3.
     
  • In the first iteration (i=1), say("1") is called and generates the output string "11", which is assigned to the sequence variable.
dry run 2 - 1
  • In the second iteration (i=2), say("11") is called and generates the output string "21", which is assigned to the sequence variable.
dry run 2 - 2
  • In the third iteration (i=3), say("21") is called and generates the output string "1211", which is assigned to the sequence variable.
dry run 2 - 3
  • The final sequence variable, which contains the count and say sequence for n=4, is printed as "1211".
dry run 2 - 4

C++ Code

#include <iostream>
using namespace std;

/*
    Function say() takes count and say sequence
    ‘N - 1’ and returns count and say sequence for ‘N’.
*/
string say(string prevSequence){
    // Initialize COUNTER = 1. Count of numbers in a group.
    int counter = 1;
    
    // Initialize sequence for ‘N’.
    string output;
    
    for (int i = 0; i < prevSequence.length(); i++){
        /*
            Check if the consecutive character is the same.
            In this case, increase the ‘COUNTER’.
        */
        if (i + 1 < prevSequence.length() && prevSequence[i] == prevSequence[i + 1]){
            counter++;
        }
        
        /* 
            End of a Group. Concatenate the count
            of the number's in the group and the number.
        */
        else{
            output += to_string(counter) + prevSequence[i];
            // Start of the next group.
            counter = 1;
        }
    }
    // Return count and say sequence for ‘N’.
    return output;
}

//Function to find the count and say sequence for ‘N'.
string countAndSay(int n){
    // Initialize the sequence BASE CASE.
    string sequence = "1";

    /*
        Now loop through 1 to ‘N’ and find
        the next count and say sequence using 
        the previous sequence.
    */
    for (int i = 1; i < n; i++){
        sequence = say(sequence);
    }

    // Return count and say sequence for ‘N’.
    return sequence;
}

int main(){
    int n=4;
    string sequence = countAndSay(n);
    cout << "Count and Say sequence for " << n << " is: " << sequence << endl;
    return 0;
}


Output

output 2

Complexity

Time Complexity
O(N2 ), where ‘N’ is the input number.
Since we are looping from 1 to ‘N’ and for each ‘N’, we find the sequence in O(N).

Space Complexity
O(1)
Space complexity is O(1) because we are not using any auxiliary space.

Dynamic Programming Approach

This approach generates the nth row of the count and say sequence by storing each row in a vector. It starts with the first row as n=1 and counts the consecutive characters. Finally, it returns the nth row of the sequence. 

Algorithm

  1. Create a vector of strings to store the result and assign the first element as “1”, which is the first row of the countAndSay sequence.
     
  2. Use a for loop starting from i = 1 till the nth row
    • For every iteration, create an empty string temp to store the next row.  
       
    • Using another for loop, iterate through the i-1th element stored in the vector.
       
    • Now use a while loop to count the number of consecutive characters of the same character.
       
  3. Once while loop is complete add count of consecutive occurrences and the current character to a temporary string.
     
  4. Once the inner for loop is over add the temporary string to the vector of strings as the ith element.
     
  5. Finally after the outer for loop is completed return the nth element of the vector of strings.

Dry Run

  • The first element of the dp vector, dp[1] is set to “1“ which represents the first row of the countAndSay sequence.
dry run 3 - 1
  • A loop is used to generate the remaining rows. The loop variable ‘i’ starts from i = 2 and goes to ‘n’ which is 4 in this case.
    • Another loop is used to iterate through the characters of the previous row which is “1” and a counter is initialized to 1.
       
    • The loop variable is then incremented to move to the next character of the previous row, which is the end of the previous row.
       
  • Since there are no more characters to compare the “counter” and the current character is added into a string “curr” which is “11”.
dry run 3 - 2
  • Now dp[2] is set to “11” which represents the second row of the countAndSay sequence.
     
  • Similar steps are followed, since 1 appears two times in the dp[2]. Therefore, the “counter” and the current character is added to the string “curr” which is “21”.
dry run 3 - 3
  • Now dp[3] is set to “21” which represents the third row of the countAndSay sequence.
     
  • Similarly, 2 appears once in dp[3] and the current character is not equal to the next character. So we append “12” to the “curr”. For the second character, 1 appears once so we append count and character to “curr” which is “11”. So the “curr” finally becomes “1211”.
dry run 3 - 4
  • The output of countAndSay for n=4 is 1211.

C++ code

#include <iostream>
#include <string>
#include <vector>
using namespace std;

string countAndSay(int n){
    // Make a dp vector to store each row
    vector<string>dp(n+1,"");
    
    // Initialize dp[1] to "1"
    dp[1]="1";
    
    // Iterate from i = 2 to n
    for(int i=2;i<=n;i++){
        // Get previous row as string 
        string curr = dp[i-1];
        
        // Initialize an empty string for next row 
        string next = "";
        /*
            Initialize counter to 1 for counting
            the consecutive characters
        */
        int counter = 1;
        
        // Iterate in previous row 
        for(int j=1;j<curr.size();j++){
            /*
                If current character is same as previous
                character, increment counter
            */
            if(curr[j-1] == curr[j]){
                counter++;
            }
            
            // If not equal, add to the next row
            else{
                next += to_string(counter) + curr[j-1];
                counter = 1;
            }
        }
        // Add final counter and charcter to the next string
        next += to_string(counter) + curr.back();
        
        // Store the next row
        dp[i] = next;
    }
    // Return the nth row
    return dp[n];
}

int main(){
    int n=4;
    string sequence = countAndSay(n);
    
    // Call the function and print the result.
    cout << sequence << endl;
    return 0;
}


Output

output 3

Complexity

Time Complexity

O(N * M ) 
Where ‘N’ is the input number and ‘M’ is the maximum length of the row in the count and say sequence

Space Complexity

O(N * M)
Where ‘N’ is the input number and ‘M’ is the maximum length of the row in the count and say sequence. Space complexity is O(N * M) because we are storing the strings in a vector.

Frequently asked questions

What is a string?

A string is a group of characters stored as a variable. It is enclosed in double quotes.

How can you find the length of a string in C++?

You can use the ‘length()’ method of the string class in C++ to find the length of a string. We can also use the ‘size()’ and ‘strlen()’ functions.

What is the difference between a character and a string?

A character is a single symbol or letter, while a string is a sequence of characters.

How can you compare two strings in C++?

You can use the ‘compare()’ method to compare two strings. We can also use operators ‘==’ and ‘!=’ to compare. We can also use the ‘strcmp()’ function when using string.

What is dynamic programming?

Dynamic programming refers to breaking down big problems into smaller subproblems and saving each subproblem for future reference.

Conclusion

In this blog, we learned the count and say problem. We have implemented the problem in C++ programming language, starting from a naive approach to the most optimized approach.

For more string data structure articles, you can refer following links:

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!

Live masterclass