38 Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:

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.
Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string

  • The biggest part here was discovering how to count duplicates and not go over range of the vector. Basically, I counted the number of duplicates, appended it to a new string, and then moved on to analyize the next two characters. Dup is always reset to 1, because it is clear there is at least of the numbers.

string countAndSay(int n) {
    if (n < 0) cout << "invalid number" << endl;

    int num_dup = 1;
    string temp = "1";
    string new_temp = "";

    // tip: if you're going to use a while loop for counting,
    // dont! A for loop will always suffice.
    for (int i = 1; i < n; i++) {
        // count of the number of duplicates
        // to make sure we get everything, its smarter
        // to start from j - 1 as opposed to something like
        // for (int j = 0; j < temp.size() - 1; j++)
        for (int j = 1; j < temp.size(); j++) {
            if (temp.at(j - 1) == temp.at(j))
                num_dup++;
            else {
                new_temp += to_string(num_dup);
                new_temp += temp.at(j - 1);
                num_dup = 1;
            }
        }
        new_temp += to_string(num_dup);
        new_temp += temp.at(temp.size() - 1);

        temp = new_temp;
        new_temp.clear();
        num_dup = 1;
    }

    return temp;
}

Last updated