166. Say What You See
In a counting game, the first call is 1. Every next call describes the previous one by reading its digits aloud group by group: a group is a maximal run of the same digit, and it is spoken as the length of the run followed by the digit. So the call 111221 is read as three ones, two twos and one one, which is written 312211.
Given n, return the n-th call of the game as a string; the first call is 1. The calls grow by about thirty percent each time, so build every call from the one before it, and collect the pieces in a list or a string builder instead of gluing text onto the front of a long string.
Example 1
- Input:
- n = 5
- Output:
- "111221"
- Explanation:
The calls are 1, 11, 21, 1211 and 111221, so the fifth one is 111221.
Example 2
- Input:
- n = 7
- Output:
- "13112221"
- Explanation:
After 111221 comes 312211, and reading that aloud gives 13112221.
Constraints
1 ≤ n ≤ 42
The 42nd call has 107312 characters
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(L)
- Space
- O(L)