Sum Multiples - Solution & Explanation

Q: Is Sum Multiples easy or hard?

Sum Multiples is rated Easy on LeetCode with a high acceptance rate around 85%. The brute force solution is straightforward, while the optimized formula-based approach introduces a small mathematical optimization using inclusion-exclusion.

Q: Sum Multiples Python/Java solution

Both Python and Java implementations follow the same logic. The brute force version loops from 1 to n and checks divisibility with modulus operations. The optimized version calculates sums using arithmetic series formulas and inclusion-exclusion, reducing runtime to O(1).

Q: How to solve Sum Multiples in O(1)?

Use the arithmetic progression formula to sum multiples of each divisor. For a divisor k, compute m = floor(n / k) and sum = k * m * (m + 1) / 2. Add sums for 3, 5, and 7, subtract sums for their pairwise LCMs (15, 21, 35), and add back the triple LCM (105). This inclusion-exclusion adjustment avoids double counting and runs in constant time.

Q: What is the best approach for Sum Multiples?

The optimal approach uses an arithmetic series formula combined with the inclusion-exclusion principle. Instead of iterating through every number, compute the sum of multiples of 3, 5, and 7 using k * m * (m + 1) / 2 where m = floor(n / k). Then subtract overlaps such as multiples of 15, 21, and 35, and add back the triple overlap 105. This produces an O(1) time and O(1) space solution.

Q: Is Sum Multiples asked at Google/Amazon/Meta?

Sum Multiples is categorized as an Easy math problem and is more commonly used in screening rounds or practice sets rather than deep algorithm interviews. Variants involving divisibility, arithmetic series, or inclusion-exclusion can appear in interviews at companies like Amazon or Google when testing mathematical reasoning.

Q: What data structure is used in Sum Multiples?

No complex data structure is required. The problem relies primarily on mathematical reasoning and arithmetic operations. A few integer variables are used to track counts and sums, keeping the space complexity constant.

Q: What is the time complexity of Sum Multiples?

The brute force method runs in O(n) time because it checks every integer from 1 to n for divisibility by 3, 5, or 7. The optimized mathematical approach runs in O(1) time since it uses constant arithmetic calculations and no loops. Both approaches use O(1) space.

EasyMath19 min readAsked at: Microsoft

Practice this problem

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 <= 10³

Approach Overview

Problem Overview: Given an integer n, compute the sum of all numbers in the range [1, n] that are divisible by 3, 5, or 7. Any number divisible by at least one of these values contributes to the total.

Approach 1: Brute Force Iteration (O(n) time, O(1) space)

Scan every integer from 1 to n. For each value i, check divisibility using modulus operations: i % 3 == 0, i % 5 == 0, or i % 7 == 0. If any condition holds, add i to a running sum. The algorithm performs a constant number of checks per number, so the runtime grows linearly with n. Space usage stays O(1) since only a few variables are maintained. This approach is straightforward and easy to implement in any language, but it becomes inefficient if n is very large.

Approach 2: Formulaic Summation with Inclusion-Exclusion Principle (O(1) time, O(1) space)

This method avoids iteration by using arithmetic series formulas from math. First compute the sum of multiples of a number k up to n. If m = floor(n / k), the multiples are k, 2k, 3k ... mk. Their sum equals k * m * (m + 1) / 2. Compute this for 3, 5, and 7. However, numbers divisible by multiple values get counted more than once. Apply the inclusion-exclusion principle: subtract sums for lcm(3,5)=15, lcm(3,7)=21, and lcm(5,7)=35, then add back the triple overlap lcm(3,5,7)=105. Each term uses the same arithmetic progression formula, so the final result is computed in constant time with a few arithmetic operations.

Recommended for interviews: Start with the brute force iteration to show you understand the requirement and divisibility checks. Then optimize using the arithmetic series formula and inclusion-exclusion. Interviewers usually expect the constant-time mathematical solution because it demonstrates comfort with mathematical reasoning and eliminating unnecessary loops.

Approach 1: Brute Force Iteration

This approach involves iterating through each number from 1 to n and checking if it is divisible by either 3, 5, or 7. If it is, add this number to the sum. This is a straightforward approach which ensures we only consider numbers that are divisible by these values.

The code iterates through each integer i from 1 to n. For each i, it checks if i is divisible by 3, 5, or 7 (i.e., the remainder when i is divided by 3, 5, or 7 is zero). If true, i is added to the sum. Finally, the sum is returned.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n) because we iterate through all numbers from 1 to n.
Space Complexity: O(1) because we only use a constant amount of space.

Try this approach in the editor →

Approach 2: Formulaic Summation with Inclusion-Exclusion Principle

This approach leverages the principle of inclusion-exclusion to calculate the sum of multiples without iterating through every number from 1 to n. It exploits the summation formula for arithmetic series to compute the sum of multiples of 3, 5, or 7, and their intersections to avoid double counting.

Using inclusion-exclusion principle, 'sumMultiples' calculates the sum of all multiples of 3, 5, and 7 efficiently, considering overlaps. The helper function, 'sumDivisibleBy', calculates the sum of multiples of any 'k' using arithmetic series summation.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(1) since the calculations are constant-time after initial parameter evaluation.
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Enumeration

We directly enumerate every number x in [1,..n], and if x is divisible by 3, 5, and 7, we add x to the answer.

After the enumeration, we return the answer.

The time complexity is O(n), where n is the given integer. The space complexity is O(1).

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Approach 4: Mathematics (Inclusion-Exclusion Principle)

We define a function f(x) to represent the sum of numbers in [1,..n] that are divisible by x. There are m = \left\lfloor \frac{n}{x} \right\rfloor numbers that are divisible by x, which are x, 2x, 3x, cdots, mx, forming an arithmetic sequence with the first term x, the last term mx, and the number of terms m. Therefore, f(x) = \frac{(x + mx) times m}{2}.

According to the inclusion-exclusion principle, we can obtain the answer as:

$f(3) + f(5) + f(7) - f(3 times 5) - f(3 times 7) - f(5 times 7) + f(3 times 5 times 7)

The time complexity is O(1), and the space complexity is O(1)$.

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Approach 5: Default Approach

Code

Rust

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Brute Force Iteration	Time Complexity: O(n) because we iterate through all numbers from 1 to n. Space Complexity: O(1) because we only use a constant amount of space.
Formulaic Summation with Inclusion-Exclusion Principle	Time Complexity: O(1) since the calculations are constant-time after initial parameter evaluation. Space Complexity: O(1)
Enumeration	—
Mathematics (Inclusion-Exclusion Principle)	—
Default Approach	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Brute Force Iteration	O(n)	O(1)	Simple implementation or when n is small
Formula + Inclusion-Exclusion	O(1)	O(1)	Best for interviews and large n where iteration is unnecessary

Video Solution

Leetcode | 2652. Sum Multiples | Easy | Java Solution • Developer Docs • 1,118 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sum Multiples easy or hard?

Sum Multiples is rated Easy on LeetCode with a high acceptance rate around 85%. The brute force solution is straightforward, while the optimized formula-based approach introduces a small mathematical optimization using inclusion-exclusion.

Sum Multiples Python/Java solution

Both Python and Java implementations follow the same logic. The brute force version loops from 1 to n and checks divisibility with modulus operations. The optimized version calculates sums using arithmetic series formulas and inclusion-exclusion, reducing runtime to O(1).

How to solve Sum Multiples in O(1)?

Use the arithmetic progression formula to sum multiples of each divisor. For a divisor k, compute m = floor(n / k) and sum = k * m * (m + 1) / 2. Add sums for 3, 5, and 7, subtract sums for their pairwise LCMs (15, 21, 35), and add back the triple LCM (105). This inclusion-exclusion adjustment avoids double counting and runs in constant time.

What is the best approach for Sum Multiples?

The optimal approach uses an arithmetic series formula combined with the inclusion-exclusion principle. Instead of iterating through every number, compute the sum of multiples of 3, 5, and 7 using k * m * (m + 1) / 2 where m = floor(n / k). Then subtract overlaps such as multiples of 15, 21, and 35, and add back the triple overlap 105. This produces an O(1) time and O(1) space solution.

Is Sum Multiples asked at Google/Amazon/Meta?

Sum Multiples is categorized as an Easy math problem and is more commonly used in screening rounds or practice sets rather than deep algorithm interviews. Variants involving divisibility, arithmetic series, or inclusion-exclusion can appear in interviews at companies like Amazon or Google when testing mathematical reasoning.

What data structure is used in Sum Multiples?

No complex data structure is required. The problem relies primarily on mathematical reasoning and arithmetic operations. A few integer variables are used to track counts and sums, keeping the space complexity constant.

What is the time complexity of Sum Multiples?

The brute force method runs in O(n) time because it checks every integer from 1 to n for divisibility by 3, 5, or 7. The optimized mathematical approach runs in O(1) time since it uses constant arithmetic calculations and no loops. Both approaches use O(1) space.

Ready to solve this problem?

Practice Sum Multiples with our built-in code editor and test cases.

Practice on FleetCode

Add Two Numbers

Reverse Integer

Problem Info

DifficultyEasy

Acceptance85.9%

Approaches5

Reading time19 min

Asked at

Microsoft

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Brute Force Iteration

Code

Complexity

Approach 2: Formulaic Summation with Inclusion-Exclusion Principle

Code

Complexity

Approach 3: Enumeration

Code

Approach 4: Mathematics (Inclusion-Exclusion Principle)

Code

Approach 5: Default Approach

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents