Problem

Submissions

Hints & solutions

Discuss

Sum of Factors

Moderate

0/80

Average time to solve is 40m

Contributed by

13 upvotes

Asked in companies

Problem statement

You are given an array/list of integers, your task is to find the sum of all the factors of each number in the array.

For Example:

For ‘N’ = 10
All factors are 1, 2, 5, 10.
So, the sum of them will be 18.

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

Input Format:

The first line contains a single integer ‘N’ denoting the size of the array.

The next line will contain 'N' space-separated integers denoting the elements of the array.

Output Format:

Print 'N' space-separated integers where the i'th element will denote the sum of all the factors of the i'th integer of the given array.

Note:

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

Constraints:

1 <= N <= 10^2
1 <= X <= 10^5
Where 'N' represents the size of the given array and 'X' represents the elements of the array.

Time Limit: 1 sec.

Sample Input 1:

2  
20 11

Sample Output 1:

42 12

Explanation For Sample Output 1:

For the first test case:
All the factors of 20 are 1, 2, 4, 5, 10, 20.
So, the output will be 42.

For the second test case:
All the factors of 11 are 1, 11.
So, the output will be 12.

Sample Input 1:

2
18 22

Sample Output 2:

39 36

Hint 1

Hint 2

Hint 3

Hint 4

Find all the factors of ‘N’ and take their sum.

Approaches (4)

Approach 1

Approach 2

Approach 3

Approach 4

Brute Force

We will iterate from 1 to ‘N’, and if the current number is a factor of ‘N’, we will add it to our answer.

Algorithm:

Declare a variable ‘SUM’ of type integer, and initialize it with zero.
Start iterating from 1 to ‘N’.
1. If the current iterator ( say i ) is a factor of ‘N’ ( N % i == 0 ), then add it to the ‘SUM’.
Finally, return ‘SUM’.

Time Complexity

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

We have to check every number from 1 till ‘N’ to find factors. So the time complexity will be O(N).

Space Complexity

O(1).

Constant extra space is used.

(100% EXP penalty)

Sum of Factors

Console