Skip to main content

Sum of All Divisors from 1 to N

Introduction

In this blog, we will discuss the problem of finding the sum of all divisors from 1 to N. This problem is an observation-based problem with a tint of simple mathematics. We will explore different approaches and algorithms to solve this problem efficiently.

Understanding the Problem

The problem statement is self-explanatory. Given a number N, we need to find the sum of all its divisors from 1 to N.

Brute Force Approach

Initially, we can think of solving this problem using a brute force approach. We can iterate from 1 to N and check if each number is a divisor of N. If it is a divisor, we add it to the sum. However, this approach is not optimal for large values of N.

Optimized Approach

To optimize the solution, we can use a contribution technique. Instead of finding all the divisors individually, we can find the contribution of each number in the sum. Let's understand this technique with an example:

For N = 8:

  • 1 can contribute to all numbers from 1 to 8
  • 2 can contribute to all even numbers from 2 to 8
  • 3 can contribute to 3, 6
  • 4 can contribute to 4
  • 5 can contribute to 5
  • 6 can contribute to 6
  • 7 can contribute to 7
  • 8 can contribute to 8

Using this contribution technique, we can calculate the sum of all divisors without finding them individually.

Implementation

Let's implement the optimized approach in code:


long long sumOfDivisors(int N) {
    long long sum = 0;
    for (int i = 1; i <= N; i++) {
        sum += (N / i) * i;
    }
    return sum;
}

The time complexity of this solution is O(N), and the space complexity is O(1) as we are using only a few variables.

Conclusion

In this blog, we discussed the problem of finding the sum of all divisors from 1 to N. We explored the brute force approach and an optimized approach using the contribution technique. The optimized approach is more efficient for large values of N. We implemented the optimized approach in code with a time complexity of O(N) and a space complexity of O(1).

Thank you for reading and have a nice day!

Comments

Post a Comment

Popular posts from this blog

UPI Chalega: The Future of Digital Payments in India

  If you are looking for a fast, easy, and secure way to make payments online, you might want to try UPI. UPI stands for Unified Payments Interface, a system that allows you to transfer money instantly from your bank account to any other bank account or merchant using a mobile app. UPI is developed by the National Payments Corporation of India (NPCI), a government-backed organization that aims to promote digital payments in the country. How does UPI work? To use UPI, you need to download a UPI app from your app store. There are many UPI apps available, such as Google Pay, PhonePe, Paytm, BHIM, etc. You can choose any app that you like, as they are all interoperable, meaning you can send and receive money from any other UPI app. Once you download the app, you need to link your bank account to it by entering your bank details and verifying your mobile number. You will also create a UPI ID, which is a unique identifier that you can use to make and receive payments. A UPI ID looks like...
Post a Comment
Read more

Tic Tac Toe Offline (2 player) - Privacy Policy

  Privacy Policy This privacy policy applies to the Tic Tac Toe Offline (2 player) app (hereby referred to as "Application") for mobile devices that was created by Ayush Agrawal (hereby referred to as "Service Provider") as a Free service. This service is intended for use "AS IS". Information Collection and Use The Application collects information when you download and use it. This information may include information such as Your device's Internet Protocol address (e.g. IP address) The pages of the Application that you visit, the time and date of your visit, the time spent on those pages The time spent on the Application The operating system you use on your mobile device The Application does not gather precise information about the location of your mobile device. The Service Provider may use the information you provided to contact you from time to time to provide you with important information, required notices and marketing promotions. For a better ex...
Post a Comment
Read more

Recursion: Solving Problems through Recursive Functions

  Problem 1: Print Your Name n Times Let's start with a simple problem: printing your name n times using recursion. The generic way to achieve this would be to run a for loop and print your name n times. However, in this case, we want to use recursion. To solve this problem, we will define a recursive function called f(i, n) . The function takes two parameters: i , which represents the current iteration, and n , which represents the total number of times to print your name. We start by taking the input of n from the user. Then, we call the function f(0, n) , which will recursively print your name n times. Here's how the function works: Check if i is greater than n . If it is, return. Print your name. Call the function f(i + 1, n) to recursively print your name n times. By following these steps, we can easily print your name n times using recursion. Problem 2: Print Numbers from 1 to n Next, let's solve a problem where we need to print numbers from 1 to n in...
Post a Comment
Read more