Problème
Commencez avec n. S'il est pair, divisez-le par 2 ; s'il est impair, multipliez-le par 3 et ajoutez 1. Répétez jusqu'à ce que la valeur atteigne 1. Incluez à la fois la valeur de départ et le 1 final dans votre réponse.
Implémentez collatz_sequence(n).
Entrée
n : L'entier de départ strictement positif.
Sortie
Retournez la suite complète dans l'ordre.
Contraintes
1 ≤ n ≤ 10 000. Pour toute entrée dans cet intervalle, la suite atteint 1 selon cette règle ; toutes les valeurs de la suite tiennent dans un entier signé 64 bits.
Exemples
Entrée :
n = 6
Sortie attendue :
expected = [6, 3, 10, 5, 16, 8, 4, 2, 1]Entrée :
long long n = 6;
Sortie attendue :
std::vector<long long> expected = {6, 3, 10, 5, 16, 8, 4, 2, 1};Entrée :
long n = 6;
Sortie attendue :
long[] expected = new long[] {6, 3, 10, 5, 16, 8, 4, 2, 1};Explication
6 est pair, donc il devient 3. Puis 3 devient 10. Continuez à appliquer la règle jusqu'à 1.
Entrée :
n = 1
Sortie attendue :
expected = [1]Entrée :
long long n = 1;
Sortie attendue :
std::vector<long long> expected = {1};Entrée :
long n = 1;
Sortie attendue :
long[] expected = new long[] {1};Explication
La valeur de départ est déjà 1, donc aucune transformation n'est nécessaire.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
La suite est générée en appliquant répétitivement une règle selon que le nombre courant est pair ou impair.
Indice 2
Ajoute chaque nouvelle valeur jusqu’à atteindre 1.
Indice 3
Attention : la valeur de départ et le 1 final doivent tous deux apparaître dans le résultat.
Complexité attendue
O(k) time, O(k) extra space, where k is the sequence length
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.