21. Sum of all divisors from 1 to n

The problem can be found at the following link: Question Link

My Approach

By obsevation, you will notice that each number appears a total of (N/i) times.

To find the sum of all divisors from 1 to N,

• I iterate through numbers from 1 to N and add up the contributions from each number by ((N/i)*i)

Explain with example

Let's take N = 6 as an example.

• For i = 1, it is a divisor of 1, 2, 3, 4, 5, and 6, so it contributes 1 + 1 + 1 + 1 + 1 + 1 = 6 to the sum.

• For i = 2, it is a divisor of 2, 4, and 6, so it contributes 2 + 2 + 2 = 6 to the sum.

• For i = 3, it is a divisor of 3 and 6, so it contributes 3 + 3 = 6 to the sum.

• For i = 4, it is a divisor of 4, so it contributes 4 to the sum.

• For i = 5, it is a divisor of 5, so it contributes 5 to the sum.

• For i = 6, it is a divisor of 6, so it contributes 6 to the sum.

Adding all these contributions gives the final sum, which is 6 + 6 + 6 + 4 + 5 + 6 = 33, which is the sum of divisors from 1 to 6.

Time and Auxiliary Space Complexity

• Time Complexity: O(N) - We iterate through numbers from 1 to N.

• Auxiliary Space Complexity: O(1) - We use a constant amount of extra space.

Code (C++)

class Solution {
public:
    long long sumOfDivisors(int N) {
        long long out = 0;
        for (int i = 1; i <= N; ++i) {
            out += (N / i) * i;
        }
        return out;
    }
};

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.