Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Sum Multiples solution and explanation

EasyMath6 min read85.9% acceptanceUpdated 9 Apr 2026
Asked atMicrosoft
Practise Sum Multiples
3:56
Leetcode | 2652. Sum Multiples | Easy | Java SolutionDeveloper Docs · 3:56 · 1K viewsWatch on YouTube
9 more videos on this problem
  1. Leetcode | 2652. Sum Multiples | Easy | Java SolutionDeveloper Docs · 3:56 · 1K views
  2. Sum Multiples - Leetcode 2652 - Python | Weekly 342Algorithms Casts · 1:42 · 452 views
  3. Sum Multiples | LeetCode 2652 | CppCodeClips with Abhishek Ranjan · 2:56 · 408 views
  4. 2652. Sum Multiples (Leetcode Easy)Programming Live with Larry · 4:53 · 401 views
  5. LeetCode Weekly contest 342 || 2651. Calculate Delayed Arrival Time || 2652. Sum MultiplesAshish Kumar · 2:11 · 97 views
  6. LeetCode 2652. Sum Multiples, JavaScriptPatrick Codes · 2:27 · 92 views
  7. Find & Sum Multiples Quickly - LeetCode 2652 Detailed Solution!CodingForBeginners · 2:14 · 75 views
  8. Leetcode Poblem 2652. Sum Multiples. Solution with pythonCodium · 2:53 · 47 views
  9. 2652 Sum Multiples - Leetcode - Rustify with PawanPawan Deore · 3:33 · 35 views
  10. 2652. Sum Multiples | LeetCode SolutionVishwa Patel · 2:52 · 33 views

The problem

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

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.

def sum_multiples(n):
    return sum(i for i in range(1, n + 1) if i % 3 == 0 or i % 5 == 0 or i % 7 == 0)

n = 10
print(sum_multiples(n))
public class SumMultiples {
    public static int sumMultiples(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;
    }
    public static void main(String[] args) {
        int n = 10;
        System.out.println(sumMultiples(n));
    }
}
#include <iostream>
using namespace std;

int sumMultiples(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() {
    int n = 10;
    cout << sumMultiples(n) << endl;
    return 0;
}
function sumMultiples(n) {
    let sum = 0;
    for (let i = 1; i <= n; i++) {
        if (i % 3 === 0 || i % 5 === 0 || i % 7 === 0) {
            sum += i;
        }
    }
    return sum;
}

let n = 10;
console.log(sumMultiples(n));
#include <stdio.h>

int sumMultiples(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() {
    int n = 10;
    printf("%d\n", sumMultiples(n));
    return 0;
}
using System;

class Program {
    static int SumMultiples(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;
    }
    static void Main() {
        int n = 10;
        Console.WriteLine(SumMultiples(n));
    }
}

Python allows for concise solutions using generators and list comprehensions. The solution calculates the sum of numbers in range 1 to n, filtering those only divisible by 3, 5, or 7.

Complexity

Time Complexity: O(n)
Space Complexity: O(1) if generator is used implicitly; otherwise, O(n) for list creation.

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.

def sum_divisible_by(n, k):
    p = n // k
    return k * (p * (p + 1)) // 2

def sum_multiples(n):
    return (sum_divisible_by(n, 3) + sum_divisible_by(n, 5) + sum_divisible_by(n, 7) - 
            sum_divisible_by(n, 15) - sum_divisible_by(n, 21) - sum_divisible_by(n, 35) + 
            sum_divisible_by(n, 105))

n = 10
print(sum_multiples(n))
public class SumMultiples {
    private static int sumDivisibleBy(int n, int k) {
        int p = n / k;
        return k * (p * (p + 1)) / 2;
    }
    public static int sumMultiples(int n) {
        return sumDivisibleBy(n, 3) + sumDivisibleBy(n, 5) + sumDivisibleBy(n, 7)
             - sumDivisibleBy(n, 15) - sumDivisibleBy(n, 21) - sumDivisibleBy(n, 35)
             + sumDivisibleBy(n, 105);
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println(sumMultiples(n));
    }
}
#include <iostream>
using namespace std;

int sumDivisibleBy(int n, int k) {
    int p = n / k;
    return k * (p * (p + 1)) / 2;
}

int sumMultiples(int n) {
    return sumDivisibleBy(n, 3) + sumDivisibleBy(n, 5) + sumDivisibleBy(n, 7)
         - sumDivisibleBy(n, 15) - sumDivisibleBy(n, 21) - sumDivisibleBy(n, 35)
         + sumDivisibleBy(n, 105);
}

int main() {
    int n = 10;
    cout << sumMultiples(n) << endl;
    return 0;
}
function sumDivisibleBy(n, k) {
    const p = Math.floor(n / k);
    return k * (p * (p + 1)) / 2;
}

function sumMultiples(n) {
    return sumDivisibleBy(n, 3) + sumDivisibleBy(n, 5) + sumDivisibleBy(n, 7)
         - sumDivisibleBy(n, 15) - sumDivisibleBy(n, 21) - sumDivisibleBy(n, 35)
         + sumDivisibleBy(n, 105);
}

const n = 10;
console.log(sumMultiples(n));
#include <stdio.h>

int sumDivisibleBy(int n, int k) {
    int p = n / k;
    return k * (p * (p + 1)) / 2;
}

int sumMultiples(int n) {
    return sumDivisibleBy(n, 3) + sumDivisibleBy(n, 5) + sumDivisibleBy(n, 7)
         - sumDivisibleBy(n, 15) - sumDivisibleBy(n, 21) - sumDivisibleBy(n, 35)
         + sumDivisibleBy(n, 105);
}

int main() {
    int n = 10;
    printf("%d\n", sumMultiples(n));
    return 0;
}
using System;

class Program {
    static int SumDivisibleBy(int n, int k) {
        int p = n / k;
        return k * (p * (p + 1)) / 2;
    }
    static int SumMultiples(int n) {
        return SumDivisibleBy(n, 3) + SumDivisibleBy(n, 5) + SumDivisibleBy(n, 7)
             - SumDivisibleBy(n, 15) - SumDivisibleBy(n, 21) - SumDivisibleBy(n, 35)
             + SumDivisibleBy(n, 105);
    }
    static void Main() {
        int n = 10;
        Console.WriteLine(SumMultiples(n));
    }
}

This Python version calculates the common divisor sums using helper 'sum_divisible_by'. The inclusion-exclusion formula ensures only unique factors contribute to the total sum.

Complexity

Time Complexity: O(1)
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).

function sumOfMultiples(n: number): number {
    let ans = 0;
    for (let x = 1; x <= n; ++x) {
        if (x % 3 === 0 || x % 5 === 0 || x % 7 === 0) {
            ans += x;
        }
    }
    return ans;
}
func sumOfMultiples(n int) (ans int) {
	for x := 1; x <= n; x++ {
		if x%3 == 0 || x%5 == 0 || x%7 == 0 {
			ans += x
		}
	}
	return
}
impl Solution {
    pub fn sum_of_multiples(n: i32) -> i32 {
        let mut ans = 0;

        for x in 1..=n {
            if x % 3 == 0 || x % 5 == 0 || x % 7 == 0 {
                ans += x;
            }
        }

        ans
    }
}
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)$.

function sumOfMultiples(n: number): number {
    const f = (x: number): number => {
        const m = Math.floor(n / x);
        return ((x + m * x) * m) >> 1;
    };
    return f(3) + f(5) + f(7) - f(3 * 5) - f(3 * 7) - f(5 * 7) + f(3 * 5 * 7);
}
func sumOfMultiples(n int) int {
	f := func(x int) int {
		m := n / x
		return (x + m*x) * m / 2
	}
	return f(3) + f(5) + f(7) - f(3*5) - f(3*7) - f(5*7) + f(3*5*7)
}
impl Solution {
    pub fn sum_of_multiples(n: i32) -> i32 {
        (1..=n)
            .filter(|&x| (x % 3 == 0 || x % 5 == 0 || x % 7 == 0))
            .sum()
    }
}
Try this approach in the editor

Approach 5: Default Approach

impl Solution {
    pub fn sum_of_multiples(n: i32) -> i32 {
        fn f(x: i32, n: i32) -> i32 {
            let m = n / x;
            ((x + m * x) * m) / 2
        }

        f(3, n) + f(5, n) + f(7, n) - f(3 * 5, n) - f(3 * 7, n) - f(5 * 7, n) + f(3 * 5 * 7, n)
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Brute Force Iteration

Time Complexity: O(n)
Space Complexity: O(1) if generator is used implicitly; otherwise, O(n) for list creation.

Formulaic Summation with Inclusion-Exclusion Principle

Time Complexity: O(1)
Space Complexity: O(1)

Enumeration–
Mathematics (Inclusion-Exclusion Principle)–
Default Approach–

Complexity analysis

ApproachTimeSpaceWhen to Use
Brute Force IterationO(n)O(1)Simple implementation or when n is small
Formula + Inclusion-ExclusionO(1)O(1)Best for interviews and large n where iteration is unnecessary

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.

Comments

Now write it yourselfClose this page and solve Sum Multiples in the editor, without looking.
Practise Sum Multiples