Problème
Les puissances de deux grandissent vite : 2^64 a déjà 20 chiffres et 2^2000 en a plus de 600. Calculez 2^n exactement et additionnez ses chiffres décimaux. Sans grands entiers, stockez le nombre dans un tableau de chiffres et doublez-le n fois.
Implémentez digit_sum_power_of_two(n).
Entrée
n : l'exposant.
Sortie
Renvoyez la somme des chiffres décimaux de 2^n.
Contraintes
0 ≤ n ≤ 2000
Exemples
Entrée :
n = 10
Sortie attendue :
expected = 7
Entrée :
long long n = 10;
Sortie attendue :
long long expected = 7;
Entrée :
long n = 10;
Sortie attendue :
long expected = 7;
Explication
2^10 = 1024 et 1 + 0 + 2 + 4 = 7.
Entrée :
n = 0
Sortie attendue :
expected = 1
Entrée :
long long n = 0;
Sortie attendue :
long long expected = 1;
Entrée :
long n = 0;
Sortie attendue :
long expected = 1;
Explication
2^0 = 1, donc la somme des chiffres vaut 1.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
2^n, c'est 1 doublé n fois.
Indice 2
Stockez les chiffres en commençant par celui des unités, pour que les retenues se propagent vers la fin du tableau.
Indice 3
N'additionnez les chiffres qu'une fois tous les doublements terminés.
Complexité attendue
temps O(n²), espace supplémentaire O(n)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.