Count and Say Problem in DSA C - Build from Scratch

Count and Say Problem

📖 Scenario: Imagine you are working with a simple number game where each number describes the previous number's digits. This is called the "Count and Say" sequence. For example, starting with "1", the next number says "one 1" which is "11", then "two 1s" which is "21", and so on.

🎯 Goal: You will write a program in C that generates the nth term of the Count and Say sequence. You will start with the first term "1" and build up to the desired term by describing the previous term.

📋 What You'll Learn

Create a string variable to hold the current term starting with "1"

Create an integer variable n to represent which term to generate

Write a loop to generate terms from 2 to n by reading the previous term and building the next

Print the final term after generating it

💡 Why This Matters

🌍 Real World

The Count and Say sequence is a simple example of run-length encoding, a technique used in data compression.

💼 Career

Understanding string manipulation and loops in C is essential for many programming jobs, especially those involving low-level data processing.

1

Setup initial term and target term

Create a string variable called current initialized to "1" and an integer variable called n set to 5.

DSA C

char current[100] = "1";
int n = 5;
// Your code here

Hint

Use a character array to hold the string "1" and an integer variable for n.

2

Add a temporary buffer for building next term

Create a character array called next with size 100 to store the next term during generation.

DSA C

char current[100] = "1";
int n = 5;
char next[100];
// Your code here

Hint

This buffer will hold the new term while you build it from the old term.

3

Generate Count and Say terms up to n

Write a for loop from i = 2 to i <= n. Inside, use variables count, j, and k to read current and build next by counting consecutive digits. After building next, copy it back to current.

DSA C

char current[100] = "1";
int n = 5;
char next[100];

// Your code here

Hint

Use nested loops to count repeated digits and build the next term. Then copy next back to current.

4

Print the final Count and Say term

Write a printf statement to print the string current.

DSA C

char current[100] = "1";
int n = 5;
char next[100];

for (int i = 2; i <= n; i++) {
    int j = 0, k = 0;
    while (current[j] != '\0') {
        char digit = current[j];
        int count = 1;
        while (current[j + 1] == digit) {
            count++;
            j++;
        }
        next[k++] = count + '0';
        next[k++] = digit;
        j++;
    }
    next[k] = '\0';
    int m = 0;
    while (next[m] != '\0') {
        current[m] = next[m];
        m++;
    }
    current[m] = '\0';
}

// Your code here

Hint

The 5th term of the Count and Say sequence starting with "1" is "111221".