Skip to content

2652. Sum Multiples 👍

Approach 1: Brute Force

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
 public:
  int sumOfMultiples(int n) {
    int ans = 0;
    for (int i = 1; i <= n; ++i)
      if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0)
        ans += i;
    return ans;
  }
};

1
2
3
4
5
6
7
8
9
class Solution {
  public int sumOfMultiples(int n) {
    int ans = 0;
    for (int i = 1; i <= n; ++i)
      if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0)
        ans += i;
    return ans;
  }
}

1
2
3
4
5
6
7
class Solution:
  def sumOfMultiples(self, n: int) -> int:
    ans = 0
    for i in range(1, n + 1):
      if i % 3 == 0 or i % 5 == 0 or i % 7 == 0:
        ans += i
    return ans

Approach 2: Intersection Theory

  • Time: $O(1)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  int sumOfMultiples(int n) {
    // Returns the sum of multiples of value in [1, n].
    auto sumOfMultiples = [n](int value) {
      const int lo = value;
      const int hi = n / value * value;
      const int count = (hi - lo) / value + 1;
      return (lo + hi) * count / 2;
    };
    return sumOfMultiples(3) + sumOfMultiples(5) + sumOfMultiples(7) -
           (sumOfMultiples(15) + sumOfMultiples(21) + sumOfMultiples(35)) +
           sumOfMultiples(105);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public class Solution {
  public int sumOfMultiples(int n) {
    return sumOfMultiples(n, 3) + sumOfMultiples(n, 5) + sumOfMultiples(n, 7) -
        (sumOfMultiples(n, 15) + sumOfMultiples(n, 21) + sumOfMultiples(n, 35)) +
        sumOfMultiples(n, 105);
  }

  // Returns the sum of multiples of value in [1, n].
  private int sumOfMultiples(int n, int value) {
    final int lo = value;
    final int hi = n / value * value;
    final int count = (hi - lo) / value + 1;
    return (lo + hi) * count / 2;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def sumOfMultiples(self, n: int) -> int:
    def sumOfMultiples(value: int) -> int:
      """Returns the sum of multiples of value in [1, n]."""
      lo = value
      hi = (n // value) * value
      count = (hi - lo) // value + 1
      return (lo + hi) * count // 2

    return (sumOfMultiples(3) + sumOfMultiples(5) + sumOfMultiples(7) -
            (sumOfMultiples(15) + sumOfMultiples(21) + sumOfMultiples(35)) +
            sumOfMultiples(105))