Skip to main content
added 18 characters in body
Source Link
Paul
  • 41
  • 3

This code is extremely inefficient. Using some basic math we can reduce runtime to constant time complexity. For any n (in this case 1000), we can predict the number of numbers < n and divisible by 3 or 5:

  • numbers divisible by 3: lowerbound(n / 3)
  • numbers divisible by 5: lowerbound(n / 5)

The sum of all numbers divisible by 3 or 5 can then be predicted using eulers formula:
the sum of all numbers from 1 to n is n(n + 1)/2. Thus the sum of all numbers n divisible by 3 is:

int div_3 = (n / 3)
int sum_div_3 = div_3 * (div_3 + 1) / 2 * 3

Now there's only one point left: all numbers that are divisible by 3 and 5 appear twice in the sum (in the sum of all numbers divisible by 3 and the sum of all numbers divisble by 5). Since 3 and 5 are prim, all numbers that are divisible by 3 and 5 are multiples of 15.

int sum_div3_5(int n)
    int div_3 = (n - 1) / 3 , 
        div_5 = (n - 1) / 5 , 
        div_15 = (n - 1) / 15

    int sum = div_3 * (div_3 + 1) * 3 / 2 + //sum of all numbers divisible by 3
              div_5 * (div_5 + 1) * 5 / 2 - //sum of all numbers divisible by 5
              div_15 * (div_15 + 1) * 15 / 2

    return sum

I can't provide python code though.

This code is extremely inefficient. Using some basic math we can reduce runtime to constant time complexity. For any n (in this case 1000), we can predict the number of numbers < n and divisible by 3 or 5:

  • numbers divisible by 3: lowerbound(n / 3)
  • numbers divisible by 5: lowerbound(n / 5)

The sum of all numbers divisible by 3 or 5 can then be predicted using eulers formula:
the sum of all numbers from 1 to n is n(n + 1)/2. Thus the sum of all numbers n divisible by 3 is:

int div_3 = (n / 3)
int sum_div_3 = div_3 * (div_3 + 1) / 2 * 3

Now there's only one point left: all numbers that are divisible by 3 and 5 appear twice in the sum (in the sum of all numbers divisible by 3 and the sum of all numbers divisble by 5). Since 3 and 5 are prim, all numbers that are divisible by 3 and 5 are multiples of 15.

int sum_div3_5(int n)
    int div_3 = n / 3 , 
        div_5 = n / 5 , 
        div_15 = n / 15

    int sum = div_3 * (div_3 + 1) * 3 / 2 + //sum of all numbers divisible by 3
              div_5 * (div_5 + 1) * 5 / 2 - //sum of all numbers divisible by 5
              div_15 * (div_15 + 1) * 15 / 2

    return sum

I can't provide python code though.

This code is extremely inefficient. Using some basic math we can reduce runtime to constant time complexity. For any n (in this case 1000), we can predict the number of numbers < n and divisible by 3 or 5:

  • numbers divisible by 3: lowerbound(n / 3)
  • numbers divisible by 5: lowerbound(n / 5)

The sum of all numbers divisible by 3 or 5 can then be predicted using eulers formula:
the sum of all numbers from 1 to n is n(n + 1)/2. Thus the sum of all numbers n divisible by 3 is:

int div_3 = (n / 3)
int sum_div_3 = div_3 * (div_3 + 1) / 2 * 3

Now there's only one point left: all numbers that are divisible by 3 and 5 appear twice in the sum (in the sum of all numbers divisible by 3 and the sum of all numbers divisble by 5). Since 3 and 5 are prim, all numbers that are divisible by 3 and 5 are multiples of 15.

int sum_div3_5(int n)
    int div_3 = (n - 1) / 3 , 
        div_5 = (n - 1) / 5 , 
        div_15 = (n - 1) / 15

    int sum = div_3 * (div_3 + 1) * 3 / 2 + //sum of all numbers divisible by 3
              div_5 * (div_5 + 1) * 5 / 2 - //sum of all numbers divisible by 5
              div_15 * (div_15 + 1) * 15 / 2

    return sum

I can't provide python code though.

Source Link
Paul
  • 41
  • 3

This code is extremely inefficient. Using some basic math we can reduce runtime to constant time complexity. For any n (in this case 1000), we can predict the number of numbers < n and divisible by 3 or 5:

  • numbers divisible by 3: lowerbound(n / 3)
  • numbers divisible by 5: lowerbound(n / 5)

The sum of all numbers divisible by 3 or 5 can then be predicted using eulers formula:
the sum of all numbers from 1 to n is n(n + 1)/2. Thus the sum of all numbers n divisible by 3 is:

int div_3 = (n / 3)
int sum_div_3 = div_3 * (div_3 + 1) / 2 * 3

Now there's only one point left: all numbers that are divisible by 3 and 5 appear twice in the sum (in the sum of all numbers divisible by 3 and the sum of all numbers divisble by 5). Since 3 and 5 are prim, all numbers that are divisible by 3 and 5 are multiples of 15.

int sum_div3_5(int n)
    int div_3 = n / 3 , 
        div_5 = n / 5 , 
        div_15 = n / 15

    int sum = div_3 * (div_3 + 1) * 3 / 2 + //sum of all numbers divisible by 3
              div_5 * (div_5 + 1) * 5 / 2 - //sum of all numbers divisible by 5
              div_15 * (div_15 + 1) * 15 / 2

    return sum

I can't provide python code though.