Count and Say Problem in DSA C

Mental Model

We describe a number by counting groups of the same digit and saying the count followed by the digit.

Analogy: Imagine reading a line of colored beads and saying aloud how many beads of each color appear in a row before the color changes.

1
↓
"one 1" -> 11
↓
"two 1s" -> 21
↓
"one 2, one 1" -> 1211

Dry Run Walkthrough

Input: n = 4 (generate the 4th term starting from '1')

Goal: Find the 4th term in the count and say sequence starting with '1'

Step 1: Start with base term '1'

1

Why: The sequence always starts with '1'

Step 2: Read '1' as 'one 1', so next term is '11'

11

Why: We count one '1' and say '11'

Step 3: Read '11' as 'two 1s', so next term is '21'

21

Why: We count two '1's and say '21'

Step 4: Read '21' as 'one 2, one 1', so next term is '1211'

1211

Why: We count one '2' then one '1' and say '1211'

Result:

1211

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Function to generate the next term from current term
char* nextTerm(const char* term) {
    int len = strlen(term);
    char* result = (char*)malloc(len * 2 + 1); // max size
    int resIndex = 0;
    int count = 1;

    for (int i = 1; i <= len; i++) {
        if (i < len && term[i] == term[i - 1]) {
            count++;
        } else {
            // Append count and digit to result
            resIndex += sprintf(result + resIndex, "%d%c", count, term[i - 1]);
            count = 1;
        }
    }
    result[resIndex] = '\0';
    return result;
}

// Function to generate nth term of count and say sequence
char* countAndSay(int n) {
    if (n == 1) {
        char* base = (char*)malloc(2);
        strcpy(base, "1");
        return base;
    }
    char* prev = countAndSay(n - 1);
    char* curr = nextTerm(prev);
    free(prev);
    return curr;
}

int main() {
    int n = 4;
    char* result = countAndSay(n);
    printf("%s\n", result);
    free(result);
    return 0;
}

if (i < len && term[i] == term[i - 1]) {

count consecutive same digits to group them

resIndex += sprintf(result + resIndex, "%d%c", count, term[i - 1]);

append count and digit to build next term

char* prev = countAndSay(n - 1);

recursively get previous term

char* curr = nextTerm(prev);

generate current term from previous

free(prev);

free memory of previous term to avoid leaks

Output

1211

Complexity Analysis

Time: O(m * n) because each term generation scans the previous term of length m, repeated n times

Space: O(m * n) due to storing strings for each term up to n

vs Alternative: Iterative approach can reduce recursion overhead but time complexity remains similar

Edge Cases

n = 1 (base case)

Returns '1' immediately without recursion

DSA C

if (n == 1) {

term with all identical digits (e.g., '111')

Counts all digits as one group correctly

DSA C

if (i < len && term[i] == term[i - 1]) {

term with alternating digits (e.g., '1212')

Counts each digit group separately

DSA C

else { resIndex += sprintf(result + resIndex, "%d%c", count, term[i - 1]); count = 1; }

When to Use This Pattern

When asked to generate a sequence where each term describes the previous term's digit groups, use the Count and Say pattern to build terms step-by-step.

Common Mistakes

Mistake: Not resetting count after appending a group
Fix: Reset count to 1 after appending count and digit

Mistake: Off-by-one error in loop causing missing last group
Fix: Loop until i <= length and handle last group in else block

Summary

Generates a sequence where each term describes the count of digits in the previous term.

Use when a problem requires describing groups of repeated digits in a sequence.

The key is to group consecutive digits and say their count followed by the digit.