PROBLEM LINK:
Editorialist: Rounaq Jhunjhunu Wala
DIFFICULTY:
EASY
PREREQUISITES:
Factors
PROBLEM:
Given a number N, we need to find the sum of all factors of N.
EXPLANATION:
This is a very common problem of number theory. The easiest approach to this is to simply loop from 1 to N and add all the numbers which are the factors of N.
ans = 0
for i = 1 to N
if N%i == 0
ans = ans + i
print ans
The above approach works, but it is O(N), so it will give a TLE result. We can do the same in O(\sqrt{N}) time complexity.
We know that for any factor i of N, there is a corresponding factor \frac{N}{i} (if i \neq \sqrt{N}). Now, if we take the smaller of \{i,\frac{N}{i}\}, the value would be atmost \lfloor{\sqrt{N}}\rfloor, because if both factors are greater than this quantity, then their product is greater than N, which is not possible.
The observation above gives us the required algorithm:
ans = 0
for i = 1 until i*i <= N
if N%i == 0
ans = ans + i
if i != N/i:
ans = ans + N/i
print ans
The if check is to handle the case when we get i as the perfect square root of N, in which case only i should be added.