All challenges
Easy 0 solved 0% acceptance

Sum of Proper Divisors

Add up every divisor of n that is smaller than n.

What you'll learn

  • Find divisors in pairs
  • Stop the loop at the square root
  • Avoid counting a square root divisor twice

Problem

The proper divisors of n are the positive divisors other than n itself. For 12 they are 1, 2, 3, 4 and 6. Their sum (sometimes called the aliquot sum) tells whether a number is perfect, abundant or deficient. Divisors come in pairs d and n / d, so you only need to try values of d up to the square root of n.

Implement sum_of_proper_divisors(n).

Input

n: A positive integer.

Output

Return the sum of all positive divisors of n that are less than n. For n = 1 there are none, so return 0.

Constraints

1 ≤ n ≤ 10^12

Examples

Example 1
Input:
n = 12

Expected output:
expected = 16
Input:
long long n = 12;

Expected output:
long long expected = 16;
Input:
long n = 12;

Expected output:
long expected = 16;

Explanation

1 + 2 + 3 + 4 + 6 = 16.

Example 2
Input:
n = 28

Expected output:
expected = 28
Input:
long long n = 28;

Expected output:
long long expected = 28;
Input:
long n = 28;

Expected output:
long expected = 28;

Explanation

1 + 2 + 4 + 7 + 14 = 28, so 28 is a perfect number.

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

If d divides n, then n / d divides n too.

Hint 2

Only try d up to the square root of n, adding both members of each pair.

Hint 3

Leave n itself out, and add the square root only once when n is a perfect square.

Expected complexity

O(sqrt n) time, O(1) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.