Count and Say

Reported in interviews at Akuna Capital

Problem statement

The count-and-say sequence starts from "1", and each subsequent term is produced by reading off the previous term as consecutive runs of the same digit -- you say the count, then the digit. So "1" $\to$ "11" (one 1) $\to$ "21" (two 1s) $\to$ "1211" (one 2, one 1) $\to$ "111221" (one 1, one 2, two 1s), and so on. Given an integer $n$, return the $n$-th term of the sequence.

Constraints:

  • $1 \le n \le 30$.

Examples:

  • $n = 1 \to$ "1"
  • $n = 4 \to$ "1211"
  • $n = 5 \to$ "111221".
Show hint

What standard compression idea describes turning a string into (count, digit) pairs?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems