Pattern visualizer

Count and Say

There is no formula here and no shortcut: term k only exists once term k-1 has been built, so the work is n-1 rounds of the same tiny job. That job is run-length encoding — sweep the string once, and every time a character repeats, swallow the repeats instead of restarting. The count of a run and the character itself get appended as a pair, which is literally what saying "three ones" writes down as 31. Get the run boundary right and the whole problem is done, because everything else is just doing it again on the result. Animated on: n = 6 — the sequence starts at "1" and every term describes the one before it, so return the 6th term..

Each term is the previous term read out loud, run by run

time O(n * L) where L is the length of the longest termspace O(L)step 1 / 14

[0]

line 2

Term 1 is the seed "1". Every later term is produced by READING the previous one out loud, so nothing but this string is ever given to us.

Pseudocode

1FUNCTION countAndSay(n):
2  term <- "1"
3  FOR k <- 2 TO n:
4    next <- ""
5    i <- 0
6    WHILE i < LENGTH(term):
7      start <- i
8      WHILE i < LENGTH(term) AND term[i] = term[start]:
9        i <- i + 1
10      APPEND (i - start) AND term[start] TO next
11    term <- next
12  RETURN term

← / → step · space play · Home restart

Where to practice Strings

Practice Strings problems All Strings problems Back to roadmap