Welcome to Subscribe On Youtube

2652. Sum Multiples

Description

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

Solutions

Solution 1: 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)$.

Solution 2: 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)$.

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

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

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

• class Solution:
      def sumOfMultiples(self, 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)
  
  

• 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
  }
  

• 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;
  }
  
  

• 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
      }
  }
  
  

All Problems

All Solutions