Sum Of Proper Divisors

Easy

0/40

Average time to solve is 15m

Contributed by

10 upvotes

Asked in companies

Problem statement

Given a natural number 'N', return the sum of all proper divisors of ‘N’.

‘X’ is a proper divisor of ‘Y’ if X < Y and Y % X = 0.

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

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases . Then each test case follows.

The first line of each testcase contains a single integer ‘N’.

Output Format :

For each test case print a single integer denoting the sum of all proper divisors of ‘N’.

Output for each test case will be printed in a separate line.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 10      
1 <= N <= 10^9

Time limit: 1 sec

Sample Input 1 :

2
6
1

Sample Output 1 :

6
0

Explanation For Sample Output 1 :

For test case 1 :
1,2,3 are proper divisors of N=6. Therefore the sum is equal to 1+2+3 = 6

For test case 2 :
No proper divisor of N=1 exists, hence the sum is equal to 0.

Sample Input 2 :

2
5
10

Sample Output 2 :

1
8

Hint 1

Hint 2

Proper divisors of N are smaller than N, try a linear search!

Approaches (2)

Approach 1

Approach 2

Linear Search

For the given N, simply iterate numbers from 1 to N-1 and if the number is divisible by N, then simply add it to the final answer.

The steps are as follows:

Initialize sum = 0
Run a for loop from 1 to N - 1, if the number is divisible by N simply add it to ‘sum’.
Return sum after iterating all elements less than N.

Time Complexity

O( N ), where ‘N’ is the natural number given in input.

Since we iterate over N - 1 numbers, Hence the time complexity is O(N)

Space Complexity

O(1)

Since constant space used. Hence the space complexity is O(1).

(100% EXP penalty)

Sum Of Proper Divisors

Console