Sumar eficientemente los números divisibles por 3 o 5.

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.

Opción 1

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 ?

opcion 2

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:

  • Hay m = (a - 1) / k números por debajo de a que son divisibles por k (con división entera).
  • Su sum es 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