Enumere la sum de los números que son múltiplos de 3 o cinco, debajo de un número dado.
Aquí está mi código, no pude encontrar nada innecesario. Pero hackerrank dice que ha finalizado debido a un tiempo de espera, el límite de tiempo es de 2 segundos para dar el resultado esperado. La primera línea de entrada contiene ‘t’ que denota el número de casos de prueba. A esto le siguen las líneas, cada una con un entero.
#include void calc(int a){ int sum = 0; for(int a0=1; a0<a; a0++){ if(a0%3==0 || a0%5==0){ sum+=a0; } } printf("%d", sum); } int main(){ int t; scanf("%d",&t); int arr[t]; for(int a0 = 0; a0 < t; a0++){ scanf("%d",&arr[a0]); } for(int b=0; b<t; b++){ calc(arr[b]); printf("\n"); } return 0; } Entrada
2 10 100
La salida debe ser
23 2318
Si enumeramos todos los números naturales por debajo de 10 que son múltiplos de 3 o 5, entonces la sum de estos múltiplos es 23.
Estás tratando de sumr todos los múltiplos de 3 o 5 bajo un número dado. ¿Ha intentado pensar en cómo podría hacerlo sin un bucle for? Intentemos. Hm, “3 o 5” es mucho para pensar. Simplifiquémoslo e intentemos sumr todos los múltiplos de 3 debajo de 99:
3+6+9+12+15+...+99
¿Cómo podría optimizar esta adición para evitar un bucle for? (Hacer eso antes de seguir leyendo)
Ahora, si sabes cómo sumr todos los múltiplos de 3 bajo una n dada, ¿te da una forma de sumr todos los múltiplos de 3 o 5 bajo una n dada? Hm, ¿qué se superpone entre las secuencias 3,6,9,12, 15 , …, n y 5,10, 15 …, n? ¿Tal vez si puedes sumr múltiplos de 3 en n, y sumr múltiplos de 5 en n, entonces puedes deshacerte de esa superposición ?
Bien, digamos que conozco la sum de los múltiplos de 3 o 5 debajo del número n. ¿Me ayuda eso a encontrar la sum de los múltiplos de 3 o 5 debajo del número n + 1? Tal vez sé qué calc (n) es en términos de calc (n-1). Si pudiera hacer eso, sería genial, porque en lugar de recalcular calc (n-1), podría guardar calc (n-1) en su lugar. Si solo…
Aquí hay algunos consejos y enlaces para todos:
m = (a - 1) / k números por debajo de a que son divisibles por k (con división entera). m * (m + 1) / 2 * k (por la fórmula de la sum de Gauss , enlace a la wiki alemana, parece que a Gauß les gusta más). La sum de todos los números más pequeños que a divisible por 3 o 5 es la misma que
+ the sum of all numbers smaller than `a` divisible by `3` + the sum of all numbers smaller than `a` divisible by `5` - the sum of all numbers smaller than `a` divisible by `15`
(por principio de inclusión-exclusión )
Esto le da el algoritmo de tiempo constante:
#include /* sums the numbers smaller than `a` that are divisible by `k` */ int s(int a, int k) { int m = (a - 1) / k; return m * (m + 1) / 2 * k; } /* sums the numbers smaller than a that are divisible by both 3 and 5 */ int calc(int a) { return s(a, 3) + s(a, 5) - s(a, 15); } int main(){ int t; scanf("%d", &t); int arr[t]; for(int a0 = 0; a0 < t; a0++){ scanf("%d", &arr[a0]); } for(int b=0; b
Ejemplo:
$ ./sumFizzBuzz 4 10 100 1000 10000 23 2318 233168 23331668
Disculpe, tenía que ser así, había demasiados bucles, y tonterías aquí y en la pregunta "casi duplicada" ...
#include void calc_faster(int a) { int mid=0,sum=0; for(unsigned int i = a-1;i>0;i--) {if(i%3==0) { if(i%5==0) { mid=i; break; } else sum+=i; } else if(i%5==0) sum+=i; } sum+=mid*(7*mid+15)/30; printf("%d\n",sum); } int main() { unsigned int t; unsigned int temp; scanf("%d",&t); unsigned int arr[t]; for(register unsigned int a0 = 0; a0 < t; a0++) { scanf("%d",&arr[a0]); } for(register unsigned int b=0; b