Verifica se é possível visitar todos os elementos exatamente uma vez e retornar ao início.
Imagine um array onde cada elemento diz quantas posições pular. Valores positivos vão para a direita, negativos para a esquerda. O array é circular — se passar do final, volta ao início. A pergunta: começando no índice 0, consigo visitar todos os elementos exatamente uma vez e voltar ao índice 0? Parece complicado, mas a solução é direta. Siga os saltos, conte quantos elementos visitou, e verifique se terminou onde começou após n saltos.
“O truque é perceber que não precisa marcar posições visitadas. Se der n saltos e voltar ao 0, visitou todos.”
Faz exatamente n saltos, cada um em O(1).
n iterações × O(1) por iteração = O(n).
Só usa variáveis auxiliares. Sem estruturas extras.
Sempre precisa verificar todos os elementos.
A complexidade não muda com o input.
| Algoritmo | Tempo | Espaco | Melhor Para |
|---|---|---|---|
| Ciclo Único(atual) | O(n) | O(1) | Verificar ciclo hamiltoniano em array circular |
| Floyd Cycle Detection | O(n) | O(1) | Detectar ciclo em linked list |
| DFS para Ciclos | O(V+E) | O(V) | Detectar ciclo em grafos |
Pratique respondendo a perguntas comuns de entrevistas tecnicas. Clique em uma pergunta para iniciar uma sessao de pratica com IA.
1def has_single_cycle(array):Definição2 current_idx = 0Inicialização3 num_visited = 04 5 while num_visited < len(array):Loop Principal6 if num_visited > 0 and current_idx == 0:Verificação de Direção7 return False8 9 num_visited += 1Incremento10 current_idx = (current_idx + array[current_idx]) % len(array)Próximo Índice11 12 return current_idx == 0Retorno13