Optimizing the "Sum of Multiples of 3 and 5" Problem: A Mathematical Approach

Optimizing the "Sum of Multiples of 3 and 5" Problem in Hackerrank

Problem Overview

In many coding challenges, we encounter the problem of finding the sum of multiples of certain numbers within a given range. One such problem is:

"Find the sum of all multiples of 3 or 5 below a given number n."

Problem Statement:

Given an integer n, the task is to compute the sum of all numbers below n that are divisible by either 3 or 5.

For example:

• Input: n = 10

• Output: 23 because the multiples of 3 or 5 below 10 are 3, 5, 6, 9. Their sum is 3 + 5 + 6 + 9 = 23.

Approach

To solve this problem, we need an efficient approach that works well even for larger values of n, as a brute-force solution would not be fast enough for very large inputs. Let's go through two approaches: a brute-force method and a more optimized mathematical approach.

1. Brute-Force Approach

The simplest method involves iterating through all integers below n and checking if each one is divisible by 3 or 5. If it is, we add it to a running total.

Brute-Force Solution:

Output:

Time Complexity of Brute-Force Approach

• Time Complexity: O(n), where n is the given number for each test case. This solution works by iterating through each number from 1 to n-1.

• Space Complexity: O(1), as we only use a constant amount of space for storing intermediate results.

While this approach works well for small values of n, it becomes inefficient as n grows larger.

2. Optimized Approach: Using Mathematical Formulas

The brute-force solution, while easy to understand, is not optimal when dealing with large values of n. Instead, we can use mathematical formulas to calculate the sum of multiples of 3 and 5 more efficiently.

Mathematical Insight

We can calculate the sum of all multiples of a number x below n using the formula for the sum of an arithmetic series:

Where p is the largest integer such that p * x is less than n. This can be calculated as p = (n - 1) / x.

Steps to Calculate Efficiently:

1. Compute the sum of multiples of 3.

2. Compute the sum of multiples of 5.

3. Subtract the sum of multiples of 15 (since these numbers are counted twice — once for 3 and once for 5).

By using the above approach, we avoid iterating through each number and directly compute the result using simple arithmetic.

Optimized Solution:

Explanation of the Optimized Code:

1. sumDivisibleBy(n, x):
   This function computes the sum of all multiples of x below n. We calculate the largest integer p such that p * x is less than n, and then use the arithmetic progression formula to compute the sum of these multiples.

2. In the main() function:

   • We process multiple test cases.

   • For each test case, we compute:

     • The sum of multiples of 3.

     • The sum of multiples of 5.

     • We subtract the sum of multiples of 15 to avoid counting numbers that are divisible by both 3 and 5.

3. Efficiency:

   • The time complexity is O(1) per test case, as we only perform a constant number of arithmetic operations.

   • The space complexity is O(1), as we use a constant amount of extra space.

Time Complexity of Optimized Approach

• Time Complexity: O(1) per test case, as we are only performing a constant number of arithmetic operations.

• Space Complexity: O(1), since we only store a few variables for each test case.

This solution is ideal for competitive programming platforms like Hackerrank, where efficiency matters for large inputs.

Conclusion

The problem of finding the sum of multiples of 3 and 5 can be solved efficiently using arithmetic progression formulas. By using a mathematical approach, we reduced the time complexity from O(n) to O(1) per test case. This makes the solution scalable even for large values of n.

This optimized approach is not only efficient but also illustrates the power of mathematical insight in solving problems in a computationally effective manner.

Final Thoughts

If you're participating in coding challenges on Hackerrank or similar platforms, it’s essential to look for optimizations early on. Mathematical formulas and techniques like the sum of an arithmetic progression can help you solve problems efficiently, even with large inputs.

Good luck with your coding challenges, and keep practicing! If you found this post helpful, feel free to share it with others who might benefit from this approach.

🔗 Connect With Me

• 🔵 LinkedIn: Neha sharma

• 📲 Telegram: Atcode

Let’s connect and grow together 🚀