Sum Multiples

Easy
692.

Sum Multiples

Sum Multiples is an easy coding problem on math and number theory, asked in TCS, Infosys and Accenture interviews.

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

Example 1

Input
n = 7
Output
21
Explanation
3 + 5 + 6 + 7 = 21.

Example 2

Input
n = 10
Output
40
Explanation
3 + 5 + 6 + 7 + 9 + 10 = 40.

Example 3

Input
n = 9
Output
30

Constraints

  • 1 <= n <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var sumOfMultiples = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Sum Multiples — Solution in Python, Java & C++

Sum Multiples solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at TCS and Infosys.

Sum Multiples is an easy coding problem on math and number theory, asked in TCS, Infosys and Accenture interviews.

  • Difficulty: Easy
  • Topics: Math, Number Theory
  • Asked at: TCS, Infosys, Accenture
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

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

Example 1

Input: n = 7
Output: 21
Explanation: 3 + 5 + 6 + 7 = 21.

Example 2

Input: n = 10
Output: 40
Explanation: 3 + 5 + 6 + 7 + 9 + 10 = 40.

Example 3

Input: n = 9
Output: 30

Constraints

  • 1 <= n <= 1000

Hints for Sum Multiples

  1. Hint 1

    A direct loop over 1..n is plenty at this size.

  2. Hint 2

    Use or, not and — a number qualifies if any of the three divides it.

  3. Hint 3

    The closed form uses inclusion–exclusion over the three divisors and their products.

How to solve Sum Multiples

Test each candidate against the three divisors and add it when any one divides it. The arithmetic shortcut is inclusion–exclusion, which computes the same total in constant time.

Approach

  1. Loop x from 1 to n.
  2. If x % 3 == 0 or x % 5 == 0 or x % 7 == 0, add x to the total.

Why it works

The closed form is S(3) + S(5) + S(7) - S(15) - S(21) - S(35) + S(105), where S(d) sums the multiples of d up to n. That is inclusion–exclusion on the three divisibility events, and it agrees with the loop.

Complexity

  • Time — O(n), or O(1) with inclusion–exclusion
  • Space — O(1)

Pitfalls

  • Adding a number once per matching divisor double counts multiples of 15, 21, 35 and 105.
  • Summing S(3) + S(5) + S(7) without subtracting the overlaps makes exactly that mistake.

Reference solution

Python

def sumOfMultiples(n: int) -> int:
    return sum(x for x in range(1, n + 1) if x % 3 == 0 or x % 5 == 0 or x % 7 == 0)

Java

public static int sumOfMultiples(int n) {
    int total = 0;
    for (int x = 1; x <= n; x++) {
        if (x % 3 == 0 || x % 5 == 0 || x % 7 == 0) total += x;
    }
    return total;
}

C++

int sumOfMultiples(int n) {
    int total = 0;
    for (int x = 1; x <= n; x++) {
        if (x % 3 == 0 || x % 5 == 0 || x % 7 == 0) total += x;
    }
    return total;
}

JavaScript

var sumOfMultiples = function(n) {
    var total = 0;
    for (var x = 1; x <= n; x++) {
        if (x % 3 === 0 || x % 5 === 0 || x % 7 === 0) total += x;
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue