프로젝트 오일러 #1: 3 또는 5의 배수

문제 설명:

10 미만의 3 또는 5의 배수인 자연수를 모두 나열하면 3, 5, 6 및 9가 됩니다. 이 배수의 합은 23입니다.
1000 미만의 3 또는 5의 모든 배수의 합을 구하십시오. HackerRank의 경우 N 미만의 배수의 합을 찾아야 합니다.

링크: Project Euler , HackerRank

#1 순진한 솔루션:

간단한 해결책은 모든 숫자를 반복하고 3 또는 5로 나누어지는 숫자를 추가하는 것입니다. 아래 코드를 참조하세요. 여기의 코드는

오(엔)오(엔)오(엔)

. 이것은 프로젝트 오일러 제약 조건에 대해 괜찮은 것 같습니다.

NNN

~이다

100010001000

. 그러나 이 코드는 HackerRank 문제에 대한 TLE를 생성합니다.

NNN

까지 할 수 있습니다

10910^9109

.

def slow_sum_of_multiples_of_3_or_5(till: int) -> int:
    sum_of_multiples = 0
    for num in range(till):
        if num % 3 == 0 or num % 5 == 0:
            sum_of_multiples += num
    return sum_of_multiples

#2 Pythonic Naive 솔루션:

파이썬의 list comprehension 을 사용하여 위의 솔루션을 더 간결하게 만들 수 있습니다. 이렇게 하면 코드가 더 빨라지지 않습니다.

def pythonic_sum_of_multiples_of_3_or_5(till: int) -> int:
    return sum(x for x in range(till) if x % 3 == 0 or x % 5 == 0)

#3 산술 진행 사용:

공차가 제수인 경우 배수는 Arithmetic Progression으로 간주할 수 있습니다.
산술 진행의 덧셈을 계산하는 직접 공식이 있습니다.

(firstElement+lastElement)*numOfElements/2
(firstElement + lastElement) * numOfElements/2
(firstElement+lastElement)*numOfElements/2


이에 대한 코드는 다음과 같습니다.

def sum_of_arithmetic_progression(first: int, last: int, no_of_elements: int) -> int:
    return (first + last) * no_of_elements // 2

이제 3의 배수와 5의 배수를 모두 더해야 합니다.
3의 배수:

3,6,9,12,15,18,21,24,27,30,...3, 6, 9, 12,\mathbf{15}, 18, 21, 24, 27,\mathbf{30} , ...3,6,9,12,15,18,21,24,27,30,...


5의 배수:

5,10,15,20,25,30,35,40,...5, 10,\mathbf{15}, 20, 25,\mathbf{30}, 35, 40, ...5,10, 15,20,25,30,35,40,...

위에서 볼 수 있듯이 배수를 더하면 15의 배수가 추가됩니다. 일부 숫자는 3과 5로 나누어지기 때문에 두 번 더할 것입니다. 따라서 올바른 덧셈을 얻으려면 3의 배수와 5의 배수의 덧셈에서 15의 ​​배수(3과 5의 LCM, 즉 3과 5로 나누어지는 숫자)를 빼야 합니다. 공식은 다음과 같습니다.

3의 배수+5의 배수−15의 배수
multiplesOf3 + multiplesOf5 - multiplesOf15
3의 배수+5의 배수−15의 배수


아래의 전체 코드를 참조하십시오. 이 코드는 주어진 시간 동안 일관된 시간이 걸립니다.

NNN

. 따라서 이에 대한 시간복잡도는

오(1)오(1)오(1)

.

def fast_sum_of_multiples_of_3_or_5(till: int) -> int:
    till -= 1  # We don't want to include `till` in our summation.

    def sum_of_multiples(of: int) -> int:
        """ Short hand function to return sum of arithmetic progression. """
        no_of_elements_divisible = till // of
        last_divisible = no_of_elements_divisible * of
        return sum_of_arithmetic_progression(
            first=of, last=last_divisible, no_of_elements=no_of_elements_divisible)

    return sum_of_multiples(of=3) + sum_of_multiples(of=5) - sum_of_multiples(of=15)


def sum_of_arithmetic_progression(first: int, last: int, no_of_elements: int) -> int:
    return (first + last) * no_of_elements // 2

읽어 주셔서 감사합니다.