Problem

Submissions

Hints & solutions

Discuss

Sum of all divisors

Easy

0/40

Contributed by

364 upvotes

Problem statement

You are given an integer ‘n’.

Function ‘sumOfDivisors(n)’ is defined as the sum of all divisors of ‘n’.

Find the sum of ‘sumOfDivisors(i)’ for all ‘i’ from 1 to ‘n’.

Example:

Input: ‘n’  = 5

Output: 21

Explanation:
We need to find the sum of ‘sumOfDivisors(i)’ for all ‘i’ from 1 to 5. 
‘sumOfDivisors(1)’ = 1
‘sumOfDivisors(2)’ = 2 + 1 = 3
‘sumOfDivisors(3)’ = 3 + 1 = 4
‘sumOfDivisors(4)’ = 4 + 2 +1 = 7 
‘sumOfDivisors(5)’ = 5 + 1 = 6
Therefore our answer is sumOfDivisors(1) + sumOfDivisors(2) + sumOfDivisors(3) + sumOfDivisors(4) + sumOfDivisors(5) = 1 + 3 + 4 + 7 + 6 = 21.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of the input contains an integer ‘n’.

Output Format:

Return an integer as described in the problem statement.

Note

You don’t need to print anything, it has already been taken care of, just complete the given function.

Sample Input 1:

Sample Output 1:

Explanation of sample output 1:

We need to find sumOfDivisors(1) + sumOfDivisors(2) +sumOfDivisors(3).
sumOfDivisors(1) = 1
sumOfDivisors(2) = 2 + 1 = 3
sumOfDivisors(3) = 3 + 1 = 4
Therefore, the answer is sumOfDivisors(1) + sumOfDivisors(2) + sumOfDivisors(3) = 1 + 3 + 4 = 8.

Sample Input 2:

Sample Output 2:

Expected Time Complexity:

Try to solve this in O(sqrt(‘n’)).

Constraints:

1 <= ‘n’ <= 3*10^4

Time Limit: 1 sec

Hint 1

Hint 2

Hint 3

Find the value of all sumOfDivisors(i) individually.

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

We will iterate through all the values of ‘i’ from 1 to ‘n’. For each value of ‘i’ we will find the value of ‘sumOfDivisors(i)’ and add it to our final answer. ‘sumOfDivisors(i)’ is the sum of all the divisors of ‘i’.

We can find the value of ‘sumOfDivisors(i)’ in square root time complexity by iterating through all the integers from 1 to ‘sqrt(i)’ using ‘j’. If ‘i’ is divisible by ‘j’ then we will add both ‘j’ and ‘i / j’ to the final answer. If j = sqrt(i), we will only add ‘j’ to the final answer to avoid double counting.

The steps are as follows:

function sumOfAllDivisors(int ‘n’)

Initialize ‘ans’ = 0
For ‘i’ from 1 to ‘n’:
- For ‘j’ from 1 to ‘sqrt(i)’:
  - If(‘i’ % ‘j’ == 0)
    1. If(‘i’ / ‘j’ == ‘j’)
      - ‘ans’ += j
    2. Else
      - ‘ans’ += j + i / j
Return ‘ans’.

Time Complexity

O(n * sqrt(n)), where ‘n’ is the given integer.

We are iterating via ‘i’ from 1 to ‘n’, and for each value of ‘i’ we are iterating from 1 to ‘sqrt(i)’.

Hence, the time complexity is O(n * sqrt(n)).

Space Complexity

O(1).

We are not using any extra space.

Hence, the space complexity is O(1).

(100% EXP penalty)

Sum of all divisors

Gaurav Kumar

Interview problems

Sum of all divisors

int sumOfAllDivisors(int n){

int sum = 0;

for (int i = 1; i <=n; i++) {

sum = sum+(n/i)*i;

}

return sum;

}

535 views

0 replies

4 upvotes

Shivam Agrawal

Interview problems

Java Solution Optimised

public class Solution {

public static int sumOfAllDivisors(int n){

int ans = 0;

int i = 1;

while (i <= n)

{

int val = n / i;

ans = ans + (i * val);

i = i + 1;

}

return ans;

}

296 views

0 replies

0 upvotes

EKANSH KUMAR

Interview problems

java solution

public class Solution {

public static int sumOfAllDivisors(int n){

int sum = 0;

// Iterate over each number from 1 to n

for (int i = 1; i <= n; i++) {

// Add 'i' to the sum for every multiple of 'i'

sum =sum + (n / i) * i;

}

return sum;

}

181 views

0 replies

0 upvotes

Amrit Sinha

Interview problems

Java Easy | Two Approach | Beginner | 1 test case failed!

public class Solution {
    // public static int sumOfDivisors(int num){
    //     int sum = 0;
    //     for(int i = 1; i <= num; i++) if(num % i == 0) sum += i;
    //     return sum;
    // }
    public static int sumOfDivisors(int num){
        int sum = 0;
        for(int i = 1; i*i <= num; i++) 
            if(num % i == 0){
                sum += i;
                if(num / i != i) sum += num/i;
            }
        return sum;
    }

    public static int sumOfAllDivisors(int num){
        int sum = 0;
        for(int i = 1; i <= num; i++) sum += sumOfDivisors(i);
        return sum;
    }
}

249 views

0 replies

0 upvotes

Anand Kumar Jha

Interview problems

C++ Easy Solution

int sumOfAllDivisors(int n){

int sum = 0;

for(int i = 1; i<=n; i++){

sum +=(n/i)*i;

}

return sum;

}

422 views

0 replies

1 upvote

DURGA PRASAD GIRI

Interview problems

Simple Code for Java but time limit is more.....

public class Solution {

public static int sumOfAllDivisors(int n){

int sum=0;

for(int i=1;i<=n;i++){

for(int j=1;j<=i;j++){

if(i%j==0){

sum=sum+j;

}}

}

return sum;

}

121 views

0 replies

0 upvotes

Ankur Kumar

Interview problems

time limit exceed is showing up in this code

long long sum=0;

int sumOfAllDivisors(int n){

// Write your code here.

if(n<1) return sum;

for(long long i=1;i<=n;i++){

if(n%i==0) sum+=i;

}

sumOfAllDivisors(n-1);

}

107 views

1 reply

3 upvotes

Kavisha Shah

Interview problems

one test case not passed

int sumOfAllDivisors(int n){

// Write your code here.

int mainsum=0;

for(int i=1;i<=n;i++){

int sum=0;

for(int j=1;j<=i;j++){

if(i%j==0){

sum=sum+j;

}

mainsum+=sum;

}

return mainsum;

}

84 views

0 replies

0 upvotes

Saurabh Kumar

Interview problems

Most optimal Solution

// Guys I will just try to give Idea here :

suppose we are given N = 5 ,

Now we have to find factors of 1, 2,3,4,5 that will be

f1 = 1, f2 = 1 + 2 , f3 = 1 + 3, f4 = 1+2+4, f5 = 1+5, and then we try to sum them so ans will be

ans = f1 + f2 + f3 + f4 + f5

= 1 + (1 + 2) + (1 + 3) + (1 + 2 + 4) + (1 + 5) // equals 21

now club alike terms

= (1x5) + (2x2) + (3x1) + (4x1)+(5x1) // remains 21

now this part does the main trick and here I will do some rewriting as

= (1 x (5/1) ) + (2 x(5/2)) + (3x(5/3)) + (4 x (5/4)) + (5x(5/5)) //still remains 21

# here I am doing floor division so example 3/2 = 1 and 7/3 =2

You can See answer remains same so here is our pattern that for any N

ans = (1 x (N/1)) + (2 x (N/2)) + (3x(N/3)) + ... + (Nx(N/N))

# apply this on some value of N and it may become more clear

this is O(N) solution I hope you can code this on your own . Hope it helps

280 views

1 reply

7 upvotes

Gourav Ghoshi

Interview problems

Can anyone give me a better approach

int sumOfAllDivisors(int n){

int sum=0;

for(int i=1; i<=n; i++){

for(int j=1; j<=i; j++){

if(i%j == 0){

sum+=j;

}

return sum;

}

it passes all test cases but

this is showing time limit exceeded, can anyone help me

290 views

1 reply

0 upvotes

Console