Practice › Strings
Count and Say
Medium · Strings · Asked at Amazon, Meta, Microsoft, Zoho
The count-and-say sequence starts with "1". Each next term reads aloud the previous one, grouping equal consecutive digits: "1" → one 1 → "11" → two 1s → "21" → one 2, one 1 → "1211" → … Print the n-th term.
Input
A single integer n.
Output
The n-th term.
Constraints
- 1 ≤ n ≤ 30
Example 1
Input
4
Output
1211
Example 2
Input
1
Output
1
Hints
- Build the terms one by one from "1".
- To read a term aloud, walk it in groups of equal consecutive digits and write "count" then "digit" for each group.
Approach
Simulate. For each step, scan the current string: extend a group while the next character equals the current one, then append group length followed by the digit. Use a string builder — the 30th term has about 4,500 characters.
Complexity: O(total length of all terms) time · O(length of the last term) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
string t = "1";
for (int step = 1; step < n; step++) {
string next;
for (size_t i = 0; i < t.size();) {
size_t j = i;
while (j < t.size() && t[j] == t[i]) j++;
next += to_string(j - i);
next += t[i];
i = j;
}
t = next;
}
cout << t << "\n";
return 0;
}Python solution
n = int(input())
t = "1"
for _ in range(n - 1):
out, i = [], 0
while i < len(t):
j = i
while j < len(t) and t[j] == t[i]:
j += 1
out.append(str(j - i) + t[i])
i = j
t = "".join(out)
print(t)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
int n = new Scanner(System.in).nextInt();
String t = "1";
for (int step = 1; step < n; step++) {
StringBuilder next = new StringBuilder();
for (int i = 0; i < t.length();) {
int j = i;
while (j < t.length() && t.charAt(j) == t.charAt(i)) j++;
next.append(j - i).append(t.charAt(i));
i = j;
}
t = next.toString();
}
System.out.println(t);
}
}