Ad
hellosirsvs.badfish1337

Sum of Multiples

Code
Diff
  • def sum_natural_numbers_till(n):
    return int((n * (n+1))/2)


def find_multiples(n):
    # runs in O(1) instead of O(n)
    total = 0
    if n <= 0:
        return 0
    fours = n // 4 if n % 4 != 0 else n // 4 - 1
    sixes = n // 6 if n % 6 != 0 else n // 6 - 1
    twelves = n // 12 if n % 12 != 0 else n // 12 - 1
    total = 4 * sum_natural_numbers_till(fours) + 6 * sum_natural_numbers_till(sixes) - 12 * sum_natural_numbers_till(twelves)
    return total
    • def sum_natural_numbers_till(n):
    • return int((n * (n+1))/2)
    • def find_multiples(n):
    • # runs in O(1) instead of O(n)
    • total = 0
    • for i in range(0, n, 2):
    • if i % 4 == 0 or i % 6 == 0:
    • total += i
    • return total
    • if n <= 0:
    • return 0
    • fours = n // 4 if n % 4 != 0 else n // 4 - 1
    • sixes = n // 6 if n % 6 != 0 else n // 6 - 1
    • twelves = n // 12 if n % 12 != 0 else n // 12 - 1
    • total = 4 * sum_natural_numbers_till(fours) + 6 * sum_natural_numbers_till(sixes) - 12 * sum_natural_numbers_till(twelves)
    • return total