Count and say
HardDescribe the previous term out loud
Problem
Generate the nth term of the count-and-say sequence, where each term describes the previous one.
Read the previous term aloud: say how many of each digit run there are, in order.
The idea
Each term is generated by reading the previous one in runs: count the consecutive identical digits and emit the count followed by the digit. There is no closed form — you must build every term from 1 up to n.
The trick
- Group consecutive equal characters and emit count then character.
- Terms grow quickly, so this is only practical for small n.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — n=4 Values: 4.
1s='1'2repeat n-1 times: s = run-length-encode(s) // count then digit3return sInput
- array
- [4]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- n = 4
- Output:
- "1211"
- Explanation:
- 1 → 11 → 21 → 1211.
Example 2
- Input:
- n = 1
- Output:
- "1"
- Explanation:
- The seed is 1.
Example 3
- Input:
- n = 5
- Output:
- "111221"
- Explanation:
- The 5th term is 111221.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.