algoadvance

Leetcode 2652. Sum Multiples

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.

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.

Clarifying Questions

  1. Are the values of n sufficiently large that performance becomes a concern?
    • This will help determine if optimization is necessary.
  2. Is it guaranteed that n is always positive?
    • This ensures we don’t need to handle negative or zero cases.
  3. Are there any constraints on the range of n?
    • This would guide whether edge cases or specific optimizations are needed.

Strategy

To solve this problem, we will use a straightforward approach using a loop:

  1. Initialize a variable to store the cumulative sum.
  2. Iterate from 1 to n.
  3. For each number in this range, check if it is divisible by 3, 5, or 7 using the modulo operator.
  4. If it is divisible, add it to the cumulative sum.
  5. Return the cumulative sum.

This approach is both straightforward and easy to implement. Given the constraints (1 through 10^4), the linear time complexity should be sufficient.

Time Complexity

Code

Here’s the implementation in C++:

#include <iostream>

class Solution {
public:
    int sumOfMultiples(int n) {
        int sum = 0;
        for (int i = 1; i <= n; ++i) {
            if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0) {
                sum += i;
            }
        }
        return sum;
    }
};

int main() {
    Solution sol;
    std::cout << sol.sumOfMultiples(7) << std::endl;  // Output: 21
    std::cout << sol.sumOfMultiples(10) << std::endl; // Output: 40
    std::cout << sol.sumOfMultiples(9) << std::endl;  // Output: 30
    return 0;
}

This solution iterates through each number from 1 to n, checks each one for divisibility by 3, 5, or 7, and adds it to the sum if it meets any condition. This achieves the desired result with linear time complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI