Count and Say
The count-and-say sequence starts with "1" and each subsequent term describes the previous:
- 1: "1"
- 2: "11" (one 1)
- 3: "21" (two 1s)
- 4: "1211" (one 2, one 1)
Given n, return the nth term.
Example
Input
4
Output
1211
Reasoning
- Input:
nis a position in the sequence. Here , so we need the 4th term, starting from term 1 = "1". - Reading a term aloud: split it into runs (maximal blocks of one digit side by side) then say each run as "how many, which digit". Write down the count followed by the digit.
- Term 1 → 2: "1" is one run of a single 1, read "one 1" → "11".
- Term 2 → 3: "11" is one run of two 1s, read "two 1s" → "21".
- Term 3 → 4: "21" has two runs, a single 2 and then a single 1, read "one 2, one 1" → "1211". That is the output
1211, and getting there took readings. - Output: a string of digits, not a number. Notice that runs are only about adjacent digits: the next term reads "1211" as three runs (one 1, one 2, two 1s) and becomes "111221", even though 1 appears three times in total.
Constraints
- 1 <= n <= 30