Introduction

In this blog post, we will explore how to solve the LeetCode problem "2652" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given a positive integer n, find the sum of all integers in the range [1, n] inclusive that are divisible by 3, 5, or 7. Return an integer denoting the sum of all numbers in the given range satisfying the constraint. Example 1: Input: n = 7 Output: 21 Explanation: Numbers in the range [1, 7] that are divisible by 3, 5, or 7 are 3, 5, 6, 7. The sum of these numbers is 21. Example 2: Input: n = 10 Output: 40 Explanation: Numbers in the range [1, 10] that are divisible by 3, 5, or 7 are 3, 5, 6, 7, 9, 10. The sum of these numbers is 40. Example 3: Input: n = 9 Output: 30 Explanation: Numbers in the range [1, 9] that are divisible by 3, 5, or 7 are 3, 5, 6, 7, 9. The sum of these numbers is 30. Constraints: 1 <= n <= 103

Explanation

Here's an efficient solution to the problem:

• Inclusion-Exclusion Principle: Utilize the inclusion-exclusion principle to avoid double-counting numbers divisible by more than one of the given divisors (3, 5, and 7).
• Sum of Arithmetic Progression: Calculate the sum of multiples of each divisor using the formula for the sum of an arithmetic progression: sum = (count * (first + last)) / 2.

• Optimization: Minimize iterations by directly calculating sums of multiples instead of iterating through the entire range.

• Runtime Complexity: O(1) - Constant time. The number of operations is independent of the input n.

• Storage Complexity: O(1) - Constant space. We only use a few variables.

Code

    def sum_multiples(n: int) -> int:
    """
    Given a positive integer n, find the sum of all integers in the range [1, n]
    inclusive that are divisible by 3, 5, or 7.

    Return an integer denoting the sum of all numbers in the given range satisfying
    the constraint.

    For example:
    sum_multiples(7) == 21
    sum_multiples(10) == 40
    sum_multiples(9) == 30
    """

    def sum_divisible_by(divisor: int, limit: int) -> int:
        count = limit // divisor
        first = divisor
        last = count * divisor
        return count * (first + last) // 2

    sum_3 = sum_divisible_by(3, n)
    sum_5 = sum_divisible_by(5, n)
    sum_7 = sum_divisible_by(7, n)
    sum_15 = sum_divisible_by(15, n)
    sum_21 = sum_divisible_by(21, n)
    sum_35 = sum_divisible_by(35, n)
    sum_105 = sum_divisible_by(105, n)

    return sum_3 + sum_5 + sum_7 - sum_15 - sum_21 - sum_35 + sum_105