Pular para o conteúdo

Termo da sequência look-and-say

Fácil#recursion#run-length~15 min

A missão

Problema

A sequência look-and-say começa com “1”. Cada termo seguinte é formado lendo o termo anterior em voz alta, em sequências de dígitos iguais: “1” é um 1, o que dá “11”; “11” são dois 1, o que dá “21”; “21” é um 2 e depois um 1, o que dá “1211”. Dado n de pelo menos 1, retorne o n-ésimo termo como string.

Exemplos

Input:  n = 4
Output: "1211"
Input:  n = 5
Output: "111221"
Por quê: "1211" se lê como um 1, um 2, dois 1
Input:  n = 1
Output: "1"
Por quê: edge case: o primeiro termo já é dado, não há nada a descrever

Dicas

0 / 3

Tempo-alvo
O(1.31ⁿ)
Espaço-alvo
O(1.31ⁿ)

Restrições

  • n ≥ 1

Travou na ideia, e não no código? O básico de recursão explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado