algoadvance

Given a positive integer n, return the sum of all integers in the range [1, n] inclusive that are divisible by 3, 5, or 7.

Clarifying Questions

1. Q: What should the function return if n is less than 1?
   • A: Since n is defined as a positive integer, this scenario should not occur.
2. Q: Are there any constraints on the size of n?
   • A: The problem statement doesn’t specify constraints, but understanding the typical range can inform our approach. If n is reasonably large, we should ensure our implementation efficiently handles it.

Assuming these points hold, let’s proceed to the strategy and code.

Strategy

1. Iterate through the range:
   • We’ll iterate through the numbers from 1 to n.
2. Check divisibility:
   • For each number in this range, check if it’s divisible by 3, 5, or 7.
3. Accumulate the sum:
   • If a number is divisible by any of these, add it to a running total.
4. Edge cases:
   • Given n starts from 1, an edge case might be where n is just 1 or slightly higher. The code should correctly handle these minimal edge cases.

Code

def sum_of_multiples(n: int) -> int:
    total_sum = 0
    for i in range(1, n + 1):
        if i % 3 == 0 or i % 5 == 0 or i % 7 == 0:
            total_sum += i
    return total_sum

Time Complexity

• Time Complexity: O(n)
  • We iterate over each number from 1 to n once, making this a linear time operation.
• Space Complexity: O(1)
  • We use a constant amount of extra space regardless of input size, primarily for the sum accumulator.

This approach should efficiently handle typical constraints by leveraging a straightforward iteration and conditional checks.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?