CODEWITHSUNDEEP
c
user8354599
user8354599

Reputation:

Efficiently add numbers divisible by 3 or 5

List the sum of numbers that are multiples of either 3 or five, below a given number.

Here's my code, couldn't find anything unnecessary. But hackerrank says it has terminated due to time out, time limit is 2 seconds to give the expected output. Input first line contains 't' that denotes the number of test cases. This is followed by lines, each containing an integer. 

#include <stdio.h>
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;
}

Input 

2
10
100

Output must be

23
2318

If we list all the natural numbers below 10 that are multiples of 3 or 5, then the sum of these multiples is 23.

Upvotes: 1

Views: 7530

Answers (3)

Andrey Tyukin
Andrey Tyukin

Reputation: 44918

Here are a few hints and links for everyone:

  • There are m = (a - 1) / k numbers below a that are divisible by k (with integer division).
  • Their sum is m * (m + 1) / 2 * k (by Gaussian sum formula, link to German wiki - they seem to like Gauß more).

  • The sum of all numbers smaller than a divisible by 3 or 5 is the same as 

    + 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`

    (by inclusion-exclusion principle)

This gives you the constant-time algorithm:

#include <stdio.h>
/* 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<t; b++){
        printf("input = %d\n", arr[b]);
        printf("%d\n", calc(arr[b]));
    }
    return 0;
}

Example:

$ ./sumFizzBuzz 
4
10
100 
1000
10000
23
2318
233168
23331668

Sorry, this had to be, there was just too much loops-&-nonsense here and on the "nearly duplicate" question...

Upvotes: 1

CaptainOfHacks
CaptainOfHacks

Reputation: 36

#include <stdio.h>
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<t; b++)
    {
       calc_faster(arr[b]);
    }
    return 0;
}

Upvotes: -3

Nicholas Pipitone
Nicholas Pipitone

Reputation: 4142

Option 1

You're trying to sum all multiples of 3 or 5 under a given number. Have you tried thinking about how you could do it without a for loop? Let's try. Hm, "3 or 5" is a lot to think about. Let's simplify it, and try to sum all multiples of 3 under 99:

3+6+9+12+15+...+99

How could you optimize this addition to avoid a for loop? (Do that before continuing to read)

Now, if you know how to sum all multiples of 3 under a given n, does that give you a way to sum all multiples of 3 or 5 under a given n? Hm, what overlaps between the sequences 3,6,9,12,15,...,n and 5,10,15...,n? Maybe if you can sum multiples of 3 under n, and sum multiples of 5 under n, then you can get rid of that overlap?

Option 2

Okay, let's say I know the sum of multiples of 3 or 5 under the number n. Does that help me find the sum of multiples of 3 or 5 under the number n+1? Maybe I know what calc(n) is in terms of calc(n-1). If I could do that then that'll be great, because rather than recalculating calc(n-1), I could just save calc(n-1) instead. If only...

Upvotes: 5

Related Questions