Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

Example 1

Input

4

Output

1211

Example 2

Input

1

Output

1

Hints

  1. Build the terms one by one from "1".
  2. 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);
    }
}

Solve Count and Say online · All practice problems